Leetcode Weekly Contest #132 (1025-1028) 思路与题解
Leetcode 4月14日周赛题解...
swtcl，第三题明明 5 min 写个 bf 就能过但我特么想了 40+min 的 dp 和启发式搜索（哭
（然后时间到了之后同学说 bf 能过然后我就试了一下，然后就过了...）
我离 1h AK 就差那么一点点.jpg
总的来说这周题不算难，虽然有一道 8 分题但是稍微想想就能过。
Contest链接在这里
1025. Divisor Game
题目大意
Alice 和 Bob 轮流玩游戏，Alice 先走，规则是给出一个数 N，每次每名玩家可以选择一个能被 N 整除的数 x，然后令 N N-x，如果轮到谁的时候数字是 1，那么这个人输。
输入一个 N, 问 Alice 能不能获胜。
思路
因为 N 为奇数的时候，玩家只能取一个奇数，此时 N 会变为偶数，而 N 为偶数的时候，先走玩家总有一种策略必定获胜。
代码
我特么提交的时候第一次还忘了写 == 0 结果就给了一个错误提交噗x
class Solution {
public:
bool divisorGame(int N) {
return N % 2 == 0;
}
};1026. Maximum Difference Between Node and Ancestor
题目大意
给出一颗二叉树，求两个节点 A, B 使得他们的差值最大且 A 是 B 的祖先节点，输出差值。
思路
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 {
int dfs(TreeNode *root, int mx, int mn) {
if (root == nullptr) return 0;
if (root->val > mx) mx = root->val;
if (root->val < mn) mn = root->val;
if (root->left == nullptr && root->right == nullptr) return abs(mx - mn);
return max(dfs(root->left, mx, mn), dfs(root->right, mx, mn));
}
public:
int maxAncestorDiff(TreeNode* root) {
return dfs(root, root->val, root->val);
}
};1027. Longest Arithmetic Sequence
题目大意
给出一个无序数组，求其最长等差子序列的长度，其中子序列不要求连续。
思路
bf........................................
代码
class Solution {
public:
int longestArithSeqLength(vector<int>& A) {
int mx = 2;
for (int i = 0; i < A.size(); ++i) {
for (int j = i + 1; j < A.size(); ++j) {
auto d = A[j] - A[i];
auto cnt = 2;
auto pre = A[j];
for (int k = j + 1; k < A.size(); ++k) {
if (A[k] - pre == d) {
pre = A[k];
++cnt;
mx = max(cnt, mx);
}
}
}
}
return mx;
}
};1028. Recover a Tree From Preorder Traversal
题目大意
给定一颗二叉树的先序遍历结果，每个节点之前有若干个 - 来表示这个节点的深度，要求还原这颗二叉树。
其中，如果一个节点有且只有一个孩子，那么其为左孩子。
思路
用一个 map 来维护第 i 层的父亲节点，然后从这个父亲节点构造孩子节点。
代码
/**
* 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:
TreeNode* recoverFromPreorder(string S) {
stringstream ss(S);
int val;
int depth;
map<int, TreeNode*> n;
ss >> val;
n[1] = new TreeNode(val);
while (ss) {
char c;
depth = 0;
while ((c = ss.get()) == '-') depth++;
ss.unget();
ss >> val;
if (!ss) break;
if (n[depth]->left == nullptr) {
n[depth]->left = new TreeNode(val);
n[depth+1] = n[depth]->left;
} else {
n[depth]->right = new TreeNode(val);
n[depth+1] = n[depth]->right;
}
}
return n[1];
}
};