Mind palace

some thoughts

0%

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

前缀和 O(n) time O(1) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        int n = nums.size();
        int presum = 0;
        for (int i = 0; i < n; ++i) {
            if (presum == sum - presum - nums[i]) {
                return i;
            }
            presum += nums[i];
        }
        return -1;
    }
};

前缀和 O(n) time O(n) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int n = nums.size();
        vector<int> presum(n + 1);
        for (int i = 1; i <= n; ++i) {
            presum[i] = presum[i - 1] + nums[i - 1];
        }
        for (int i = 0; i < n; ++i) {
            if (presum[i] == presum[n] - presum[i + 1]) {
                return i;
            }
        }
        return -1;
    }
};

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

O(n) time O(n) space
统计模K同余的presum，跟523. Continuous Subarray Sum类似，区别是K是正数且array可能有负数，所以不需要非得给前缀和维护一个hashmap，直接开一个长度为K的数组来统计即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int subarraysDivByK(vector<int>& A, int K) {
        int n = A.size();
        vector<int> cnt(K);
        cnt[0] = 1; // 必须初始化模0的个数为1，表示什么都没有的情况有1个！！
        for (int i = 0, p = 0; i < n; ++i) {
            p += A[i];
            ++cnt[((p % K) + K) % K];
        }
        int res = 0;
        for (int x : cnt) {
            res += x * (x - 1) / 2; // 即(x - 1) * ((x - 1) + 1) / 2
        }
        return res;
    }
};

O(n2) time O(n) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int subarraysDivByK(vector<int>& A, int K) {
        int n = A.size();
        vector<int> presum(n + 1);
        for (int i = 0; i < n; ++i) {
            presum[i + 1] = presum[i] + A[i];
        }
        int res = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j <= n; ++j) {
                int t = (presum[j] - presum[i]) % K;
                res += t == 0;
            }
        }
        return res;
    }
};

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

dfs

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
class Solution {
public:
    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        m = board.size(), n = board[0].size();
        switch (board[click[0]][click[1]]) {
            case 'M': board[click[0]][click[1]] = 'X'; return board;
            case 'E': update(board, click[0], click[1]); break;
        }
        return board;
    }

    int count(const vector<vector<char>> &b, int y, int x) {
        int res = 0;
        for (int i = 0; i < 8; ++i) {
            int yy = y + dy[i], xx = x + dx[i];
            res += (0 <= yy && yy < m && 0 <= xx && xx < n && b[yy][xx] == 'M');
        }
        return res;
    }

    void update(vector<vector<char>> &b, int y, int x) {
        if (y < 0 || y >= m || x < 0 || x >= n || b[y][x] != 'E') return;
        int cnt = count(b, y, x);
        if (cnt == 0) {
            b[y][x] = 'B';
            for (int i = 0; i < 8; ++i) {
                update(b, y + dy[i], x + dx[i]);
            }
        } else {
            b[y][x] = '0' + cnt;
        }
    }

    int m, n, dy[8] = {1, 1, 0, -1, -1, -1, 0, 1}, dx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
};
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<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        m = board.size(), n = board[0].size();
        switch (board[click[0]][click[1]]) {
            case 'M': {
                board[click[0]][click[1]] = 'X';
                return board;
            } break;
            case 'E': {
                update(board, click[0], click[1]);
            }
        }
        return board;
    }

    int count(const vector<vector<char>> &b, int y, int x) {
        int dy[] = {1, 1, 0, -1, -1, -1, 0, 1}, dx[] = {0, 1, 1, 1, 0, -1, -1, -1};
        int res = 0;
        for (int i = 0; i < 8; ++i) {
            int yy = y + dy[i], xx = x + dx[i];
            if (yy < 0 || yy >= m || xx < 0 || xx >= n || b[yy][xx] != 'M') continue;
            ++res;
        }
        return res;
    }

    void update(vector<vector<char>> &b, int y, int x) {
        if (y < 0 || y >= m || x < 0 || x >= n || b[y][x] != 'E') return;
        int ret = count(b, y, x);
        int dy[] = {1, 1, 0, -1, -1, -1, 0, 1}, dx[] = {0, 1, 1, 1, 0, -1, -1, -1};
        if (ret == 0) {
            b[y][x] = 'B';
            for (int i = 0; i < 8; ++i) {
                update(b, y + dy[i], x + dx[i]);
            }
        } else {
            b[y][x] = '0' + ret;
        }
    }

    int m, n;
};

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

