Mind palace

some thoughts

0%

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

O(1) time O(1) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from copy import deepcopy
class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        v = [[False] * 10 for _ in range(9)]
        h = [[False] * 10 for _ in range(9)]
        b = [[False] * 10 for _ in range(9)]
        # v = [[False] * 10 for _ in range(9)]
        # h, b = deepcopy(v), deepcopy(v)
        for r in range(9):
            for c in range(9):
                x = board[r][c]
                if x != '.':
                    x = int(x) # 巧妙！
                    if v[c][x] or h[r][x] or b[r // 3 * 3 + c // 3][x]:
                        return False
                    v[c][x] = h[r][x] = b[r // 3 * 3 + c // 3][x] = True
        return True

用bitset替代hashtable遍历找重复即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        vector<bitset<9>> h(9), v(9), s(9);
        for (int r(0); r < 9; ++r) {
            for (int c(0); c < 9; ++c) {
                if (board[r][c] == '.')
                    continue;
                int x = board[r][c] - '1';
                if (h[r][x] || v[c][x] || s[r / 3 * 3 + c / 3][x]) return false;
                h[r][x] = v[c][x] = s[r / 3 * 3 + c / 3][x] = true;
            }
        }
        return true;
    }
};

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

O(logn) time
找lower_bound

1
2
3
4
5
6
7
8
9
10
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) # 注意直接用左闭右开！！
        while l < r:
            m = l + (r - l) // 2
            if nums[m] < target:
                l = m + 1
            else:
                r = m
        return l
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        int l = 0, r = n; // 直接用左闭右开
        while (l < r) {
            int m = l + (r - l) / 2;
            if (target > nums[m]) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        return l;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        int l = 0, r = n - 1;
        while (l <= r) {
            int m = l + (r - l) / 2;
            if (nums[m] == target) {
                return m;
            } else if (target > nums[m]) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return l;
    }
};

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

O(logn) time

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def find(b, e, t):
            while b < e:
                m = b + (e - b) // 2
                if nums[m] < t:
                    b = m + 1
                else:
                    e = m
            return b
        n = len(nums)
        l = find(0, n, target)
        if l == n or nums[l] != target:
            return [-1, -1]
        return [l, find(l + 1, n, target + 1) - 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:
    vector<int> searchRange(vector<int>& nums, int target) {
        int n = nums.size();
        int i = lb(nums, 0, n, target);
        if (i == n || nums[i] != target) return {-1, -1};
        return {i, lb(nums, i, n, target + 1) - 1}; // 找大一号的数即可，且可以从下界找起
    }

    int lb(const vector<int> &nums, int l, int r, int target) {
        while (l < r) {
            int m = l + (r - l) / 2;
            if (nums[m] < target) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        return l;
    }
};
1
2
3
4
5
6
7
8
9
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        auto lb = lower_bound(begin(nums), end(nums), target);
        if (lb == end(nums) || *lb != target) return {-1, -1};
        auto ub = upper_bound(begin(nums), end(nums), target);
        return {lb - begin(nums), ub - 1 - begin(nums)};
    }
};

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

binary search O(logn)
先判断左半边数多还是右半边数多，再对每一种情况分类讨论

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1
        while (l <= r):
            m = l + (r - l) // 2
            if nums[m] == target:
                return m
            elif nums[m] > nums[r]:
                if nums[l] <= target < nums[m]:
                    r = m - 1
                else:
                    l = m + 1
            else:
                if nums[m] < target <= nums[r]:
                    l = m + 1
                else:
                    r = m - 1
        return -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
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        int l = 0, r = n - 1;
        while (l <= r) { // 这道题是要找数，所以要=
            int mid = (l + r) / 2;
            if (target == nums[mid]) { // 找到直接返回
                return mid;
            } else if (nums[mid] > nums[r]) {
                if (nums[l] <= target && target < nums[mid]) { // 检查是否在单调区间
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[r]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return -1;
    }
};

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

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
class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.length();
        vector<int> v{-1}; // 开始加入-1方便后面计算，比如"()()())"
        for (int i = 0; i < n; ++i) {
            if (s[i] == '(') { // 如果是"("，直接把下标入栈
                v.push_back(i);
            } else {
                if (v.back() != -1 && s[v.back()] == '(') { // 如果是")"，并且栈不为『空』或者栈顶是"("，证明有正确的匹配，将栈顶的"("的下标出栈
                    v.pop_back();
                } else { // 否则证明是一个孤立无法匹配的")"，将下标入栈
                    v.push_back(i);
                }
            }
        }
        v.push_back(n); // 最后入栈一个结尾长度下标，方便计算，比如")()()"
        int res = 0;
        for (int i = 1; i < v.size(); ++i) {
            res = max(res, v[i] - v[i - 1] - 1); // 只需要检查前后两个不匹配的括号之前的距离便可以找到最长的合法匹配的括号的长度
        }
        return res;
    }
};

