Mind palace

some thoughts

0%

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

rolling hash 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
class Solution {
public:
    string shortestPalindrome(const string &s) {
        if (s.empty()) return s;
        string r(rbegin(s), rend(s));
        long M = INT_MAX, B = 256;
        int n = size(s);
        vector<long> p(n, 1);
        for (int i = 1; i < n; ++i) {
            p[i] = (p[i - 1] * B) % M;
        }
        long sh = 0, rh = 0;
        for (int i = 0; i < n; ++i) {
            sh = (sh * B + s[i]) % M;
            rh = (rh * B + r[i]) % M;
        }
        if (sh == rh && s.compare(0, n, r, 0, n) == 0) return s;
        for (int i = 1; i < n; ++i) {
            sh = (sh + M - s[n - i] * p[i - 1] % M) % M;
            rh = (rh + M - r[i - 1] * p[n - i] % M) % M;
            if (sh == rh * p[i] % M && s.compare(0, n - i, r, i, n - i) == 0) return r.substr(0, i) + s;
        }
        return s;
    }
};
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
class Solution {
public:
    string shortestPalindrome(const string &s) {
        if (s.empty()) return s;
        string r(rbegin(s), rend(s));
        long M = INT_MAX, B = 256;
        int n = size(s);
        vector<long> p(n, 1);
        for (int i = 1; i < n; ++i) {
            p[i] = (p[i - 1] * B) % M;
        }
        long sh = 0, rh = 0;
        for (int i = 0; i < n; ++i) {
            sh = (sh + s[i] * p[i]) % M;
            rh = (rh + r[i] * p[i]) % M;
        }
        if (sh == rh && s.compare(0, n, r, 0, n) == 0) return s;
        for (int i = 1; i < n; ++i) {
            sh = (sh + M - s[n - i] * p[n - i] % M) % M;
            rh = (rh + M - r[i - 1] * p[i - 1] % M) % M;
            if ((sh * p[i]) % M == rh && s.compare(0, n - i, r, i, n - i) == 0) return r.substr(0, i) + s;
        }
        return s;
    }
};
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
class Solution {
public:
    string shortestPalindrome(const string &s) {
        if (s.empty()) return s;
        string r(rbegin(s), rend(s));
        long M = INT_MAX, B = 256;
        int n = size(s);
        vector<long> p(n, 1), sh(n), rh(n);
        for (int i = 1; i < n; ++i) {
            p[i] = (p[i - 1] * B) % M;
        }
        sh[0] = s[0];
        rh[0] = r[0];
        for (int i = 1; i < n; ++i) {
            sh[i] = (sh[i - 1] + s[i] * p[i]) % M;
            rh[i] = (rh[i - 1] + r[i] * p[i]) % M;
        }
        if (sh[n - 1] == rh[n - 1] && s.compare(0, n, r, 0, n) == 0) return s;
        for (int i = 1; i < n; ++i) {
            auto a = (sh[n - i - 1] * p[i]) % M;
            auto b = (rh[n - 1] + M - rh[i - 1]) % M;
            if (a == b && s.compare(0, n - i, r, i, n - i) == 0) return r.substr(0, i) + s;
        }
        return s;
    }
};

O(n2)递归版
KMP可以实现O(n)
我们使用双指针来找出字符串s的最长回文前缀的大概范围，指针i和j分别指向s串的开头和末尾，若 s[i] 和 s[j] 相等，则i自增1，j自减1，否则只有j自减1。这样遍历一遍后，最长回文前缀就在范围 [0, i) 中，但不保证这个本身就是最大回文前缀，我们只能确定后面剩余的部分肯定不属于，此时我们提取出剩下的字符，翻转一下加到最前面，而对范围 [0, i) 内的子串再次递归调用本函数，这样，在子函数最终会组成最短的回文串，从而使得整个的回文串就是最短的
Each iteration of shortestPalindrome is linear in size of substring and the maximum number of recursive calls can be n/2 times as shown in the Intuition section.
Let the time complexity of the algorithm be T(n). Since, at the each step for the worst case, the string can be divide into 2 parts and we require only one part for further computation. Hence, the time complexity for the worst case can be represented as : T(n)=T(n-2)+O(n)T(n)=T(n−2)+O(n). So, T(n) = O(n) + O(n-2) + O(n-4) + … + O(1)T(n)=O(n)+O(n−2)+O(n−4)+…+O(1) which is O(n2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    string shortestPalindrome(string s) {
        int n = s.length();
        int i = 0;
        for (int j = n - 1; j >= 0;--j) {
            if (s[i] == s[j]) {
                ++i;
            }
        }
        if (i == n) return s;
        string prefix = s.substr(i);
        reverse(prefix.begin(), prefix.end());
        string mid = shortestPalindrome(s.substr(0, i));
        return prefix + mid + s.substr(i);
    }
};

