ONE NOTE

Rage, rage against the dying of the light.

Posted on In

Before

今天域名备案流程终于走完了，每次重新开服务器就要重新备案(它生怕我伤害民族感情，我真的哭死)，申请证书，很麻烦，这里就记录一下zero_ssl的免费证书申请流程吧,以后再要搞照着来就行。

Steps

setup

1
2
3
4
5
6
7
8
curl https://get.acme.sh | bash

# auto update (optional)
acme.sh --upgrade --auto-upgrade

acme.sh --set-default-ca --server zerossl

acme.sh --register-account -m hinak0@qq.com --server zerossl
cloudfare
1
2
3
4
export CF_Key="<yourkey>"
export CF_Email="hinak0@qq.com"

acme.sh --issue --dns dns_cf -d hinak0.site -d "*.hinak0.site"
nginx
1
2
3
# auth by nginx
# 记得打开端口防火墙
acme.sh --issue -d hinak0.site -d "*.hinak0.site" --nginx
http-server
1
2
# 确保80端口空闲
acme.sh --issue -d hinak0.site -d "*.hinak0.site"

install cert

1
acme.sh --installcert -d hinak0.site -d "*.hinak0.site" --fullchain-file /usr/local/ssl/hinak0.site.cer --key-file /usr/local/ssl/hinak0.site.key

最后在nginx加载证书

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
server {
  listen 443 ssl;
  server_name hinak0.site;

  ssl_certificate /usr/local/ssl/hinak0.site.cer;
  ssl_certificate_key /usr/local/ssl/hinak0.site.key;

  ssl_session_timeout 5m;
  ssl_ciphers ECDHE-RSA-AES128-GCM-SHA256:ECDHE:ECDH:AES:HIGH:!NULL:!aNULL:!MD5:!ADH:!RC4;
  ssl_protocols TLSv1 TLSv1.1 TLSv1.2;
  ssl_prefer_server_ciphers on;

  location / {
    root /var/www/html/hinak0.github.io;
    index index.html;
  }
}
server {
  listen 80;
  server_name hinak0.site;
  return 301 https://hinak0.site;
}

update cert

1
2
3
4
# 记得保持80端口空闲，关掉nginx的80端口301重定向
acme.sh --renew -d hinak0.site -d "*.hinak0.site" --force

acme.sh --installcert -d hinak0.site -d "*.hinak0.site" --fullchain-file /usr/local/ssl/hinak0.site.cer --key-file /usr/local/ssl/hinak0.site.key

Posted on In

背景

今天打开博客页面，发现主页这么呈现：

很明显是因为随机封面算法是真随机，于是找到现在在用的主题butterfly中，随机封面的算法如下：

1
2
3
4
5
6
7
8
9
const randomCoverFn = () => {
	const {
		cover: { default_cover: defaultCover },
	} = hexo.theme.config;
	if (!defaultCover) return false;
	if (!Array.isArray(defaultCover)) return defaultCover;
	const num = Math.floor(Math.random() * defaultCover.length);
	return defaultCover[num];
};

强迫症简直不能忍，于是立马写一个shuffle函数

闭包+克隆数组的写法

这是想到的最简单的一个办法，写法也简单：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
const defaultCover = ["1", "2", "3", "4", "5"];

const randomCoverFn = (() => {
	if (!defaultCover) return false;
	if (!Array.isArray(defaultCover)) return defaultCover;

	const shuffle = [...defaultCover];
	let lastChoice = null;
	return function () {
		//重新加牌
		if (shuffle.length < 2) {
			shuffle.push(...defaultCover);
		}

		// 防止重新加牌后产生重复，记录上次选择
		let num;
		do {
			num = Math.floor(Math.random() * shuffle.length);
		} while (shuffle[num] === lastChoice);

		// 去掉选择过的
		let res = shuffle.splice(num, 1)[0];
		lastChoice = res;
		return res;
	};
})();

let last = null;
for (let i = 0; i < 1000; i++) {
	let s = randomCoverFn();
	if (last === s) {
		console.log("error !");
	}
	last = s;
}

这个办法问题多多：

  1. 不够优雅
  2. 都记录上次选择了，何必辛苦克隆数组

于是优化版本:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
const defaultCover = ["1", "2", "3", "4", "5"];