进一步优化，不需要最后再扫一遍，每次找到一个合法匹配就可以直接更新res

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        stk, res = [-1], 0
        for i, c in enumerate(s):
            if c == '(':
                stk.append(i)
            elif stk[-1] >= 0 and s[stk[-1]] == '(':
                stk.pop()
                res = max(res, i - stk[-1])
            else:
                stk.append(i)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.length(), res = 0;
        stack<int> stk{{-1}}; // 开始加入-1方便后面计算，比如"()()())"
        for (int i = 0; i < n; ++i) {
            if (s[i] == '(') { // 如果是"("，直接把下标入栈
                stk.push(i);
            } else if (stk.top() != -1 && s[stk.top()] == '(') { // 如果是")"，并且栈不为『空』或者栈顶是"("，证明有正确的匹配，将栈顶的"("的下标出栈
                stk.pop(); // 一定要先出栈再更新res
                res = max(res, i - stk.top()); // 当前是一个合法的匹配，更新res
            } else { // 否则证明是一个孤立无法匹配的")"，将下标入栈
                stk.push(i);
            }
        }
        return res;
    }
};

Posted on Edited on Disqus:
Symbols count in article: 186 Reading time ≈ 1 mins. 
1
2
3
4
for i in range(4):
    print(i) # 0 1 2 3

print(i) # 3
1
2
3
4
for i in range(6):
    if i % 2 == 0:
        i += 2
    print(i) # 2 1 4 3 6 5 5

Conclusion:

  • induction variable的scope不仅限于for loop
  • 不管for loop内部对induction variable如何修改，for loop本身还会对其重新赋值

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

O(n) time 举例021找到第一个顺序对02，说明2开始已经是全逆序了，不可能再找到新的排列，所以只能找2后面的一个数和0交换，从后往前找到第一个比0大的是1，说明1以后的数都不比0大，不可能跟0交换，把1跟0交换以后，得到了一个新的排列，这时要将从2开始的全逆序翻转，即021 –> 120 –> 102

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n, x = len(nums), 0
        for i in range(n - 2, -1, -1):
            if nums[i] < nums[i + 1]:
                x = i
                break
        else:
            nums.reverse()
            return
        for i in range(n - 1, x, -1):
            if nums[i] > nums[x]:
                nums[x], nums[i] = nums[i], nums[x]
                break
        # nums[x + 1:] = reversed(nums[x + 1:])
        nums[x + 1:] = nums[n - 1:x:-1]
        # nums[x + 1:] = nums[x + 1:][::-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        for i in range(n - 2, -1, -1):
            if nums[i] < nums[i + 1]:
                break
        else:
            nums.reverse()
            return
        for j in range(n - 1, i, -1):
            if nums[j] > nums[i]:
                nums[i], nums[j] = nums[j], nums[i]
                break
        l, r = i + 1, n - 1
        while l < r:
            nums[l], nums[r] = nums[r], nums[l]
            l += 1
            r -= 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        int i = n - 1;
        while (i > 0 && nums[i - 1] >= nums[i]) --i;
        if (i == 0) {
            reverse(begin(nums), end(nums));
            return;
        }
        int j = n - 1;
        while (nums[j] <= nums[i - 1]) --j;
        swap(nums[i - 1], nums[j]);
        reverse(begin(nums) + i, end(nums));
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        int i = n - 1;
        while (i > 0 && nums[i - 1] >= nums[i]) --i;
        if (i == 0) {
            reverse(begin(nums), end(nums));
            return;
        }
        int j = lower_bound(begin(nums) + i, end(nums), nums[i - 1], greater()) - begin(nums) - 1; // 二分查找右边降序序列里倒数第一个比nums[i - 1]大的数的位置
        swap(nums[i - 1], nums[j]);
        reverse(begin(nums) + i, end(nums));
    }
};
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
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) return;
        int l = 0, r = n - 1;
        int i1 = l, i2 = l;
        for (int i = r; i > l; --i) {
            if (nums[i - 1] < nums[i]) {
                i1 = i - 1;
                i2 = i;
                break;
            }
        }
        if (l == i2) {
            reverse(begin(nums), end(nums));
            return;
        }
        int i3 = i2;
        for (int i = r; i >= i2; --i) {
            if (nums[i] > nums[i1]) {
                i3 = i;
                break;
            }
        }
        swap(nums[i1], nums[i3]);
        reverse(begin(nums) + i2, end(nums));
    }
};
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:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        nextPerm(nums, 0, n - 1); // 这里用的是左右闭区间
    }

    bool nextPerm(vector<int> &nums, int l, int r) {
        if (r <= l) return false; // 如果元素个数为0或者1，则没有下一个排列
        int idx1 = l, idx2 = l;
        for (int i = r - 1; i >= l; --i) { // 从后往前找到第一个相邻两元素后面的比前面大的
            if (nums[i] < nums[i + 1]) {
                idx1 = i;
                idx2 = i + 1;
                break;
            }
        }
        if (idx1 == idx2) { // 如果找不到，说明已经逆序，返回一个初始正序
            reverse(nums.begin() + l, nums.begin() + r + 1);
            return false;
        }
        int idx3 = l;
        for (int i = r; i >= l; --i) { // 从后往前找到第一个比之前找到的较小元素大的元素，与之交换
            if (nums[i] > nums[idx1]) {
                idx3 = i;
                break;
            }
        }
        swap(nums[idx1], nums[idx3]);
        reverse(nums.begin() + idx2, nums.begin() + r + 1); // 将从之前找到的较大元素到数组尾的所有元素翻转
        return true;
    }
};

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