iterative O(n2) time

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    string shortestPalindrome(const string &s) {
        int n = size(s);
        string r(rbegin(s), rend(s));
        for (int i = 0; i < n; ++i) {
            if (s.compare(0, n - i, r, i, n - i) == 0) return r.substr(0, i) + s; // 避免copy
        }
        return s;
    }
};

TLE O(n2) time

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    string shortestPalindrome(const string &s) {
        int n = size(s);
        string r(rbegin(s), rend(s));
        for (int i = 0; i < n; ++i) {
            if (s.substr(0, n - i) == r.substr(i)) return r.substr(0, i) + s;
        }
        return s;
    }
};

错误dp版本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
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
    string shortestPalindrome(string s) {
        if (s.empty()) return "";
        string t = s;
        reverse(t.begin(), t.end());
        int n = s.length();
        vector<vector<int>> f(n + 1, vector<int>(n + 1));
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (s[i - 1] == t[j - 1]) {
                    f[i][j] = f[i - 1][j - 1] + 1;
                } else {
                    f[i][j] = max(f[i][j - 1], f[i - 1][j]);
                }
            }
        }
        string res;
        for (int i = n, j = n; i > 0 || j > 0;) {
            if (i == 0) {
                res += t[j - 1];
                --j;
            } else if (j == 0) {
                res += s[i - 1];
                --i;
            } else if (s[i - 1] == t[j - 1]) {
                res += s[i - 1];
                --i;
                --j;
            } else {
                if (f[i][j] == f[i][j - 1]) {
                    res += t[j - 1];
                    --j;
                } else {
                    res += s[i - 1];
                    --i;
                }
            }
        }
        return res;
    }
};

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

dfs O(n) time O(logn) space
遍历左半边的时候，相当于

1
2
3
4
5
if (lb) {
    res.push_back(root->val);
}
dfs(root->left, lb, false);
dfs(root->right, lb && !root->left, false); // 只有左子不存在才考虑右子

遍历右半边的时候，相当于

