Mind palace

some thoughts

0%

Posted on Edited on In Disqus:
Symbols count in article: 2.3k Reading time ≈ 2 mins.

O(h) time O(h) space
递归版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * 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* inorderSuccessor(TreeNode* root, TreeNode* p) {
        if (!root) return root;
        if (root->val <= p->val) return inorderSuccessor(root->right, p);
        auto l = inorderSuccessor(root->left, p);
        return l ? l : root;
    }
};

循环版 O(h) time O(1) space
比p大的第一个节点要不是p的父节点（p是其父节点的左子）要不在p的右子树上，从root开始往下找，如果当前的root比p大，说明这个点有可能是p的父节点，即有可能是最终解，先存下来继续往下找，如果当前的root不比p大，说明这个点肯定不是最终解，最终解要不已经被存下来（之前的最近的父节点）要不就还在右子树上，则继续沿着右子树往下找，如果在右子树上找到了符合要求的（比p大的）节点，则存下来更新res，直到找到叶节点为止，复杂度就是树高

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 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* inorderSuccessor(TreeNode* root, TreeNode* p) {
        TreeNode *res = nullptr;
        while (root) {
            if (root->val <= p->val) {
                root = root->right;
            } else {
                res = root;
                root = root->left;
            }
        }
        return res;
    }
};
Read more »

Posted on Edited on In Disqus:
Symbols count in article: 408 Reading time ≈ 1 mins.

双指针 O(n) time O(1) space
题目要求one-pass，所以从头开始往后扫，遇到0往前放，遇到2往后放
i0的左边都是0，i2的右边都是2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n = nums.size();
        int i0 = 0, i2 = n - 1; // i0和i2分别表示下一个0和2要放的位置
        for (int i = 0; i <= i2; ++i) { // 这里必须是<=因为i2最后i和i2相遇时i2也要检查
            if (nums[i] == 0) {
                swap(nums[i], nums[i0++]);
            } else if (nums[i] == 2) {
                swap(nums[i--], nums[i2--]);
            }
        }
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 742 Reading time ≈ 1 mins.

sliding window O(n) 另外有个O(nlogn)的维护presum和map

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int n = nums.size();
        int sum = 0;
        int res = INT_MAX;
        for (int r = 0, l = r; r < n; ++r) {
            sum += nums[r];
            while (sum >= s && l <= r) { // 这里必须是<=因为单个数就有可能大于s
                res = min(res, r + 1 - l); // 因为是求最短所以可以实时更新res
                sum -= nums[l++];
            }
        }
        return (res == INT_MAX ? 0 : res);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int n = nums.size();
        int sum = 0;
        int res = INT_MAX;
        for (int l = 0, r = l; l < n; ++l) {
            while (r < n && sum < s) {
                sum += nums[r++];
            }
            if (sum >= s) {
                res = min(res, r - l);
            }
            sum -= nums[l];
        }
        return (res == INT_MAX ? 0 : res);
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 790 Reading time ≈ 1 mins.