O(n2) time O(n) space
常规遍历ijk需要O(n3)，为了降低复杂度，先枚举j，然后分别枚举i和k，在枚举i的时候，如果遇到s[0:i-1] == s[i+1:j-1]则cache起来，这样在枚举k的时候，直接可以判断cache里是否存在s[j+1:k-1] == s[k+1:n-1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool splitArray(vector<int>& nums) {
        int n = nums.size();
        if (n < 7) return false;
        vector<int> presum(1);
        for (int x : nums) {
            presum.push_back(presum.back() + x);
        }
        for (int j = 3; j <= n - 4; ++j) {
            unordered_set<int> t;
            for (int i = 1; i <= j - 2; ++i) {
                if (presum[i] == presum[j] - presum[i + 1]) {
                    t.insert(presum[i]);
                }
            }
            for (int k = j + 2; k <= n - 2; ++k) {
                if (presum[k] - presum[j + 1] == presum[n] - presum[k + 1] && t.count(presum[k] - presum[j + 1])) return true;
            }
        }
        return false;
    }
};

O(n2) time O(n2) 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
class Solution {
public:
    bool splitArray(vector<int>& nums) {
        int n = nums.size();
        if (n < 7) return false;
        int s = accumulate(begin(nums), end(nums), 0), s0 = nums[0];
        vector<unordered_set<int>> m(n);
        int t = nums[0] + nums[1] + nums[2];
        for (int j = 3; j <= n - 4; ++j) {
            t += nums[j];
            int s2 = nums[j + 1];
            for (int k = j + 2; k <= n - 2; ++k) {
                int s3 = s - (t + s2 + nums[k]);
                if (s2 == s3) {
                    m[j].insert(s2);
                }
                s2 += nums[k];
            }
        }
        for (int i = 1; i <= n - 6; ++i) {
            int s1 = nums[i + 1];
            for (int j = i + 2; j <= n - 4; ++j) {
                if (s0 == s1 && m[j].count(s1)) return true;
                s1 += nums[j];
            }
            s0 += nums[i];
        }
        return false;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 1.2k Reading time ≈ 1 mins. 
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
class RandomizedSet {
public:
    /** Initialize your data structure here. */
    RandomizedSet() {
        srand(time(NULL)); // 用时间做种子
    }

    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    bool insert(int val) {
        if (m.count(val)) return false;
        m[val] = v.size(); // 用数组下标来把hashmap和数组联系起来
        v.push_back(val);
        return true;
    }

    /** Removes a value from the set. Returns true if the set contained the specified element. */
    bool remove(int val) {
        if (!m.count(val)) return false;
        m[v.back()] = m[val]; // 删除的主要操作是把数组中待删除的数和数组最后一个数『交换』，所以要把最后一个数的下标改成待删除的数的下标
        v[m[val]] = v.back(); // 把数组结尾的数挪到待删除的数的位置
        v.pop_back();
        m.erase(val);
        return true;
    }

    /** Get a random element from the set. */
    int getRandom() {
        return v.empty() ? 0 : v[rand() % v.size()]; // 注意数组为空的case
    }

    unordered_map<int, int> m; // 因为添加删除都要O(1)所以肯定是unordered容器，又因为unordered_set无法保存更多的信息，所以肯定要想到用unordered_map
    vector<int> v; // 因为需要random access所以肯定要用一个数组存所有的数，即v[m[val]] = val
};

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * bool param_1 = obj.insert(val);
 * bool param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */

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

O(mn) time O(1) space
对于每个X只要确定左边和上边不是X就行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int countBattleships(vector<vector<char>>& board) {
        if (board.empty() || board[0].empty()) return 0;
        int res = 0;
        int n = board.size(), m = board[0].size();
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if ((board[i][j] == 'X')
                    && (i == 0 || board[i - 1][j] != 'X')
                    && (j == 0 || board[i][j - 1] != 'X')) {
                    ++res;
                }
            }
        }
        return res;
    }
};

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

union-find O(n) time O(n) space
合法的树只有一个连通组件，因为点数和边数之差为1

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
class Solution {
public:
    bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
        parent.resize(n);
        iota(begin(parent), end(parent), 0);
        cnt = n;
        for (int i = 0; i < n; ++i) {
            if (!merge(i, leftChild[i])) return false;
            if (!merge(i, rightChild[i])) return false;
        }
        return cnt == 1;
    }

    int find(int x) {
        while (x != parent[x]) {
            x = parent[x] = parent[parent[x]];
        }
        return x;
    }

    bool merge(int x, int y) {
        if (y == -1) return true; // 注意-1的情况！！！
        int px = find(x), py = find(y);
        if (px == py) return false;
        parent[px] = py;
        --cnt;
        return true;
    }

    int cnt;
    vector<int> parent;
};

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