1
2
3
4
5
dfs(root->left, false, rb && !root->right); // 只有右子不存在才考虑左子
dfs(root->right, false, rb);
if (rb) {
    res.push_back(root->val);
}
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
/**
 * 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> boundaryOfBinaryTree(TreeNode* root) {
        if (!root) return {};
        res.push_back(root->val);
        dfs(root->left, true, false); // 左右分两半递归遍历，遍历左半边时，右flag永远是false
        dfs(root->right, false, true); // 遍历右半边时，左flag永远是false
        return res;
    }

    void dfs(TreeNode *root, bool lb, bool rb) {
        if (!root) return;
        if (!root->left && !root->right) {
            res.push_back(root->val);
            return; // 所有的叶节点放完即返回
        }
        if (lb) { // 左半边的遍历顺序是中左右
            res.push_back(root->val);
        }
        dfs(root->left, lb, rb && !root->right); // 右半边的内部节点不加，当右子树不为空，左边除叶节点以外所有节点都认为是内部节点
        dfs(root->right, lb && !root->left, rb); // 左半边的内部节点不加，当左子树不为空，右边除叶节点完所有节点都认为是内部节点
        if (rb) { // 右半边的遍历顺序是左右中
            res.push_back(root->val);
        }
    }

    vector<int> res;
};
Read more »

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

O(mn) time O(mn) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int K) {
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> res = mat, presum(m + 1, vector<int>(n + 1));
        for (int r = 1; r <= m; ++r) {
            for (int c = 1; c <= n; ++c) {
                presum[r][c] = presum[r - 1][c] + presum[r][c - 1] - presum[r - 1][c - 1] + mat[r - 1][c - 1];
            }
        }
        for (int r = 0; r < m; ++r) {
            for (int c = 0; c < n; ++c) {
                int ulr = max(0, r - K), ulc = max(0, c - K), brr = min(m - 1, r + K), brc = min(n - 1, c + K);
                res[r][c] = presum[brr + 1][brc + 1] + presum[ulr][ulc] - presum[ulr][brc + 1] - presum[brr + 1][ulc];
            }
        }
        return res;
    }
};

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

O(logn) time O(1) space

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int findSpecialInteger(vector<int>& arr) {
        int n = size(arr);
        for (auto p : {.25, .5, .75}) { // 分别测试每个quartile位置的数，超过25%的数一定能被capture
            int i = n * p;
            auto [b, e] = equal_range(begin(arr), end(arr), arr[i]);
            if (e - b > n / 4) return arr[i];
        }
        return -1;
    }
};

O(n) time O(1) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int findSpecialInteger(vector<int>& arr) {
        int n = arr.size(), mx = n * .25;
        for (int i = 0; i < n;) {
            int j = i;
            while (arr[j] == arr[i]) {
                if (++j - i > mx) return arr[i]; // 一旦找到则提前返回
            }
            i = j;
        }
        return -1;
    }
};

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

找到中点reverse后半部，跟前半部比对即可，比如[1,2,1]拆成[1]和[2,1]，比较[1]跟[1,2]即可

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (!head || !head->next) return true;
        ListNode dummy_head(0), *slow = &dummy_head, *fast = head; // fast从head或者dummy_head开始都行
        dummy_head.next = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        fast = slow->next;
        slow->next = nullptr;
        fast = reverse(fast);
        while (head && head->val == fast->val) { // head短fast长因为找中点时fast从head开始
            head = head->next;
            fast = fast->next;
        }
        return !head;
    }

    ListNode *reverse(ListNode *head) {
        ListNode *prev = nullptr, *curr = head;
        while (curr) {
            auto succ = curr->next; curr->next = prev; prev = curr;
            curr = succ;
        }
        return prev;
    }
};
Read more »

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

O(n) time
这道题2001:0db8:85a3:00:000:8A2E:0370:7334是合法的

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 Solution {
public:
    string validIPAddress(string IP) {
        if (isIPv4(IP)) return "IPv4";
        else if (isIPv6(IP)) return "IPv6";
        return "Neither";
    }

    bool isIPv4(const string &IP) {
        if (count(begin(IP), end(IP), '.') != 3) return false;
        istringstream input(IP);
        string s;
        int cnt = 0;
        while (getline(input, s, '.')) { // 分段检查
            try {
                int x = stoi(s);
                if (to_string(x) != s || x < 0 || x > 255) return false; // 开头不能有0，必须在0到255之间，不能有非数字
            } catch (exception &e) {
                return false;
            }
            ++cnt;
        }
        return cnt == 4;
    }

    bool isIPv6(const string &IP) {
        if (count(begin(IP), end(IP), ':') != 7) return false;
        istringstream input(IP);
        string s;
        int cnt = 0;
        while (getline(input, s, ':')) { // 分段检查
            if (empty(s) || size(s) > 4) return false;
            for (char c : s) {
                c = tolower(c);
                if (!('0' <= c && c <= '9') && !('a' <= c && c <= 'f')) return false; // 不能有非16进制字符
            }
            ++cnt;
        }
        return cnt == 8;
    }
};
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
class Solution {
public:
    string validIPAddress(string IP) {
        if (IP.empty() || IP.back() == '.' || IP.back() == ':') return "Neither"; // 不能结尾出现delimiter
        bool isv4 = false;
        for (char c : IP) {
            if (isv4 = c == '.') break; // 初步判断是v4还是v6
        }
        char delimiter = isv4 ? '.' : ':';
        int cnt = 0;
        istringstream input(IP);
        string s;
        while (getline(input, s, delimiter)) { // 分段检查
            if (!isValid(s, isv4)) return "Neither";
            ++cnt; // 数一共有几段
        }
        if (isv4) { // 判断段数是否合法
            return cnt == 4 ? "IPv4" : "Neither";
        } else {
            return cnt == 8 ? "IPv6" : "Neither";
        }
    }

    bool isValid(const string &s, bool isv4) {
        if (isv4) {
            if (s.empty() || s.length() > 3) return false; // 判断长度
            int x = 0;
            for (char c : s) {
                if (!isdigit(c)) return false; // 判断是否有非法字符比如abcd
                x = x * 10 + c - '0';
            }
            return (s == "0") || (0 < x && x < 256 && s[0] != '0'); // 不能出现leading zeros
        } else {
            if (s.empty() || s.length() > 4) return false;
            for (char c : s) {
                c = tolower(c);
                if (!('0' <= c && c <= '9') && !('a' <= c && c <= 'f')) return false;
            }
            return true;
        }
    }
};

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

hashmap O(n)
这个方法比简单统计字母频要快

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int firstUniqChar(string s) {
        int f[26] = {0};
        for (const auto &c : s) {
            ++f[c - 'a'];
        }
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            if (f[s[i] - 'a'] == 1) {
                return i;
            }
        }
        return -1;
    }
};

把重复的字母的下标全部记成n，不重复的则记成i，然后遍历找出最小的i

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int firstUniqChar(string s) {
        vector<int> m(26, INT_MAX);
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            int k = s[i] - 'a';
            if (m[k] == INT_MAX) {
                m[k] = i;
            } else if (m[k] < n) {
                m[k] = n;
            }
        }
        int res = *min_element(m.begin(), m.end());
        return res < n ? res : -1;
    }
};

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

dp O(mn) time O(mn) space
LCS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.length(), n = text2.length();
        vector<vector<int>> f(m + 1, vector<int>(n + 1));
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (text1[i - 1] == text2[j - 1]) {
                    f[i][j] = f[i - 1][j - 1] + 1;
                } else {
                    f[i][j] = max(f[i - 1][j], f[i][j - 1]);
                }
            }
        }
        return f[m][n];
    }
};

O(mn) time O(n) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.length(), n = text2.length();
        vector<vector<int>> f(2, vector<int>(n + 1));
        for (int i = 1; i <= m; ++i) {
            for (int k = i & 1, j = 1; j <= n; ++j) {
                if (text1[i - 1] == text2[j - 1]) {
                    f[k][j] = f[k ^ 1][j - 1] + 1;
                } else {
                    f[k][j] = max(f[k ^ 1][j], f[k][j - 1]);
                }
            }
        }
        return f[m & 1][n];
    }
};

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

decreasing deque O(n) time O(k) space
维护一个递减deque，因为每次新数都是从尾入队列，所以能保证deque内所有数在原数组的位置都是递增的，这样就构造了一个数值递减下标递增的数据结构，每次只要检查最前面的数的位置是否已经超过了k个即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> q;
        vector<int> res;
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            while (!q.empty() && nums[q.back()] < nums[i]) {
                q.pop_back();
            }
            q.push_back(i);
            if (i - q.front() >= k) {
                q.pop_front();
            }
            if (i >= k - 1) {
                res.push_back(nums[q.front()]);
            }
        }
        return 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
25
26
27
28
29
30
31
32
33
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        if (k <= 0) return {};
        nums.push_back(INT_MIN);
        int n = nums.size();
        for (int i = 0; i < k; ++i) {
            enqueue(nums[i]);
        }
        vector<int> res;
        for (int i = k; i < n; ++i) {
            res.push_back(q.front());
            dequeue(nums[i - k]);
            enqueue(nums[i]);
        }
        return res;
    }

    void enqueue(int num) {
        while (!q.empty() && num > q.back()) {
            q.pop_back();
        }
        q.push_back(num);
    }

    void dequeue(int num) {
        if (q.front() == num) {
            q.pop_front();
        }
    }

    deque<int> q;
};

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

greedy O(n) time O(1) space
纯粹考心细
从前往后扫，只要找到合适的位置就放，不需要考虑是否最佳，greedy是对的

  1. 如果f[i] == 1跳过
  2. 如果f[i] == 0 && f[i - 1] == 1跳过
  3. 如果f[i] == 0 && f[i + 1] == 1跳过
  4. –n同时一定要将f[i]改成1！！！！！！
  5. 最后一定要判断n等于0！！！！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        int sz = flowerbed.size();
        for (int i = 0; i < sz; ++i) {
            if (flowerbed[i] == 0) {
                if (n == 0) return true;
                if (i > 0 && flowerbed[i - 1]) continue;
                if (i + 1 < sz && flowerbed[i + 1]) continue;
                --n;
                flowerbed[i] = 1; // 放
            }
        }
        return n == 0;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        int sz = flowerbed.size();
        for (int i = 0; i < sz; ++i) {
            if (flowerbed[i] == 0) {
                if (i > 0 && flowerbed[i - 1]) continue;
                if (i + 1 < sz && flowerbed[i + 1]) continue;
                --n;
                flowerbed[i] = 1; // 放
            }
            if (n <= 0) return true; // 这里必须是小于等于0因为可能n会多减
        }
        return false;
    }
};