Joyce' Blog
0%

发表于

题目描述

给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：

  1. 每次转换只能改变一个字母。

  2. 转换过程中的中间单词必须是字典中的单词。

说明:

  1. 如果不存在这样的转换序列，返回 0。
  2. 所有单词具有相同的长度。
  3. 所有单词只由小写字母组成。
  4. 字典中不存在重复的单词。
  5. 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。

题解

无向无权图中，每个单词作为节点，差距只有一个字母的两个单词之间连一条边。问题变成找到从起点到终点的最短路径，如果存在的话。因此可以使用广度优先搜索方法。

为了快速的找到这些相邻节点，我们对给定的 wordList 做一个预处理，将单词中的某个字母用 * 代替。这步预处理找出了单词表中所有单词改变某个字母后的通用状态，更方便也更快的找到相邻节点。否则，对于每个单词我们需要遍历整个字母表查看是否存在一个单词与它相差一个字母，这将花费很多时间。预处理操作在广度优先搜索之前高效的建立了邻接表。

如果使用两个同时进行的广搜可以有效地减少搜索空间。一边从 beginWord 开始，另一边从 endWord 开始。我们每次从两边各扩展一个节点，当发现某一时刻两边都访问了某一顶点时就停止搜索。这就是双向广度优先搜索，它可以可观地减少搜索空间大小，从而降低时间和空间复杂度。

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
class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {

        unordered_set<string> dict(wordList.begin(), wordList.end());
        if (dict.find(endWord) == dict.end() ) return 0;
        // 初始化起始和终点
        unordered_set<string> beginSet, endSet, tmp, visited;
        beginSet.insert(beginWord);
        endSet.insert(endWord);
        int len = 1;

        while (!beginSet.empty() && !endSet.empty()){
            if (beginSet.size() > endSet.size()){
                tmp = beginSet;
                beginSet = endSet;
                endSet = tmp;
            }
            tmp.clear();
            for ( string word : beginSet){
                for (int i = 0; i < word.size(); i++){
                    char old = word[i];
                    for ( char c = 'a'; c <= 'z'; c++){
                        if ( old == c) continue;
                        word[i] = c;
                        if (endSet.find(word) != endSet.end()){
                            return len+1;
                        }
                        if (visited.find(word) == visited.end() && dict.find(word) != dict.end()){
                            tmp.insert(word);
                            visited.insert(word);
                        }
                    }
                    word[i] = old;
                }
            }
            beginSet = tmp;
            len++;
            

        }
        return 0;
    }
};


作者：xu-zhou-geng
链接：https://leetcode-cn.com/problems/word-ladder/solution/cpp-yi-ge-si-lu-de-zhuan-bian-cong-1156msjia-su-da/

发表于

题目描述

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

题解

一个丑陋的版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int singleNumber(vector<int>& nums) {
	int vsize = nums.size();
	map<int, bool>m;
	for (int i = 0; i < vsize; i++)
	{
		if (m.count(nums[i]))
		{
			m.erase(nums[i]);
		}
		else
			m[nums[i]] = false;
	}
	return (*m.begin()).first;
}

改进

数学公式：2∗(a+b+c)−(a+a+b+b+c)=c

1
2
3
4
int singleNumber(vector<int>& nums) {
	set<int>st(nums.begin(), nums.end());
	return 2 * accumulate(st.begin(),st.end(),0) - accumulate(nums.begin(), nums.end(), 0);
}

异或位操作才是最强的：对 0 和二进制位做 XOR 运算，得到的仍然是这个二进制位；对相同的二进制位做 XOR 运算，返回的结果是 0。XOR 满足交换律和结合律。将所有的数进行 XOR 操作，得到那个唯一的数字。

1
2
3
4
5
6
int singleNumber(vector<int>& nums) {
	int res = 0;
	for (int i = 0; i<nums.size(); i++)
		res ^= nums[i];
	return res;
}

挺自闭的，找个简单题 写了早早睡吧。