two-pass greedy O(n) time O(1) space
反证即可，如果有反例则一定可以trap，否则就是balanced
There are 3 valid cases:

  1. There are more open parenthesis but we have enough ‘*‘ so we can balance the parenthesis with ‘)’
  2. There are more close parenthesis but we have enough ‘*‘ so we can balance the parenthesis with ‘(‘
  3. There are as many ‘(‘ than ‘)’ so all parenthesis are balanced, we can ignore the extra ‘*‘

Algorithm: You can parse the String twice, once from left to right by replacing all ‘*‘ by ‘(‘ and once from right to left by replacing all ‘*‘ by ‘)’. For each of the 2 loops, if there’s an iteration where you end up with a negative count (SUM[‘(‘] - SUM[‘)’] < 0) then you know the parenthesis were not balanced. You can return false. After these 2 checks (2 loops), you know the string is balanced because you’ve satisfied all the 3 valid cases mentioned above.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool checkValidString(string s) {
        int l = 0;
        for (char c : s) {
            l += (c == ')' ? -1 : 1); // 如果所有*都当(
            if (l < 0) return false;
        }
        if (l == 0) return true; // 只是用来加速，可有可无
        int r = 0, n = s.length();
        for (int i = n - 1; i >= 0; --i) {
            r += (s[i] == '(' ? -1 : 1); // 如果所有*都当)
            if (r < 0) return false;
        }
        return true; // 因为既没有左括号过多又没有右括号过多，所以是balanced
    }
};

O(n) 用lo和hi来表示可能的左括号个数减右括号个数之差（只考虑非负数）的区间，
比如(*)，(是[1, 1]，(*是[0, 2]，(*)是[0, 1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool checkValidString(string s) {
        int lo = 0, hi = 0;
        for (char c : s) {
            if (c == '(') { // 遇见左括号，则区间整体加1
                ++lo;
                ++hi;
            } else if (c == ')') { // 遇见右括号，则区间整体减1
                --lo;
                --hi;
            } else { // 遇见*，既可能是左括号，也可能是右括号，则区间扩大lo减1，hi加1
                --lo;
                ++hi;
            }
            if (hi < 0) return false; // 当hi为负时，说明右括号过多，肯定不合法
            lo = max(lo, 0); // lo如果小于0，说明)比(多，是不合法的，如果hi并没有小于0，说明lo小于0是由之前的*造成的，*不一定是)也可能是空字符或者(，所以这里lo时刻要保持为非负数，要排除之前的过多*和)对后边可能产生的影响，比如反例((*)(*))((*如果不维持lo始终非负，则最后会产生false negative，因为前面的*和)让low小于0，后边过多的(虽然让low变成非负，但是结果并不合法
        }
        return lo == 0; // 最后判断一下0是否在区间里
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool checkValidString(string s) {
        int lo = 0, hi = 0;
        for (char c : s) {
            lo += c == '(' ? 1 : -1;
            hi += c == ')' ? -1 : 1;
            if (hi < 0) return false;
            lo = max(lo, 0);
        }
        return lo == 0;
    }
};

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

binary search O(logn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int n = nums.size();
        long l = 0, r = n - 1;
        while (l < r) {
            long m = l + (r - l) / 2;
            if (nums[m] > nums[m + 1]) { // 因为一定存在peak所以只要单边检查即可，之所以选择m + 1而不是m - 1是因为m一定会取到较小的那个数，也就是说m + 1一定存在，而m - 1不一定
                r = m;
            } else {
                l = m + 1;
            }
        }
        return l;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int n = nums.size();
        int l = 0, r = n - 1;
        while (l <= r) {
            int m = l + (r - l) / 2;
            if ((m == 0 || nums[m - 1] < nums[m]) && (m == n - 1 || nums[m] > nums[m + 1])) {
                return m; // 循环内return一律终止条件设成l <= r
            } else if (m == 0 || nums[m - 1] < nums[m]) {
                l = m + 1; // m不可能是结果
            } else {
                r = m - 1; // m不可能是结果
            }
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int n = nums.size();
        int l = 0, r = n - 1;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (nums[m] < nums[m + 1]) { // m never reaches n - 1
                l = m + 1;
            } else {
                r = m; // nums[m] > nums[m + 1] so m could be an answer and should be inclusive when shrinking range
            }
        }
        return l;
    }
};

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

trie
因为是最后k个字母，所以是suffix tree

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
44
45
46
47
48
49
50
class StreamChecker {
public:
    StreamChecker(vector<string>& words) : root(new TrieNode) {
        for (const auto &w : words) {
            add(w);
        }
    }

    bool query(char letter) {
        data += letter;
        return search(data);
    }

    struct TrieNode {
        TrieNode *children[26] = {nullptr};
        bool isEnd = false;
    };

    void add(const string &s) {
        auto p = root;
        for (auto rit = rbegin(s); rit != rend(s); ++rit) {
            int k = *rit - 'a';
            if (!p->children[k]) {
                p->children[k] = new TrieNode;
            }
            p = p->children[k];
        }
        p->isEnd = true;
    }

    bool search(const string &s) {
        auto p = root;
        for (auto rit = rbegin(s); rit != rend(s); ++rit) {
            int k = *rit - 'a';
            if (p->isEnd) return true;
            if (!p->children[k]) return false;
            p = p->children[k];
        }
        return p->isEnd;
    }

    string data;
    TrieNode *root;
};

/**
 * Your StreamChecker object will be instantiated and called as such:
 * StreamChecker* obj = new StreamChecker(words);
 * bool param_1 = obj->query(letter);
 */