sliding window O(n * l) time O(m * l) space
这道题主要思路是把每个单词当成单个字母来处理，用sliding window找出所有符合要求的结果，即对于s[0:10)来说，假设words的每个单词长度为3，那么第一次处理s[0:3) s[3:6) s[6:9) s[9:10)，第二次处理s[1:4) s[4:7) s[7:10)，第三次处理s[2:5) s[5:8) s[8:10)
跟76. Minimum Window Substring思路接近
跟438. Find All Anagrams in a String解法一样

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:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        if not s or not words: return []
        d = defaultdict(int)
        for w in words:
            d[w] += 1
        n, m, l = len(s), len(words), len(words[0])
        total, res = m * l, []
        for i in range(l):
            td, cnt = d.copy(), m
            for j in range(i, n, l): # 应该是j + l <= n但是python里字符串切片越界也不影响
                t = s[j:j + l]
                td[t] -= 1
                if td[t] >= 0:
                    cnt -= 1
                if j - total >= i:
                    t = s[j - total:j - total + l]
                    td[t] += 1
                    if td[t] > 0:
                        cnt += 1
                if cnt == 0:
                    res.append(j - total + l)
        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
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        if (words.empty() || s.empty()) return {};
        int n = s.length(), m = words.size(), l = words[0].length(), total = m * l;
        unordered_map<string_view, int> hm;
        for (const auto &w : words) {
            ++hm[w];
        }
        string_view sv{s};
        vector<int> res;
        for (int i = 0; i < l; ++i) {
            auto t = hm;
            int cnt = m;
            for (int j = i; j + l <= n; j += l) {
                if (--t[sv.substr(j, l)] >= 0) { // 从0减小成非0不更新cnt
                    --cnt;
                }
                if (j - total >= i && ++t[sv.substr(j - total, l)] > 0) { // cnt只有在大于等于0以上更新才有用，从非0变成0不贡献频数所以不更新cnt
                    ++cnt;
                }
                if (cnt == 0) {
                    res.push_back(j - total + l);
                }
            }
        }
        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
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        if (words.empty() || s.empty()) return {};
        int n = s.length(), m = words.size(), l = words[0].length(), total = m * l;
        unordered_map<string, int> hm;
        for (const auto &w : words) {
            ++hm[w];
        }
        vector<int> res;
        for (int i = 0; i < l; ++i) {
            auto t = hm;
            int cnt = m;
            for (int j = i; j + l <= n; j += l) {
                auto w = s.substr(j, l);
                if (t.count(w) && t[w]-- > 0) {
                    --cnt;
                }
                if (j >= total) {
                    w = s.substr(j - total, l);
                    if (t.count(w) && ++t[w] > 0) {
                        ++cnt;
                    }
                }
                if (cnt == 0) {
                    res.push_back(j - total + l);
                }
            }
        }
        return res;
    }
};

一点优化：如果当前统计的单词不存在则sliding window直接跳过该单词开始新的统计

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
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        if (words.empty() || s.empty()) return {};
        int n = s.length(), m = words.size(), len = words[0].size();
        unordered_map<string, int> hm; // 先统计单词频数
        for (const auto &w : words) {
            ++hm[w];
        }
        vector<int> res;
        for (int i = 0; i < len; ++i) { // trick在扫描方式上，假设单词长度为3，那么第一次扫0369第二次147第三次258
            unordered_map<string, queue<int>> t; // 每个queue放每个有效单词的出现位置
            int cnt = 0;
            for (int j = i, b = j; j + len <= n; j += len) {
                auto w = s.substr(j, len);
                if (hm.count(w) == 0) { // 如果当前位置单词不存在，之前统计全部清空
                    t.clear();
                    cnt = 0;
                    b = j + len;
                } else if (t[w].size() < hm[w]) { // 如果当前位置单词存在且个数未超过上限
                    t[w].push(j);
                    ++cnt;
                } else { // 如果当前位置单词存在但是个数已达上限，清除当前位置单词在窗口内最早出现位置之前的所有单词
                    b = t[w].front() + len;
                    for (auto &&p : t) {
                        while (!p.second.empty() && p.second.front() < b) {
                            --cnt;
                            p.second.pop();
                        }
                    }
                    t[w].push(j);
                    ++cnt;
                }
                if (cnt == m) { // 如果找到符合要求的单词组合
                    res.push_back(b);
                    --cnt;
                    t[s.substr(b, len)].pop();
                    b += len;
                }
            }
        }
        return res;
    }
};

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