发表于

如果真的有人进到这个博客，然后点开这篇文章，并且是我的学弟学妹的话，qq大概率是不会给的，但是下面的留言区是开放的。

另外关于晚自习的考试，我和校长反映了，校长说我们当时也是这么过来的，emm…这我就记不清了……不过第二阶段会累一点，第三阶段就不会占用晚自习了。

还有认真刷题，别走捷径，“水一水”这话就当是开玩笑。不然校长知道了可能以后就不让我进高中了。

发表于 更新于

题目描述

给定两个单词（beginWord 和 endWord）和一个字典 wordList，找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则：

  1. 每次转换只能改变一个字母。

  2. 转换过程中的中间单词必须是字典中的单词。

说明:

  • 如果不存在这样的转换序列，返回一个空列表。

  • 所有单词具有相同的长度。

  • 所有单词只由小写字母组成。
  • 字典中不存在重复的单词。
  • 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。

题解

想法：转化为图，单词做为顶点，相差一个字母的两个单词之间连一条边，问题转化为：求两个点之间所有的最短路径。

原始的Dijkstra算法得到的是从源点到其他点的一条最短路径，即 一颗最短路径树。在这里，对Dijkstra算法进行修正，得到一个最短路径图，使得从源点到指定点的人一两条路径都具有相同的距离。基于最短路径图，应用Yin算法罗列从源点到指定点的所有最短路径。

修正后的Dijkstra算法

$T$表示从源点$v_1$到$v$的最短路径的上限，记为$T(v)$，$P$表示从原点$v_1$到这一点的最短路径，集合$S$表示所有具有$P$的点的集合。函数$\lambda(v)$表示路径$R$中点$v$的上一个点。

  1. 初始化：$T(v_1)=0，\mu(y,x)=0，R={v_1}，S=\phi$
  2. 在集合$R$中选取具有最小$T$标号的点$y$，则：$S=S\bigcup{y}, R=R-{y}$；若边$(y,x)\in E$且$x\notin S$，则$R=R\bigcup{x}$
  3. 若边$(y,x)\in E$，则：若$T(y)+w(y,x)<T(x)$，则$T(x)=T(y)+w(y,x), \mu(y,x)=1$，同时若$\mu(z,x)=1$且$z\neq y$，则$ \mu(z,x)=0$；若$T(y)+w(y,x) = T(x)$，则$\mu(y,x)=1$。
  4. 如果所有点进入集合$S$，那么算法停止，把所有$\mu(y,x)=0$的边从图$G(V,E)$中删去，得到的新图就是最短路径图。否则，转到step2.

算法思想：根据各最短路径中边的数目对各最短路径进行排序，变数越少的最短路径对应的级别就越高，算法按照由高到低的顺序依次列出所有的最短路径。在这道题中，各边的权均为1，那么从源点到指定点的路径长度越短，该路径的级别就越高，按照级别由高到低依次列出所有的最短路径，可以借助于求第$k$条最短路径问题的Yen算法来解决。

Yen算法的思想是,首先求得从源点到指定点的第1,2,…,k-1条最短路径,然后在这k-1条最短路径的基础上求得第k条最短路径.由于在最短路径图中,从源点到指定点的最短路径是有限的,因而当k足够大时,按照Yen算法总可以求得从源点到指定点的所有最短路径.

test

参考文献
https://wenku.baidu.com/view/0254244b001ca300a6c30c22590102020740f2d8.html
王志坚，韩伟一，李一军. 具有多条最短路径的最短路问题[J]. 哈尔滨工业大学学报，2010，42（9）：1429-1431.

Anyway, wrong again. Debug tomorrow and learn parallel slide.

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
#define INF 200000000
#define N 1000

struct Edge
{
	int to;          // 边终止节点
	int cost;        // 花费

	Edge(int to1, int cost1)
	{
		to = to1;
		cost = cost1;
	}
};

