1. 题目列表
- 除数博弈(一维简单动态规划）
- 节点与其祖先之间的最大差值（DFS，求最大差值）
- 最长等差数列（二维动态规划，理解状态转移）
- 从先序遍历还原二叉树（DFS建树，待学习）
2. 除数博弈
当前输赢状态i由前面i-1个状态所决定。
状态转移方程：
dp[i] = true, if i % j == 0 && dp[i - j] == fasle, j = 1, 2, ..., i - 1
dp[i] = false, else
代码：
class Solution {
public:
bool divisorGame(int N) {
bool win[N + 10];
win[1] = false, win[2] = true;
for (int i = 3; i <= N; i++){
int j;
for (j = 1; j < i; j++){
if (i % j == 0 && !win[i - j]){
win[i] = true;
break;
}
}
if (j == i)
win[i] = false;
}
return win[N];
}
};
3. 节点与其祖先之间的最大差值
求二叉树连通边上的最大差值。最佳方案是维护DFS中的最大值和最小值，到达边界时计算一次最大差值。（我的方法比较烦了...记录DFS路径，计算路径上的差值，其实一个道理。）
代码：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> path, vals;
int MAX = 0;
int maxAncestorDiff(TreeNode* root) {
path.clear();
MAX = 0;
path.push_back(root -> val);
DFS(root);
return MAX;
}
void DFS(TreeNode* root){
if (root -> left == NULL && root -> right == NULL){
vals = path; // 注意不能sort(path)，path在DFS不能被sort
sort(vals.begin(), vals.end());
int sub = vals[vals.size() - 1] - vals[0];
if (sub > MAX){
MAX = sub;
}
return ;
}
if (root -> left){
path.push_back(root -> left -> val);
DFS(root -> left);
path.pop_back();
}
if (root -> right){
path.push_back(root -> right -> val);
DFS(root -> right);
path.pop_back();
}
}
};
4. 最长等差数列
二维dp题：（关键理解状态转移的过程）
定义dp[i][j]表示以i为结尾的公差为j的最大等差序列长度。
则状态转移方程：
dp[i][A[i] - A[j]] = max(dp[i][A[i] - A[j]], dp[j][A[i] - A[j]] + 1), j=0,1,2,...,i-1
根据等差数列的性质，以A[i]结尾的公差为A[i] - A[j]的状态依赖于以A[j]结尾公差也为A[i] - A[j]的状态。
初始dp数组所有可能的公差长度为1。
注意: 此处的公差可能为负值，因此可以偏移数组的第二维，或者使用vector<map>结构表示二维数组
代码：
class Solution {
public:
int longestArithSeqLength(vector<int>& A) {
vector< map<int, int> > dp(A.size());
for (int i = 0; i < A.size(); i++){
for (int j = i + 1; j < A.size(); j++){
dp[i][A[j] - A[i]] = 1; // 公差计算：后面减前面的
}
}
int MAX = 1;
for (int i = 1; i < A.size(); i++){
for (int j = 0; j < i; j++){
// 注意：公差的计算是后面的减前面的，因此是A[i]-A[j]
dp[i][A[i] - A[j]] = max(dp[i][A[i] - A[j]], dp[j][A[i] - A[j]] + 1);
MAX = max(dp[i][A[i] - A[j]], MAX);
}
}
return MAX;
}
};
5. 从先序遍历还原二叉树（复习二叉树的重构）
复杂的二叉树DFS重构。该题是给定二叉树的先序序列 + 节点的深度，并且规定了左节点优先，因此保证了重构二叉树的唯一性。
此外，也要复习二叉树的先序 + 中序、后序 + 中序重构。
代码：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int pos = 0; //记录当前遍历到的位置，总指针
string T;
inline int read_val(int p) {
int x = 0;
for (; p < T.length() && isdigit(T[p]); ++ p)
x = (x * 10) + (T[p] - '0');
return x;
}
TreeNode* Dfs(int dep) {
int cur = 0; //记录 '-' 的个数，表示下一个节点的深度
for (int j = pos; j < T.length() && T[j] == '-'; ++ j) ++ cur;
if (cur != dep) return NULL;
pos += cur;
TreeNode *u = new TreeNode(read_val(pos));
while (pos < T.length() - 1 && isdigit(T[pos])) ++ pos; //跳过第一个数字后面的数字，在函数里已经计算过了
u -> left = Dfs(dep + 1);
u -> right = Dfs(dep + 1);
return u;
}
TreeNode* recoverFromPreorder(string S) {
T = S; return Dfs(0);
}
};
