Mind palace

some thoughts

0%

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

sliding window O(minSize * n) time O(n) space
这道题的trick是如果maxSize的子串多次出现则minSize的子串只会出现更多次因为短子串一定包含在长子串里，所以只需要检查minSize子串即可！！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int maxFreq(string s, int maxLetters, int minSize, int maxSize) {
        int res = 0;
        unordered_map<string, int> f;
        unordered_map<char, int> m;
        for (int l = 0, r = 0; r < size(s); ++r) {
            ++m[s[r]];
            if (r >= minSize) {
                if (--m[s[l]] == 0) {
                    m.erase(s[l]);
                }
                ++l;
            }
            if (r >= minSize - 1 && size(m) <= maxLetters) {
                res = max(res, ++f[s.substr(l, minSize)]);
            }
        }
        return res;
    }
};
Read more »

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

O(nlogn) time O(n) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> arrayRankTransform(vector<int>& arr) {
        auto A = arr;
        sort(begin(A), end(A));
        unordered_map<int, int> m;
        for (int x : A) {
            m.emplace(x, size(m) + 1); // insert重复key会失败，只有第一个会keep
        }
        for (int i = 0; i < size(arr); ++i) {
            A[i] = m[arr[i]];
        }
        return A;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> arrayRankTransform(vector<int>& arr) {
        vector<int> A = arr;
        sort(begin(A), end(A));
        unordered_map<int, int> m;
        int i = 0;
        for (int x : A) {
            m[x] = m.count(x) ? m[x] : ++i;
        }
        vector<int> res;
        for (int x : arr) {
            res.push_back(m[x]);
        }
        return res;
    }
};

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

dfs O(n) time O(h) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * 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 maxDepth(TreeNode* root) {
        return root ? max(maxDepth(root->left), maxDepth(root->right)) + 1 : 0;
    }
};

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

recursive dfs O(n)
判断对应子树一样即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 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:
    bool isSymmetric(TreeNode* root) {
        return !root || isMirror(root->left, root->right);
    }

    bool isMirror(TreeNode *l, TreeNode *r) {
        if (!l && !r) return true;
        if (!l || !r || l->val != r->val) return false;
        return isMirror(l->left, r->right) && isMirror(l->right, r->left);
    }
};