int nV;                      // 顶点数
vector<Edge> G[N];           // 图的邻接表形式
int dist[N];                 // 从源点出发的最短距离
typedef pair<int, int> P;    // first是最短距离，second是顶点编号
bool vis[N];
vector<Edge> G4[N];
int G1[N][N];                // 图的邻接矩阵形式

void addEdge(int from, int to, int cost, vector<Edge> G[N])
{
	Edge e(to, cost);
	G[from].push_back(e);

	Edge e1(from, cost);
	G[to].push_back(e1);
}

void dijkstra(int s, vector<Edge> G[N])
{
	fill(dist, dist + nV + 1, INF);
	priority_queue<P, vector<P>, greater<P> > q;
	dist[s] = 0;
	q.push(P(0, s));
	while (!q.empty())
	{
		P p = q.top();   //从尚未使用的顶点中找到一个距离最小的顶点
		q.pop();
		int v = p.second;
		if (dist[v] < p.first)
			continue;
		for (int i = 0; i<G[v].size(); i++)
		{
			Edge &e = G[v][i];
			int dis = dist[v] + e.cost;
			if (dist[e.to] > dis)
			{
				dist[e.to] = dist[v] + e.cost;
				q.push(P(dist[e.to], e.to));
				G4[v].push_back(e);
			}
			else if (dist[e.to] == dis)
			{
				G4[v].push_back(e);
			}
		}
	}
}

struct Ans
{
	vector<int> link;
	int cost;
	int start;

	void getCost()
	{
		cost = G1[start][link[0]];
		for (int i = 0; i<link.size() - 1; i++)
		{
			cost += G1[link[i]][link[i + 1]];
		}
	}
};

void dfs(int s, int t, Ans &A, vector< Ans > &paths, int start)
{
	if (s == t)
	{
		A.start = start;
		A.getCost();
		paths.push_back(A);
	}

	for (int i = 0; i < G4[s].size(); i++)
	{
		int u = G4[s][i].to;
		if (!vis[u])
		{
			vis[u] = true;
			A.link.push_back(u);
			dfs(u, t, A, paths, start);
			A.link.pop_back();
			vis[u] = false;
		}
	}
}

bool neighbour(string s1, string s2)
{
	bool flag = true;
	int i = 0;
	//所有单词具有相同的长度
	while (i < s1.length())
	{
		if (s1[i] != s2[i])
		{
			if (flag)
				flag = false;
			else
				return false;
		}
		i++;
	}
	return true;
}
vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) 
{
	//beginWord 和 endWord 是非空的，且二者不相同
	int source = 0;
	int vsize = wordList.size();
	for (; source < vsize; source++)
	{
		if (wordList[source] == beginWord)break;
	}
	if (source == vsize)
	{
		wordList.push_back(beginWord);
		vsize++;
	}
	
	int destination = 0;
	for (; destination < vsize; destination++)
	{
		if (wordList[destination] == endWord)break;
	}
	if (destination == vsize)return {};
	nV = vsize;

	//这里假设beginWord 和 endWord不在wordList中	

	//build graph
	for (int i = 0; i<vsize; i++)
	{
		for (int j = i; j<vsize; j++)
		{
			G1[i][j] = G1[j][i] = INF;
		}
	}
	for (int i = 0; i < vsize; i++)
	{
		for (int j = i + 1; j < vsize; j++)
		{
			if (neighbour(wordList[i], wordList[j]))
			{
				addEdge(i, j, 1, G);
				G1[i][j] = G1[j][i] = 1;
			}
		}
	}
	
	//get new graph
	dijkstra(source, G);

	//Yen算法
	vector<vector<string>> res;
	vector<Ans> paths;
	Ans ans;
	memset(vis, false, sizeof(vis));
	dfs(source, destination, ans, paths, 1);

	for (int i = 0; i<paths.size(); i++)
	{
		vector<string> tmp = { beginWord };
		for (int j = 0; j<paths[i].link.size(); j++)
		{
			tmp.push_back(wordList[paths[i].link[j]]);
		}
		res.push_back(tmp);
	}
	return res;
}
int singleNumber(vector<int>& nums) {
	int res = 0;
	for (int i = 0; i<nums.size(); i++)
		res ^= nums[i];
	return res;
}
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
	unordered_set<string> dict(wordList.begin(), wordList.end());
	if (dict.find(endWord) == dict.end()) return 0;
	// 初始化起始和终点
	unordered_set<string> beginSet, endSet, tmp, visited;
	beginSet.insert(beginWord);
	endSet.insert(endWord);
	int len = 1;

	while (!beginSet.empty() && !endSet.empty()) {
		if (beginSet.size() > endSet.size()) {
			tmp = beginSet;
			beginSet = endSet;
			endSet = tmp;
		}
		tmp.clear();
		for (string word : beginSet) {
			for (int i = 0; i < word.size(); i++) {
				char old = word[i];
				for (char c = 'a'; c <= 'z'; c++) {
					if (old == c) continue;
					word[i] = c;
					if (endSet.find(word) != endSet.end()) {
						return len + 1;
					}
					if (visited.find(word) == visited.end() && dict.find(word) != dict.end()) {
						tmp.insert(word);
						visited.insert(word);
					}
				}
				word[i] = old;
			}
		}
		beginSet = tmp;
		len++;
	}
	return 0;
}