binary search O(log(dividend/divisor)) time
相当于把商转成二进制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        dd, dr = abs(dividend), abs(divisor)
        res = 0
        while dd >= dr:
            t, cnt = dr, 1
            while dd >= (t << 1):
                t <<= 1
                cnt <<= 1
            dd -= t
            res += cnt
        if (dividend ^ divisor) < 0:
            return -res
        return min(res, (1 << 31) - 1)
        # return [res, (1 << 31) - 1][res > (1 << 31) - 1] # 相当于array[0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int divide(int dividend, int divisor) {
        long dd = labs(dividend), dr = labs(divisor), res = 0; // 这里要用labs因为abs(INT_MIN)还是INT_MIN
        while (dd >= dr) {
            long t = dr, cnt = 1;
            while (dd >= (t << 1)) { // 这里是要避免1/1这个case死循环
                t <<= 1;
                cnt <<= 1;
            }
            dd -= t;
            res += cnt;
        }
        if ((dividend ^ divisor) < 0) return -res;
        return min(res, (long)INT_MAX);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int divide(int dividend, int divisor) {
        bool isNeg = (dividend ^ divisor) < 0;
        long dd = abs((long)dividend), dr = abs((long)divisor);
        if (dr == 0) return INT_MAX;
        long res = 0, v = 0, shift = 0;
        bool changed = false;
        do {
            dd -= (v >> 1);
            res += (shift >> 1);
            v = dr;
            shift = 1;
            changed = false;
            while (v <= dd) {
                v <<= 1;
                shift <<= 1;
                changed = true;
            }
        } while (changed);
        if (!isNeg && res >= INT_MAX) return INT_MAX;
        return isNeg ? -res : 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
class Solution {
public:
    int divide(int dividend, int divisor) {
        bool isNeg = (dividend ^ divisor) < 0;
        long dd = abs((long)dividend), dr = abs((long)divisor);
        if (dr == 0) return INT_MAX; // x/0
        long res = 0;
        while (true) {
            long v = dr;
            long shift = 1;
            bool changed = false;
            while (v <= dd) {
                v <<= 1;
                shift <<= 1;
                changed = true;
            }
            if (changed) {
                dd -= (v >> 1);
                res += (shift >> 1);
            }
            else {
                break;
            }
        };
        if (!isNeg && res >= INT_MAX) return INT_MAX; // INT_MIN/-1
        return isNeg ? -res : res;
    }
};

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

rolling hash O(h + n)
hash = (hash * base + ord(c)) % modulus
modulus 必须是一个大质数（比 ord(c)要大，否则 C++会算出负数，Python 不会）来避免过多的 collision
必须要解决 hash collision，反例
“gytisyz”
“aaaaaab”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        h, n = len(haystack), len(needle)
        if h < n: return -1
        highest_power, hh, nh = 1, 0, 0
        M, B = 2**31 - 1, 256
        for i in range(n):
            highest_power = (highest_power * B) % M
            hh = (hh * B + ord(haystack[i])) % M
            nh = (nh * B + ord(needle[i])) % M
        for i in range(h - n + 1):
            if i >= 1:
                hh = (hh * B + M - ord(haystack[i - 1]) * highest_power % M + ord(haystack[i + n - 1])) % M
            if hh == nh:
                for j in range(n):
                    if haystack[i + j] != needle[j]:
                        break
                else:
                    return i
        return -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:
    int strStr(string haystack, string needle) {
        int h = haystack.length(), n = needle.length();
        long M = INT_MAX, B = 256;
        if (h < n) return -1;
        long highest_power = 1, hh = 0, nh = 0;
        for (int i = 0; i < n; ++i) {
            highest_power = (highest_power * B) % M;
            nh = (nh * B + needle[i]) % M;
            hh = (hh * B + haystack[i]) % M;
        }
        for (int i = 0; i <= h - n; ++i) {
            if (i >= 1) {
                hh = (hh * B + M - haystack[i - 1] * highest_power % M + haystack[i + n - 1]) % M; // 这里highest_power是B的n次方，因为先整体左移再减高位，如果先减高位再整体左移就是n-1次方了
            }
            if (hh == nh && haystack.substr(i, n) == needle) {
                return i;
            }
        }
        return -1;
    }
};
Read more »