先上本次contest的链接：
https://leetcode.com/contest/weekly-contest-132/
Divisor Game
本题重在分析。
首先必须明确，
对于一个给定的N，其胜负结果都是确定的
（否则N与比赛结果之间不存在函数关系，这道题也就没有答案了）
由于双方都按最优决策进行操作，必有如下结论：
1. 若初始数字为N时Alice先手必败，则初始数字为N时Bob先手也必败（Alice可以采取相同的策略）。
2. 进一步推出：若初始数字为N（N > 1）时Alice先手必败，则初始数字为N+1时Alice先手必胜（Alice第一步可以取1）
另外，我们注意到奇数的一个非常简单的性质：
奇数的任何因子都是奇数
所以，
当Alice先手面对的是奇数时，不管怎么取，必然取到奇数，而奇数-奇数=偶数，所以留给Bob的一定是一个偶数，此时Bob必然可以通过取1的方法再留给Alice一个奇数
。如此循环往复，Bob总有应对策略，而必然存在某个时刻Alice面对的是那个讨厌的数字——1，此时game over，Alice输掉了。
**至此我们可以得出结论：N为奇数时Alice必败，再由结论2推出，N为偶数时Alice必胜。**分析到这里，这道题就做完了。
代码简单得甚至想笑哈哈哈哈哈。
class Solution {
public:
bool divisorGame(int N) {
return N % 2 == 0;
}
};
Maximum Difference Between Node and Ancestor
解析：
本题相对简单，我用的方法是前序遍历二叉树，用vector记录中间过程，每次遍历记录最大值和最小值，并不断更新差值。记得在递归函数的最后将当前节点的值pop出来。
AC代码：
/**
* 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 max_value = INT_MIN, min_value = INT_MAX;
int maxAncestorDiff(TreeNode* root) {
int res = 0;
vector<int> nodes;
solve(root, res, nodes);
return res;
}
void solve(TreeNode* root, int& res, vector<int>& nodes) {
if (!root)
return;
nodes.push_back(root->val);
max_value = *max_element(nodes.begin(), nodes.end());
min_value = *min_element(nodes.begin(), nodes.end());
res = max(max_value - min_value, res);
solve(root->left, res, nodes);
solve(root->right, res, nodes);
nodes.pop_back();
}
};
Longest Arithmetic Sequence
本题与其说考察是算法，不如说考察的是数据结构。**关键在于如何用一种合理的结构存储中间过程。**一种合理的解法如下：
构造一个二维映射表dp，
dp[diff][index]表示从第一个元素到下标为index的元素所构成的数列中，公差为diff的子序列的最大长度
。
先给出AC代码，各位看官欣赏一哈：
class Solution {
public:
int longestArithSeqLength(vector<int>& A) {
int n = A.size(), res = 2;
map<int, map<int, int>> dp;
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
int a = A[i], b = A[j];
dp[b - a][j] = max(dp[b - a][j], dp[b - a][i] + 1);
res = max(res, dp[b - a][j] + 1);
}
}
return res;
}
};
巧妙之处在于使用了一个二级map，用这种方法实现按值访问，然后再用DP记录最大值即可。不过
这里用unordered_map会更快，因为unordered_map用哈希表实现，而map用的是红黑树实现，元素自动根据键值排序，这也是map最大的优势，其查找复杂度即为红黑树查找复杂度，即O(lgn)。而用哈希表实现的unordered_map查找的复杂度可以达到O(1)，这里我们并不会用到有序性，而是频繁使用查找，因此用unordered_map会是更好的选择。
Recover a Tree From Preorder Traversal
本题是回溯法的典型应用，关键在于如何定义回溯条件，以及如何进行回溯之后的处理。这里我采用了榜单上一个大佬的代码，分析一下其中的妙处。
class Solution {
public:
TreeNode* recoverFromPreorder(string S) {
if (S.empty())
return NULL;
int i = 0, depth = 0;
TreeNode* root = solve(S, i, depth);
return root;
}
TreeNode* solve(const string& S, int& i, int depth) {
int num = 0, countDepth = 0, n = S.size();
while (i < n && S[i] != '-') {
num = num * 10 + (S[i++] - '0');
}
TreeNode* p = new TreeNode(num);
int j = i;
while (j < n && S[j] == '-') { //用j作为指针"试探"下一个节点的深度
countDepth++;
j++;
}
if (countDepth == depth + 1) {
i = j;
p->left = solve(S, i, depth + 1);
//p->left = solve(S, j, depth + 1); //此处不能直接用j作为参数，因为第二个参数是引用，传入j将直接改变j的值
}
countDepth = 0;
j = i;
while (j < n && S[j] == '-') {
countDepth++;
j++;
}
if (countDepth == depth + 1) {
i = j; // i 是遍历字符串的指针，当某个位置需要插入节点时才将i向后移
p->right = solve(S, i, depth + 1);
//p->right = solve(S, j, depth + 1);
}
return p;
}
};
**这里的i和j的作用相当于两个指针，i表示当前读取字符串读到的位置，j用于对下一个节点的深度进行“试探”。**depth参数记录当前深度，countDepth为从字符串解析出来的深度，当且仅当countDepth == depth + 1时进行下一个节点的插入。
对于回溯的处理逻辑：当countDepth != depth + 1时，换到右节点进行判断。**这里的冗余计算是无法避免的，因为你无法保证下一次插入的左子节点和下一次插入的右子节点属于同一层！**注意当进行下一个节点的插入时，需要更新i的值（相当于把i指针往右移），再将i作为参数传入，而不能直接使用j作为参数。因为i使用的是引用类型，在递归过程中是不断向前推进的；而j可能会因为深度条件不符合而导致回溯，其值是可以回退的。这也是递归函数中的一个易错点。
秉持开源精神，分享技术干货，欢迎关注我的公众号：小K技术碎笔