这就很过分了，vs和leetcode里面运行出来的结果居然不一样。

大佬的看着就很简洁。使用标准的BFS遍历，将已经访问过的单词加入待删除集合dels中，不要立即删除。因为在同一层遍历时，有可能有多种路径，即多个解。这是与127的区别之一。
使用trace记住当前单词的前驱，注意前驱有多个（即有可能多个解），然后使用dfs恢复路径。

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
// Time 156ms, Space 22MB
class Solution {
	void dfs(unordered_map<string,unordered_set<string> > &trace, const string &last, vector<string> path, vector<vector<string> > &vs){
		path.push_back(last);
		if(trace.count(last)==0){
			reverse(path.begin(),path.end());
			vs.push_back(path);
			return;
		}
		for(const string &word:trace[last])
			dfs(trace,word,path,vs);
	}
public:
	vector<vector<string>> findLadders(string begin, string end, vector<string>& wordList) {
		unordered_set<string> dict(wordList.begin(),wordList.end());
		if (dict.count(end)==0) return {};
		unordered_map<string,unordered_set<string> > trace;
		unordered_set<string> q={begin}, dels;
		for(; q.size() && trace.count(end)==0; q=dels){
			for(const string &word:q)
				dict.erase(word);
			dels.clear();
			for(const string &word:q){
				for(int i=0; i<word.length(); ++i){
					string s=word;
					for(char ch='a'; ch<='z'; ++ch){
						if(word[i]==ch) continue;
						s[i] = ch;
						if(dict.find(s)==dict.end()) continue;
						trace[s].insert(word);
						dels.insert(s);
					}
				}
			}
		}
		if(trace.size()==0) return {};
		vector<vector<string> > result;
		dfs(trace,end,{},result);
		return result;
	}
};

作者：joy-teng
链接：https://leetcode-cn.com/problems/word-ladder-ii/solution/bfsdfs-by-joy-teng/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

发表于

题目描述

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明：本题中，我们将空字符串定义为有效的回文串。

题解

头文件：#include <ctype.h>

isalnum() 用来判断一个字符是否为英文字母或数字，相当于 isalpha(c) || isdigit(c)，其原型为： 

1
int isalnum(char c);

c 为需要检测的字符。若 c 为 0 ~ 9 a ~ z A ~ Z 则返回非 0，否则返回 0。isalnum()为宏定义，不是真正的函数。

C++ STL string 大小写转换：