iterative bfs O(n)
trick是用一个queue放两个root，然后对于一对left和right分别push left的left，right的right，left的right，right的left

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
/**
 * 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:
    bool isSymmetric(TreeNode* root) {
        queue<TreeNode *> q;
        q.push(root);
        q.push(root);
        while (!q.empty()) {
            auto l = q.front(); q.pop();
            auto r = q.front(); q.pop();
            if (!l && !r) continue;
            if (!l || !r || l->val != r->val) return false;
            q.push(l->left);
            q.push(r->right);
            q.push(l->right);
            q.push(r->left);
        }
        return true;
    }
};

follow up 如果left or right pointer can point to any node in tree
必须要一一对应，要不就是自己

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
unordered_map<TreeNode *, TreeNode *> m;

bool isMirror(TreeNode *l, TreeNode *r) {
    if (l == r) {
        if (!l) return true;
        if (m.count(l)) return m[l] == l;
        m[l] = l;
        return isMirror(l->left, l->right);
    } else {
        if (!l || !r) return false;
        if (!m.count(l) && !m.count(r)) {
            m[l] = r;
            m[r] = l;
            return isMirror(l->left, r->right) && isMirror(l->right, r->left);
        }
        return m.count(l) && m.count(r) && m[l] == r && m[r] == l;
    }
}

bool isSymmetric(TreeNode *root) {
    return isMirror(root, root);
}

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

O(n)
把这道题转换成类似找第一小第二小第三小的数，最后的a1和a2不一定是最后结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int a1 = INT_MAX, a2 = INT_MAX;
        for (int x : nums) {
            if (x <= a1) {
                a1 = x;
            } else if (x <= a2) {
                a2 = x;
            } else {
                return true;
            }
        }
        return false;
    }
};

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

iterative stack O(n) time O(n) space

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
/**
 * 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> inorderTraversal(TreeNode* root) {
        stack<pair<TreeNode *, bool>> s;
        s.emplace(root, false);
        vector<int> res;
        while (!s.empty()) {
            auto [n, v] = s.top();
            s.pop();
            if (!n) continue;
            if (v) {
                res.push_back(n->val);
            } else {
                s.emplace(n->right, false);
                s.emplace(n, true);
                s.emplace(n->left, false);
            }
        }
        return res;
    }
};
Read more »

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

backtracking O(n*2n) time 即worst case “aaa”
预处理isPalin剪枝提速

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
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
    vector<vector<string>> partition(string s) {
        n = s.length();
        isPalin.resize(n, vector<bool>(n));
        computeIsPalin(s);
        dfs(s, 0);
        return res;
    }

    void computeIsPalin(const string &s) {
        for (int i = 0; i < n; ++i) {
            isPalin[i][i] = true;
        }
        for (int i = 0; i < n - 1; ++i) {
            isPalin[i][i + 1] = (s[i] == s[i + 1]);
        }
        for (int len = 2; len <= n; ++len) {
            for (int i = 0, j = i + len; i < n && j < n; ++i, ++j) {
                isPalin[i][j] = isPalin[i + 1][j - 1] && (s[i] == s[j]);
            }
        }
    }

    void dfs(string_view s, int b) {
        if (b == n) {
            vector<string> vs(begin(v), end(v));
            res.push_back(move(vs));
        }
        for (int i = b; i < n; ++i) {
            if (isPalin[b][i]) {
                v.push_back(s.substr(b, i + 1 - b));
                dfs(s, i + 1);
                v.pop_back();
            }
        }
    }

    int n;
    vector<string_view> v;
    vector<vector<string>> res;
    vector<vector<bool>> isPalin;
};
Read more »

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

knapsack O(mn) time O(m) space
问题是累加到amount最少需要多少个coin
假设最终是a0 + a1 + a2 + … + ak = amount
最后一步：ak是最后一个coin（可能是任何一种币值coins[j]）
之前一步：a0 + a1 + a2 + … + ak-1 = amount - ak
问题变成：求累加到amount - ak最少需要多少个coin
从f[amount]变成f[amount - ak]，f[i]表示累加到i最少需要多少个coin
状态转移方程：f[i] = min(f[i-coins[j]] + 1) where 0 <= j < n && i >= coins[j]
初始条件：f[0] = 0
最终要求的：f[amount]
边界条件：如果某个f[x]不能由任何coin组合，则其值为INT_MAX（也可以用amount + 1来代替避免overflow）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        vector<int> f(amount + 1, INT_MAX);
        f[0] = 0;
        for (int i = 1; i <= amount; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i >= coins[j] && f[i - coins[j]] != INT_MAX) {
                    f[i] = min(f[i], f[i - coins[j]] + 1);
                }
            }
        }
        return f[amount] == INT_MAX ? -1 : f[amount];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        vector<int> f(amount + 1, amount + 1);
        f[0] = 0;
        for (int i = 1; i <= amount; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i >= coins[j]) {
                    f[i] = min(f[i], f[i - coins[j]] + 1);
                }
            }
        }
        return f[amount] >= amount + 1 ? -1 : f[amount];
    }
};

knapsack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> f(amount + 1, amount + 1);
        f[0] = 0;
        for (int i = 1; i <= amount; ++i) {
            for (int c : coins) {
                if (i >= c) {
                    f[i] = min(f[i], f[i - c] + 1);
                }
            }
        }
        return f[amount] > amount ? -1 : f[amount];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> f(amount + 1, amount + 1);
        f[0] = 0;
        for (int c : coins) {
            for (int i = c; i <= amount; ++i) {
                f[i] = min(f[i], f[i - c] + 1);
            }
        }
        return f[amount] > amount ? -1 : f[amount];
    }
};

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

O(n) time O(1) space
利用下标从0到n，把所有数异或最后剩下的就是差的数

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int res = n;
        for (int i = 0; i < n; ++i) {
            res ^= (i ^ nums[i]);
        }
        return res;
    }
};

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

greedy O(n) time - best!
计算每个位置所能到达的最远的位置（选择最远的，即贪心），并维护一个全局当前可以到达的最远位置，如果当前的位置比当前的全局可以到达的最远位置还要远，证明当前位置无法达到，那么最后一个位置也不可能从第一个位置到达

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0, curr_max = 0; i < n && curr_max < n - 1; ++i) {
            if (i > curr_max) return false;
            curr_max = max(curr_max, i + nums[i]);
        }
        return true;
    }
};
Read more »