const randomCoverFn = (() => {
	if (!defaultCover) return false;
	if (!Array.isArray(defaultCover)) return defaultCover;

	let lastChoice = null;
	return function () {
		let num;
		do {
			num = Math.floor(Math.random() * defaultCover.length);
		} while (lastChoice === num);
		lastChoice = num;

		return defaultCover[num];
	};
})();

let last = null;
for (let i = 0; i < 1000; i++) {
	let s = randomCoverFn();
	if (last === s) {
		console.log("error !");
	}
	last = s;
}

这个办法不错，但测试下来也有缺点，可能出现[1,2,1,2,1,2]这种重复排列，不够完美。

查到资料，有一种Fisher–Yates shuffle算法，更巧妙，链接在这里：

Fisher–Yates shuffle

Fisher–Yates shuffle

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
"use strict";

var randomCoverFn;

const createShuffleClosure = (arr) => {
	const shuffledArray = [...arr];
	const currentShuffleList = [];
	let lastChioce;

	const shuffle = () => {
		// https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
		let currentIndex = arr.length;
		while (currentIndex !== 0) {
			const randomIndex = Math.floor(Math.random() * currentIndex);
			currentIndex--;

			// Swap elements between currentIndex and randomIndex
			const tempValue = shuffledArray[currentIndex];
			shuffledArray[currentIndex] = shuffledArray[randomIndex];
			shuffledArray[randomIndex] = tempValue;
		}
		return [...shuffledArray]; // Return a new shuffled array
	};

	const getOneFromShuffled = () => {
		// flush shuffledList if necessary
		if (currentShuffleList.length === 0) {
			do {
				currentShuffleList.splice(0);
				currentShuffleList.push(...shuffle());
			} while (currentShuffleList[currentShuffleList.length - 1] === lastChioce);
		}

		return currentShuffleList.pop();
	};

	return getOneFromShuffled;
};

hexo.on("generateBefore", () => {
	const {
		cover: { default_cover: defaultCover },
	} = hexo.theme.config;

	if (!defaultCover) {
		randomCoverFn = () => false;
		return;
	}
	if (!Array.isArray(defaultCover)) {
		randomCoverFn = () => defaultCover;
		return;
	}

	randomCoverFn = createShuffleClosure(defaultCover);
});

这种算法完美解决了上述问题

Posted on In

问题

Link

设计一个算法收集某些股票的每日报价，并返回该股票当日价格的跨度 。

当日股票价格的跨度被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。

例如，如果未来 7 天股票的价格是 [100,80,60,70,60,75,85]，那么股票跨度将是 [1,1,1,2,1,4,6] 。

实现 StockSpanner 类：

StockSpanner() 初始化类对象。

int next(int price) 给出今天的股价 price ，返回该股票当日价格的 跨度 。

难度：一般

思路

  1. 一维数组的第一个小于/大于问题应该用单调栈解法；
  2. 定义一个递减单调栈，每个元素是索引与price的二元组；
  3. 每次返回栈顶元素与该元素索引差。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var StockSpanner = function () {
	this.stack = [[-1, Number.MAX_VALUE]];
	this.index = -1;
};

/**
 * @param {number} price
 * @return {number}
 */
StockSpanner.prototype.next = function (price) {
	this.index++;
	while (this.stack.slice(-1)[0][1] <= price) {
		this.stack.pop();
	}
	let res = this.index - this.stack.slice(-1)[0][0];
	this.stack.push([this.index, price]);
	return res;
};

/**
 * Your StockSpanner object will be instantiated and called as such:
 * var obj = new StockSpanner()
 * var param_1 = obj.next(price)
 */

Posted on In

问题

Link

给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

难度：一般

思路

  • 使用动态规划思想解题

  • 定义状态：dp[i][0]表示第i天手上没有股票的利润，dp[i][1]表示第i天手上有股票的利润

  • 状态转移方程与初始状态：

    1
    2
    3
    4
    dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);
    dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
    dp[0][0] = 0;
    dp[0][1] = -price[0];

  • 每天的状态只和前一天有关，无需存储整个数组，所以状态转移方程为：

    1
    2
    buy = max(buy, sell - prices[i]);
    sell = max(sell, buy + prices[i] - fee);

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * @param {number[]} prices
 * @param {number} fee
 * @return {number}
 */