1
2
3
string str = "abcdADcdeFDde!@234";
transform(str.begin(), str.end(), str.begin(), ::toupper);
transform(str.begin(), str.end(), str.begin(), ::tolower);
1
2
3
4
5
6
7
8
9
10
11
12
13
bool isPalindrome(string s) {
	bool res = true;
	int i = 0, j = s.length() - 1;
	transform(s.begin(), s.end(), s.begin(), ::toupper);
	while (i < j)
	{
		while (i<j&&!isalnum(s[i]))i++;
		while (i<j&&!isalnum(s[j]))j--;
		if (s[i] != s[j])return false;
		i++; j--;
	}
	return res;
}

发表于 更新于

题目描述

给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

题解

自底向上？后序遍历？太卑微了，最终还是点开了答案。

使用 val 来记录全局最大路径和。lmr表示路径：left->middle->right，return表示路径：由左/右子树经过当前节点向上走。

1
2
3
4
5
6
7
8
9
10
11
12
13
int hmax(TreeNode* root, int &val) {
	if (root == nullptr)return 0;
	int left = max(hmax(root->left, val),0);
	int right = max(hmax(root->right, val),0);
	int lmr = root->val + left + right;
	val = max(val,lmr);
	return root->val + max(left, right);
}
int maxPathSum(TreeNode* root) {
	int val = INT_MIN;
	int k= hmax(root, val);
	return max(k, val);
}

发表于

题目描述

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。注意：你不能在买入股票前卖出股票。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int maxProfit(vector<int>& prices) {
	int t1 = 0, t2 = 1;
	int vsize = prices.size();
	if (vsize <=1||(vsize==1&&prices[1]<prices[0]))return 0;
	int pro = prices[1] - prices[0];
	while (t2 < vsize)
	{
		if (prices[t2] > prices[t2 - 1])
		{
			for (int i = t1; i < t2; i++)
			{
				if (prices[t2] - prices[i] > pro)
				{
					t1 = i;
					pro = prices[t2] - prices[i];
				}
			}
		}
		t2++;
	}
	return pro;
}

题目描述

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

题解

既然可以买多次，那就把赚钱的时候都加起来就行了。

1
2
3
4
5
6
7
8
9
10
11
int maxProfit(vector<int>& prices) {
	int vsize = prices.size();
	if (vsize <= 1)return 0;
	int pro = 0;
	for (int i = 1; i < vsize; i++)
	{
		if (prices[i] - prices[i - 1]>0)
			pro += prices[i] - prices[i - 1];
	}
	return pro;
}

==题目描述==

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

==题解==

链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/solution/yi-ge-tong-yong-fang-fa-tuan-mie-6-dao-gu-piao-wen/

6 道股票买卖问题是有共性的，我们通过对第四题（限制最大交易次数为 k）的分析一道一道解决。因为第四题是一个最泛化的形式，其他的问题都是这个形式的简化。

第一题是只进行一次交易，相当于 k = 1；第二题是不限交易次数，相当于 k = +infinity（正无穷）；第三题是只进行 2 次交易，相当于 k = 2；剩下两道也是不限次数，但是加了交易「冷冻期」和「手续费」的额外条件，其实就是第二题的变种，都很容易处理。

利用「状态」进行穷举

具体到每一天，看看总共有几种可能的「状态」，再找出每个「状态」对应的「选择」。我们要穷举所有「状态」，穷举的目的是根据对应的「选择」更新状态。

1
2
3
4
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 择优(选择1，选择2...)

每天都有三种「选择」：买入、卖出、无操作，用 buy, sell, rest 表示这三种选择。 sell 必须在 buy 之后，那么 rest 操作还应该分两种状态，一种是 buy 之后的 rest（持有了股票），一种是 sell 之后的 rest（没有持有股票）。还有交易次数 k 的限制， buy 还只能在 k > 0 的前提下操作。

这个问题的「状态」有三个，第一个是天数，第二个是允许交易的最大次数，第三个是当前的持有状态（即之前说的 rest 的状态，我们不妨用 1 表示持有，0 表示没有持有）。然后我们用一个三维数组就可以装下这几种状态的全部组合：