backtracking + dfs O(n)

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
/**
 * 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<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> res;
        vector<int> v;
        dfs(root, sum, v, res);
        return res;
    }

    void dfs(TreeNode *root, int sum, vector<int> &v, vector<vector<int>> &res) {
        if (!root) return;
        v.push_back(root->val);
        if (!root->left && !root->right) {
            if (sum == root->val) {
                res.push_back(v);
            }
        } else {
            dfs(root->left, sum - root->val, v, res);
            dfs(root->right, sum - root->val, v, res);
        }
        v.pop_back();
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 1.1k Reading time ≈ 1 mins.

O(n) time O(n) space
跟242. Valid Anagram基本一样，只要两个数组能对的上就行，需要知道怎么reverse可以参考969. Pancake Sorting

1
2
3
4
5
6
class Solution {
public:
    bool canBeEqual(vector<int>& target, vector<int>& A) {
        return unordered_multiset<int>(A.begin(), A.end()) == unordered_multiset<int>(target.begin(),target.end());
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool canBeEqual(vector<int>& target, vector<int>& arr) {
        unordered_map<int, int> m;
        for (int x : target) {
            ++m[x];
        }
        for (int x : arr) {
            if (--m[x] < 0) return false;
        }
        return true;
    }
};
Read more »

Posted on Edited on In Disqus:
Symbols count in article: 482 Reading time ≈ 1 mins.

O(t.length)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool isSubsequence(string s, string t) {
        int m = s.length(), n = t.length(), i = 0, j = 0;
        if (m > n) return false;
        for (; i < m && j < n; ++j) {
            if (s[i] == t[j]) {
                ++i;
            }
        }
        return i == m;
    }
};
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    bool isSubsequence(string s, string t) {
        int i_t = 0;
        for (auto&& c : s) {
            while (i_t < t.length() && t[i_t] != c) ++i_t;
            if (i_t++ >= t.length()) return false;
        }
        return true;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 367 Reading time ≈ 1 mins.

O(m+n) time O(1) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> addToArrayForm(vector<int>& A, int K) {
        int n = A.size();
        int i = n - 1, c = 0;
        vector<int> res;
        while (i >= 0 || c > 0 || K > 0) {
            int a = i >= 0 ? A[i] : 0;
            int b = K % 10;
            int s = a + b + c;
            c = s / 10;
            res.push_back(s % 10);
            --i;
            K /= 10;
        }
        return vector<int>(rbegin(res), rend(res));
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 678 Reading time ≈ 1 mins.

O(n) time O(26) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        unordered_map<char, int> m;
        int n = s.length();
        int res = 0;
        for (int l = 0, r = 0; r < n; ++r) {
            ++m[s[r]];
            while (l < r && m.size() > 2) {
                if (--m[s[l]] == 0) {
                    m.erase(s[l]);
                }
                ++l;
            }
            res = max(res, r + 1 - l);
        }
        return res;
    }
};

lee的做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        unordered_map<char, int> m;
        int n = s.length();
        int res = 0, l = 0, r = 0;
        for (; r < n; ++r) {
            ++m[s[r]];
            if (m.size() > 2) {
                if (--m[s[l]] == 0) {
                    m.erase(s[l]);
                }
                ++l;
            }
        }
        return r - l;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 168 Reading time ≈ 1 mins.

O(n) time O(1) space

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for (int x : nums) {
            res ^= x;
        }
        return res;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 4.5k Reading time ≈ 4 mins.

上来先clarify数的取值范围，然后再决定用哪个

O(n2) time O(n2) space
对于每个A[i]，从前往后枚举之前的每个A[j]，得到一个等差d，利用以A[j]结尾的等差数列长度来更新以A[i]结尾的等差数列的长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int longestArithSeqLength(vector<int>& A) {
        int n = A.size(), res = 0;
        vector<unordered_map<int, int>> f(n);
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) { // 一定要从前往后，因为是要找最长的，后边的可能更长
                int d = A[i] - A[j];
                f[i][d] = max(2, f[j][d] + 1);
                res = max(res, f[i][d]);
            }
        }
        return res;
    }
};

O(n2) time O(1001n) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int longestArithSeqLength(vector<int>& A) {
        int n = A.size(), res = 0;
        vector<vector<int>> f(n, vector<int>(1001));
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) { // 一定要从前往后，因为是要找最长的，后边的可能更长
                int d = A[i] - A[j] + 500;
                f[i][d] = max(2, f[j][d] + 1);
                res = max(res, f[i][d]);
            }
        }
        return res;
    }
};

O(500n) time O(500) space
因为题目里每个数都是在0到500之间，所以等差的绝对值肯定是在0到500之间，维护正数等差和负数等差两个数组来记录以x为最后一个数的等差数列的长度，从0到500枚举所有可能的等差，对于每个可能的等差d再枚举数组里的每个数x，看x之前数组里有没有x - d和x + d，用他们的等差数列的长度来更新x的长度，然后再更新全局res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int longestArithSeqLength(vector<int>& A) {
        int pos_step[501], neg_step[501];
        int res = 0;
        for (int d = 0; d <= 500; ++d) {
            memset(pos_step, 0, sizeof(pos_step));
            memset(neg_step, 0, sizeof(neg_step));
            for (int x : A) {
                pos_step[x] = x < d ? 1 : pos_step[x - d] + 1;
                neg_step[x] = x + d > 500 ? 1 : neg_step[x + d] + 1;
                res = max(res, pos_step[x]);
                res = max(res, neg_step[x]);
            }
            if (d > 0 && 501 / d < res) break; // 优化：因为等差d从小到大枚举并更新res，如果当前的等差所能产生的最大长度不足以超过之前的res则没必要继续枚举了，直接返回即可
        }
        return res;
    }
};
Read more »