var maxProfit = function (prices, fee) {
	let buy = -prices[0],
		sell = 0;
	for (let i = 1; i < prices.length; i++) {
		sell = Math.max(sell, buy + prices[i] - fee);
		buy = Math.max(buy, sell - prices[i]);
	}
	return sell;
};

其他题解

暴力算法

  1. 计算出所有[上坡-fee]，相加。

Posted on In

问题

Link

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

难度：困难

思路

  • 题目限定了只能进行两笔交易，显然贪心算法这种方法不考虑交易不行
  • 使用动态规划解法，定义状态dp[i]代表第i天结束时手里的钱数
  • 定义状态sell1,buy1,sell2,buy2代表买了一次，买卖一次，买卖一次+买了二次，买买二次
  • 每天的状态只和前一天有关，无需存储整个数组，所以状态转移方程为：
    1
    2
    3
    4
    buy1 = max(buy1, -prices[i]);
    sell1 = max(sell1, buy1 + prices[i]);
    buy2 = max(buy2, sell1 - prices[i]);
    sell2 = max(sell2, buy2 + prices[i]);
  • 接下来考虑初始状态，第0天如果手里买进了，就是-prices[0]，没有就是0。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
	let buy1 = -prices[0],
		buy2 = -prices[0],
		sell1 = 0,
		sell2 = 0;
	for (let i = 0; i < prices.length; i++) {
		buy1 = Math.max(buy1, -prices[i]);
		sell1 = Math.max(sell1, buy1 + prices[i]);
		buy2 = Math.max(buy2, sell1 - prices[i]);
		sell2 = Math.max(sell2, buy2 + prices[i]);
	}
	return sell2;
};

其他题解

暴力算法

  1. 计算出所有上坡，排序
  2. 选择落差最大的两个，相加。

Posted on In

问题

Link

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

思路

题目没说不可以同一天卖了又买。所以贪心算法，将折线图中所有上坡都收集到，就是最大利润。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
	let ans = 0;
	for (let i = 1; i < prices.length; i++) {
		let profit = prices[i] - prices[i - 1];
		if (profit > 0) {
			ans += profit;
		}
	}
	return ans;
};

官方题解

动态规划法

  1. dp[i][j]表示第i天手里有无股票(j=0无股票，1有股票)
  2. dp[i][0]=max{dp[i−1][0],dp[i−1][1]+prices[i]}
  3. dp[i][1]=max{dp[i−1][1],dp[i−1][0]−prices[i]}

代码

1
2
3
4
5
6
7
8
9
10
var maxProfit = function (prices) {
	const n = prices.length;
	const dp = new Array(n).fill(0).map((v) => new Array(2).fill(0));
	((dp[0][0] = 0), (dp[0][1] = -prices[0]));
	for (let i = 1; i < n; ++i) {
		dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
		dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
	}
	return dp[n - 1][0];
};

觉得有点简单问题复杂化了

Posted on In

问题

Link

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。

思路

  1. 子问题是节点k的左右节点的最大收获。
  2. 我们可以用f(o)表示选择o节点的情况下，o节点的子树上被选择的节点的最大权值和；g(o)表示不选择o节点的情况下，o节点的子树上被选择的节点的最大权值和；
  3. 当o被选中时，左右节点不能选中，也就是f(o)=g(l)+g(r)+o
  4. 当o不选中时，g(o)=max{f(l),g(l)}+max{f(r),g(r)}
  5. 使用深度优先遍历二叉树

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.HashMap;
import java.util.Map;

class Solution {
	Map<TreeNode, Integer> f = new HashMap<TreeNode, Integer>();
	Map<TreeNode, Integer> g = new HashMap<TreeNode, Integer>();

	public int rob(TreeNode root) {
		dfs(root);
		return Math.max(f.getOrDefault(root, 0), g.getOrDefault(root, 0));
	}

	public void dfs(TreeNode node) {
		if (node == null) {
			return;
		}
		dfs(node.left);
		dfs(node.right);
		f.put(node, node.val + g.getOrDefault(node.left, 0) + g.getOrDefault(node.right, 0));
		g.put(node,
				Math.max(f.getOrDefault(node.left, 0), g.getOrDefault(node.left, 0)) +
						Math.max(f.getOrDefault(node.right, 0), g.getOrDefault(node.right, 0)));
	}
}

优化

  1. 空间优化：在dfs时将f(x)和g(x)的值全都返回给上一级，可以省去哈希表空间。