1
2
3
4
5
6
7
8
9
dp[i][k][0 or 1]
0 <= i <= n-1, 1 <= k <= K
n 为天数，大 K 为最多交易数
此问题共 n × K × 2 种状态，全部穷举就能搞定。

for 0 <= i < n:
    for 1 <= k <= K:
        for s in {0, 1}:
            dp[i][k][s] = max(buy, sell, rest)

比如说 dp[3][2][1] 的含义就是：今天是第三天，我现在手上持有着股票，至今最多进行 2 次交易。再比如 dp[2][3][0] 的含义：今天是第二天，我现在手上没有持有股票，至今最多进行 3 次交易。

我们想求的最终答案是 dp[n - 1][K][0]，即最后一天，最多允许 K 次交易，最多获得多少利润。

状态转移图

状态转移方程：

1
2
3
4
5
6
7
8
9
10
11
12
13
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
              max(   选择 rest  ,           选择 sell      )

解释：今天我没有持有股票，有两种可能：
要么是我昨天就没有持有，然后今天选择 rest，所以我今天还是没有持有；
要么是我昨天持有股票，但是今天我 sell 了，所以我今天没有持有股票了。

dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
              max(   选择 rest  ,           选择 buy         )

解释：今天我持有着股票，有两种可能：
要么我昨天就持有着股票，然后今天选择 rest，所以我今天还持有着股票；
要么我昨天本没有持有，但今天我选择 buy，所以今天我就持有股票了。

注意 k 的限制，我们在选择 buy 的时候，把 k 减小了 1，很好理解吧，当然你也可以在 sell 的时候减 1，一样的。

定义 base case

1
2
3
4
5
6
7
8
dp[-1][k][0] = 0
解释：因为 i 是从 0 开始的，所以 i = -1 意味着还没有开始，这时候的利润当然是 0 。
dp[-1][k][1] = -infinity
解释：还没开始的时候，是不可能持有股票的，用负无穷表示这种不可能。
dp[i][0][0] = 0
解释：因为 k 是从 1 开始的，所以 k = 0 意味着根本不允许交易，这时候利润当然是 0 。
dp[i][0][1] = -infinity
解释：不允许交易的情况下，是不可能持有股票的，用负无穷表示这种不可能。

新状态只和相邻的一个状态有关，其实不用整个 dp 数组，只需要一个变量储存相邻的那个状态就足够了，这样可以把空间复杂度降到 O(1):

具体实现

第一题，k = 1

1
2
3
4
5
6
7
8
9
dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + prices[i])
dp[i][1][1] = max(dp[i-1][1][1], dp[i-1][0][0] - prices[i]) 
            = max(dp[i-1][1][1], -prices[i])
解释：k = 0 的 base case，所以 dp[i-1][0][0] = 0。

现在发现 k 都是 1，不会改变，即 k 对状态转移已经没有影响了。
可以进行进一步化简去掉所有 k：
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], -prices[i])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
for (int i = 0; i < n; i++) {
    if (i - 1 == -1) {
        dp[i][0] = 0;
        // 解释：
        //   dp[i][0] 
        // = max(dp[-1][0], dp[-1][1] + prices[i])
        // = max(0, -infinity + prices[i]) = 0
        dp[i][1] = -prices[i];
        //解释：
        //   dp[i][1] 
        // = max(dp[-1][1], dp[-1][0] - prices[i])
        // = max(-infinity, 0 - prices[i]) 
        // = -prices[i]
        continue;
    }
    dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
    dp[i][1] = Math.max(dp[i-1][1], -prices[i]);
}
return dp[n - 1][0];

空间优化：

1
2
3
4
5
6
7
8
9
10
11
12
13
// k == 1
int maxProfit_k_1(int[] prices) {
    int n = prices.length;
    // base case: dp[-1][0] = 0, dp[-1][1] = -infinity
    int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
    for (int i = 0; i < n; i++) {
        // dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
        dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
        // dp[i][1] = max(dp[i-1][1], -prices[i])
        dp_i_1 = Math.max(dp_i_1, -prices[i]);
    }
    return dp_i_0;
}

