Leetcode 501-600
510. Inorder Successor in BST II (Medium)¶
返回二叉树中序遍历的后继节点，这里直接给出node，不给root，同时每个节点有指向父节点的指针
Input: root = {"$id":"1","left":{"$id":"2","left":null,"parent": {"$ref":"1"},"right":null,"val":1},"parent":null,"right": {"$id":"3","left":null,"parent":{"$ref":"1"},"right":null,"val":3},"val":2} p = 1 Output: 2 Explanation: 1's in-order successor node is 2. Note that both p and the return value is of Node type.
思路
一个节点左孩子一定在它之前访问，因此只需要判断右节点是否为空
- 不为空，则右子树最左边叶子节点即是后继
- 为空，则访问父亲节点，当某个父亲节点的左节点是该节点时，这个父亲节点是后继，否则返回nullptr
Node* inorderSuccessor(Node* node) {
if (node == nullptr) return nullptr;
if (node->right != nullptr) {
Node* ptr = node->right;
while (ptr->left != nullptr) ptr = ptr->left;
return ptr;
} else {
for (Node* ptr = node; ptr->parent != nullptr; ptr = ptr->parent)
if (ptr == ptr->parent->left) return ptr->parent;
}
return nullptr;
}
516. Longest Palindromic Subsequence (Medium)¶
求一个字符串的最长回文子串
求最长公共子序列
转化成求和reverse的字符串最长公共子序列的问题，这里不用真的翻转，从末尾来取第j个字符就行
104 ms (44.21%)
int longestPalindromeSubseq(string s) {
int n = s.size();
if (n <= 1) return n;
int dp[n + 1][n + 1];
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= n; j ++) {
if (s[i - 1] == s[n - j])
dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
return dp[n][n];
}
动归
可以改进为dp[i][j]表示从i到j最长回文串长度，这样执行次数少了一半
56 ms (95.03%)
转移方程同样，如果 s[i]==s[j] dp[i][j] = dp[i + 1][j - 1] + 2;
else dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
int longestPalindromeSubseq(string s) {
int n = s.size();
if (n <= 1) return n;
int dp[n][n];
memset(dp, 0, sizeof(dp));
for (int i = n - 1; i >= 0; i --) {
dp[i][i] = 1;
for (int j = i + 1; j < n; j ++) {
if (s[j] == s[i]) dp[i][j] = dp[i + 1][j - 1] + 2;
else dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
}
}
return dp[0][n - 1];
}
空间复杂度改进
以上dp可以改为只用一维数组，即如下
32 ms, faster than 99.91%
int longestPalindromeSubseq(string s) {
int n = s.size();
if (n <= 1) return n;
int dp[n];
memset(dp, 0, sizeof(dp));
for (int i = n - 1; i >= 0; i --) {
int prev = dp[i];
dp[i] = 1;
for (int j = i + 1; j < n; j ++) {
int temp = dp[j];
if (s[j] == s[i]) dp[j] = prev + 2;
else dp[j] = max(dp[j], dp[j - 1]);
prev = temp;
}
}
return dp[n - 1];
}
538. Convert BST to Greater Tree (Easy)¶
Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.
Input: The root of a Binary Search Tree like this: 5 / \ 2 13 Output: The root of a Greater Tree like this: 18 / \ 20 13
思路
迭代来做，先走右边，然后加自身节点，然后增加左边
同时有一个参数fatherVal表示比当前节点大的key总和
int recursion(TreeNode *root, int fatherVal) {
if (root == NULL) return 0;
if (root->right != NULL) root->val += recursion(root->right, fatherVal);
else root->val += fatherVal;
if (root->left != NULL) return recursion(root->left, root->val);
return root->val;
}
TreeNode* convertBST(TreeNode* root) {
recursion(root, 0);
return root;
}
543. Diameter of Binary Tree (Easy)¶
Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.
求最长路径1 / \ 2 3 / \ 4 5
思路
这里每个点有两种取法，取->最长长度为左边单链+右边单链，不取->最长为左边双链/右边双链
如果每个点都分取/不取来迭代，次数太多，而且会重复计算很多次
因此想办法在一遍迭代内得到答案，这里可以用一个引用来记录双链，然后recursion只计算单链长度，之前也有题用过这种思路，可以将迭代次数减少为N，即节点个数次迭代
int diameterOfBinaryTree(TreeNode* root) {
if(root == NULL) return 0;
int sum = 0;
recursion(root, sum);
return sum;
}
int recursion(TreeNode* root, int& sum) {
if(root == NULL) return 0;
int left = recursion(root->left, sum);
int right = recursion(root->right, sum);
sum = max(sum, left + right);
return max(left, right) + 1;
}
560. Subarray Sum Equals K (Medium)¶
一个数组，和为k的连续子数组的个数
思路
用一个map记录从左端起连续数字和及其出现次数，当sum-k在之前出现过时，result加上这个次数
最后result即为答案
int subarraySum(vector<int>& n, int k) {
unordered_map<int, int> map;
map[0] = 1;
int result = 0, sum = 0;
for (int num : n) {
sum += num;
if (map.count(sum-k)) result += map[sum - k];
map[sum] ++;
}
return result;
}
564. Find the Closest Palindrome (Hard)¶
给一个正整数字符串，求最近的非自身的回文字符串，如果多个答案距离相同，返回最小的一个
字符串长度不超过18
"1", "0" "1234", "1221" "999", "1001" "998", "999" "99800", "99799" "12120", "12121" "1000", "999" "12932", "12921" "10", "9"
思路
思路关键点1是明白当对称位不一样时，改后面数字即可
关键点2是发现除过999...9和1000...01是会发生进位或退位之外，其余结果都是位数不变，然后在按照思路1修改完成后，对中间位进行修改，包括本来就是回文串的数据
中间位修改就是+1，-1和不变三种情况，这里把前半部分转成long long，然后实际加减一下，再复制一半到后面，即可得到答案
加上之前进退位的两种情况，再除去文串自身，然后检查一遍，即可得到答案
class Solution {
long long pow(long long base, int len) {
long long res = 1;
while (len--) res *= base;
return res;
}
public:
string nearestPalindromic(string n) {
if (n.size() == 0) return n;
long long num = stoll(n);
int len = n.size();
set<long long> candidates;
candidates.insert(pow(10, len) + 1);
candidates.insert(pow(10, len - 1) - 1);
long long prefix = stoll(n.substr(0, (len + 1) / 2));
for (int i = -1; i <= 1; i++) {
if (prefix + i < 0) continue;
string ps = to_string(prefix + i);
candidates.insert(stoll(ps + string(ps.rbegin() + (len&1), ps.rend())));
}
candidates.erase(num);
long long mn = num + 1, res = 0;
for (auto candidate : candidates) {
long long delta = abs(candidate - num);
if (delta < mn || (delta == mn && candidate < res)) {
mn = delta;
res = candidate;
}
}
return to_string(res);
}
};
572. Subtree of Another Tree (Easy)¶
Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node's descendants. The tree s could also be considered as a subtree of itself.
给两个节点，看t是不是s的子树
Given s 3 / \ 4 5 / \ 1 2 Given t 4 / \ 1 2 return true
思路
递归来做，这里要注意的是分两个递归函数，一个确认选当前节点为根节点开始对比，一个递归在左右子树中和t对比
递归总次数为N^2，递归栈最深为2N，可以接受
bool recursion(TreeNode* s, TreeNode* t) {
if (s == NULL || t == NULL) return (t == NULL && s == NULL);
if (s->val != t->val) return false;
return recursion(s->left, t->left) && recursion(s->right, t->right);
}
bool isSubtree(TreeNode* s, TreeNode* t) {
if (s == NULL || t == NULL) return (t == NULL && s == NULL);
if (s->val == t->val) {
if (recursion(s->left, t->left) && recursion(s->right, t->right))
return true;
}
return isSubtree(s->left, t) || isSubtree(s->right, t);
}
581. Shortest Unsorted Continuous Subarray (Easy)¶
Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order, too.
即一个乱序数组中找一个子数组，将这个子数组排好序后整个数组也是有序的Input: [2, 6, 4, 8, 10, 9, 15] Output: 5 Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.
思路
一个数比它后面的最小值还大，或者比前面的最大值还小，都在该数组内
子数组左端点即比后面最小值还大的最左边值，如例子中的6
右端点即比前面最大值还小的最右边值，如例子中的9
扫描两遍，相减得到最终结果即可
int findUnsortedSubarray(vector<int>& nums) {
if (nums.size() <= 1) return 0;
int l = -1, r = -2, mx = nums[0], mn = nums[nums.size()-1];
for (int i = 0; i < nums.size(); i ++) {
if (nums[i] < mx) r = i;
mx = max(nums[i], mx);
}
for (int i = nums.size() - 1; i >= 0; i --) {
if (nums[i] > mn) l = i;
mn = min(nums[i], mn);
}
return r - l + 1;
}