第二题，k = +infinity

如果 k 为正无穷，那么就可以认为 k 和 k - 1 是一样的。数组中的 k 已经不会改变了，也就是说不需要记录 k 这个状态了

1
2
3
4
5
6
7
8
9
10
int maxProfit_k_inf(int[] prices) {
    int n = prices.length;
    int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
    for (int i = 0; i < n; i++) {
        int temp = dp_i_0;
        dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
        dp_i_1 = Math.max(dp_i_1, temp - prices[i]);
    }
    return dp_i_0;
}

第三题，k = +infinity with cooldown

每次 sell 之后要等一天才能继续交易。只要把这个特点融入上一题的状态转移方程即可：

1
2
3
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i])
解释：第 i 天选择 buy 的时候，要从 i-2 的状态转移，而不是 i-1 。
1
2
3
4
5
6
7
8
9
10
11
12
int maxProfit_with_cool(int[] prices) {
    int n = prices.length;
    int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
    int dp_pre_0 = 0; // 代表 dp[i-2][0]
    for (int i = 0; i < n; i++) {
        int temp = dp_i_0;
        dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
        dp_i_1 = Math.max(dp_i_1, dp_pre_0 - prices[i]);
        dp_pre_0 = temp;
    }
    return dp_i_0;
}

第四题，k = +infinity with fee

每次交易要支付手续费，只要把手续费从利润中减去即可。改写方程：

1
2
3
4
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i] - fee)
解释：相当于买入股票的价格升高了。
在第一个式子里减也是一样的，相当于卖出股票的价格减小了。
1
2
3
4
5
6
7
8
9
10
int maxProfit_with_fee(int[] prices, int fee) {
    int n = prices.length;
    int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
    for (int i = 0; i < n; i++) {
        int temp = dp_i_0;
        dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
        dp_i_1 = Math.max(dp_i_1, temp - prices[i] - fee);
    }
    return dp_i_0;
}

第五题，k = 2

1
2
3
原始的动态转移方程，没有可化简的地方
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])

必须要对 k 进行穷举：

1
2
3
4
5
6
7
8
9
10
11
int max_k = 2;
int[][][] dp = new int[n][max_k + 1][2];
for (int i = 0; i < n; i++) {
    for (int k = max_k; k >= 1; k--) {
        if (i - 1 == -1) { /*处理 base case */ }
        dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]);
        dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]);
    }
}
// 穷举了 n × max_k × 2 个状态，正确。
return dp[n - 1][max_k][0];

这里 k 取值范围比较小，所以可以不用 for 循环，直接把 k = 1 和 2 的情况手动列举出来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
dp[i][2][0] = max(dp[i-1][2][0], dp[i-1][2][1] + prices[i])
dp[i][2][1] = max(dp[i-1][2][1], dp[i-1][1][0] - prices[i])
dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + prices[i])
dp[i][1][1] = max(dp[i-1][1][1], -prices[i])

int maxProfit_k_2(int[] prices) {
    int dp_i10 = 0, dp_i11 = Integer.MIN_VALUE;
    int dp_i20 = 0, dp_i21 = Integer.MIN_VALUE;
    for (int price : prices) {
        dp_i20 = Math.max(dp_i20, dp_i21 + price);
        dp_i21 = Math.max(dp_i21, dp_i10 - price);
        dp_i10 = Math.max(dp_i10, dp_i11 + price);
        dp_i11 = Math.max(dp_i11, -price);
    }
    return dp_i20;
}

第六题，k = any integer

有了上一题 k = 2 的铺垫，这题应该和上一题的第一个解法没啥区别。但是出现了一个超内存的错误，原来是传入的 k 值会非常大，dp 数组太大了。一次交易由买入和卖出构成，至少需要两天。所以说有效的限制 k 应该不超过 n/2，如果超过，就没有约束作用了，相当于 k = +infinity。这种情况是之前解决过的。

自此，跟股票划清界限了。

发表于 更新于

题目描述

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

说明：

如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。

题解

自底向上动态规划，类似于求最短路径。↙或者↘方向两种选择

居然有直接在triangle上操作的！不过确实省了不少事。

1
2
3
4
5
6
7
8
int minimumTotal(vector<vector<int>>& triangle) {
	int high = triangle.size();
	if (!high)return 0;
	for (int i = high - 2; i >= 0; i--)
		for (int j = 0; j<triangle[i].size(); j++)
			triangle[i][j] += min(triangle[i + 1][j + 1], triangle[i + 1][j]);
	return triangle[0][0];
}

发表于

题目描述

给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。

题解

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
void gen(int numRows, vector<vector<int>>& vec)
{
	if (numRows == 1) 
	{
		vec.push_back({ 1 });
		return;
	}
	else
	{
		gen(numRows - 1, vec);
		vector<int> t = { 1 };
		vector<int> p = vec.back();
		for (int i = 1; i < numRows - 1; i++)
			t.push_back(p[i] + p[i - 1]);
		t.push_back(1);
		vec.push_back(t);
		return;
	}
}
vector<vector<int>> generate(int numRows) {
	vector<vector<int>> res;
	if (!numRows)return res;
	gen(numRows, res);
	return res;
}

题目描述

给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。

进阶：

你可以优化你的算法到 O(k) 空间复杂度吗？

题解

O(k)？观察一下下面的规律就好写了，类似于，优化空间的动态规划的方法。

1
2
3
4
5
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> getRow(int rowIndex) {
	if (rowIndex == 0)return { 1 };
	vector<int> p;
	vector<int> res = { 1 };
	for (int i = 0; i < rowIndex; i++)
		res.push_back(0);
	p = res;
	for (int j = 2; j < rowIndex+2; j++)
	{
		for (int i = 1; i < j; i++)
		{
			res[i] = p[i - 1] + p[i];
		}
		p = res;
	}
	return res;
}

执行用时 :0 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗 :6.5 MB, 在所有 C++ 提交中击败了100.00%的用户

666

发表于

题目描述

给定一个二叉树填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。初始状态下，所有 next 指针都被设置为 NULL。

进阶：

  • 你只能使用常量级额外空间。
  • 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

题解

诶？和之前的题目还不一样了，不能直接算出来什么时候该分层了。那就，只能，递归了呗？（队列依然是可以使用的，以后再说吧）

核心是getNextNoNullChild，根据root，找到下一级右手第一个
然后分情况讨论，对每个节点：
左子右子都有，则左子next指向右子，右子next指向getNextNoNullChild
只有左子，左子指向getNextNoNullChild，
只有右子，右子指向getNextNoNullChild，

注意：递归时要先递归右子树，否则上级节点next关系没建好，下级无法成功getNextNoNullChild

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
Node* getNextNoNullChild(Node* root){
	Node* t = root;
	while (t->next != NULL){
		if (t->next->left!= NULL) {
			return t->next->left;
		}
		if (t->next->right != NULL){
			return t->next->right;
		}
		t = t->next;
	}
	return NULL;
}

Node* connect(Node* root) {
	if (!root||(!root->left&&!root->right))return root;
	if (root->left&&root->right){
		root->left->next = root->right;
		root->right->next = getNextNoNullChild(root);
	}
	else if (!root->right){
		root->left->next = getNextNoNullChild(root);
	}
	else{
		root->right->next = getNextNoNullChild(root);
	}
	//先递归右子树
	//否则右子树根节点next关系没建立好，左子树到右子树子节点无法正确挂载
	root->right = connect(root->right);
	root->left = connect(root->left);
	return root;
}
注意学习递归的顺序！！自顶向下！先右后左！