Mind palace

some thoughts

0%

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

O(n) time
通用解法

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
class Solution {
public:
    int calculate(string s) {
        int i = 0;
        s += "+";
        return calc(s, i);
    }

    int calc(const string &s, int &i) { // 用函数调用来模拟栈操作，这里i必须是引用
        char op = '+';
        long n = s.size(), num = 0, curRes = 0, res = 0;
        for (; i < n; ++i) {
            char c = s[i];
            if (isdigit(c)) {
                num = num * 10 + c - '0';
            } else if (c == '(') {
                num = calc(s, ++i);
            } else if (c != ' ') { // +-*/)五种操作符都要运行
                switch (op) {
                    case '+': curRes += num; break;
                    case '-': curRes -= num; break;
                    case '*': curRes *= num; break;
                    case '/': curRes /= num; break;
                }
                if (c == '+' || c == '-' || c == ')') { // 只要不是*/都要对前面进行一次累加操作
                    res += curRes;
                    curRes = 0;
                }
                op = c;
                num = 0;
                if (c == ')') break;
            }
        }
        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
34
35
36
class Solution {
public:
    int calculate(string s) {
        int i = 0;
        s += "+";
        return calc(s, i);
    }

    int calc(const string &s, int &i) { // 用函数调用来模拟栈操作，这里i必须是引用
        char op = '+';
        long n = s.size(), num = 0, curRes = 0, res = 0;
        for (; i < n && op != ')'; ++i) { // 结束条件是op != ')'而不是c != ')'因为即便c是')'也需要用op来进行一步操作
            char c = s[i];
            if (isdigit(c)) {
                num = num * 10 + c - '0';
            } else if (c == '(') {
                num = calc(s, ++i);
                --i; // 因为当op是')'才返回，这时i已经指向了')'的下一个，所以要回退一个
            } else if (c != ' ') { // +-*/)五种操作符都要运行
                switch (op) {
                    case '+': curRes += num; break;
                    case '-': curRes -= num; break;
                    case '*': curRes *= num; break;
                    case '/': curRes /= num; break;
                }
                if (c == '+' || c == '-' || c == ')') { // 只要不是*/都要对前面进行一次累加操作
                    res += curRes;
                    curRes = 0;
                }
                op = c;
                num = 0;
            }
        }
        return res;
    }
};

recursive
worst case O(n2) time
1-2*3 ==> 0+1+-2*3+
遇到左括号找对应的右括号递归处理

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
class Solution {
public:
    int calculate(string s) {
        char op = '+';
        s += "+"; // 补一个+方便操作
        long n = s.size(), num = 0, curRes = 0, res = 0;
        for (int i = 0; i < n; ++i) {
            char c = s[i];
            if (isdigit(c)) {
                num = num * 10 + c - '0';
            } else if (c == '(') {
                int j = i, cnt = 0;
                for (; i < n; ++i) {
                    if (s[i] == '(') ++cnt;
                    if (s[i] == ')') --cnt;
                    if (cnt == 0) break; // 括号匹配
                }
                num = calculate(s.substr(j + 1, i - j - 1));
            } else if (c == '+' || c == '-' || c == '*' || c == '/') {
                switch (op) { // 这个op不是当前的，是之前的，即curRes op num c
                    case '+': curRes += num; break;
                    case '-': curRes -= num; break;
                    case '*': curRes *= num; break;
                    case '/': curRes /= num; break;
                }
                if (c == '+' || c == '-') {
                    res += curRes;
                    curRes = 0;
                }
                op = c;
                num = 0;
            }
        }
        return res;
    }
};

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
class Solution {
public:
    int calculate(string s) {
        s.erase(remove_if(s.begin(), s.end(), [](char c) {return c == ' ';}), s.end()); // 先去掉多余的空格
        s = "(" + s + ")";
        double x = 0;
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            switch (s[i]) {
                case '+': {
                    if (i > 0 && !isdigit(s[i - 1]) && s[i - 1] != ')') {
                        continue;
                    }
                    if (isdigit(s[i - 1])) {
                        opnd.push_back(x);
                        x = 0;
                    }
                    if (!optr.empty() && optr.back() != '(') {
                        eval();
                    }
                    optr.push_back('+');
                }
                    break;
                case '-': {
                    if (i == 0 || s[i - 1] == '(') {
                        optr.push_back('*');
                        opnd.push_back(-1);
                    } else if (s[i - 1] == '+') {
                        optr.back() = '-';
                    } else if (s[i - 1] == '-') {
                        optr.back() = '+';
                    } else if (s[i - 1] == '*' || s[i - 1] == '/') {
                        opnd.back() *= -1;
                    } else if (isdigit(s[i - 1])) {
                        opnd.push_back(x);
                        x = 0;
                        if (!optr.empty() && optr.back() != '(') {
                            eval();
                        }
                        optr.push_back('-');
                    } else {
                        if (!optr.empty() && optr.back() != '(') {
                            eval();
                        }
                        optr.push_back('-');
                    }
                }
                    break;
                case '*':
                case '/': {
                    if (isdigit(s[i - 1])) {
                        opnd.push_back(x);
                        x = 0;
                    }
                    if (!optr.empty() && (optr.back() == '*' || optr.back() == '/')) {
                        eval();
                    }
                    optr.push_back(s[i]);
                }
                    break;
                case '(': {
                    optr.push_back('(');
                }
                    break;
                case ')': {
                    if (isdigit(s[i - 1])) {
                        opnd.push_back(x);
                        x = 0;
                    }
                    while (optr.back() != '(') {
                        eval();
                    }
                    optr.pop_back();
                }
                    break;
                default: {
                    x = x * 10 + s[i] - '0';
                }
                    break;
            }
        }
        return opnd.back();
    }

    void eval() {
        char op = optr.back(); optr.pop_back();
        auto b = opnd.back(); opnd.pop_back();
        auto a = opnd.back(); opnd.pop_back();
        switch (op) {
            case '+': opnd.push_back(a + b); break;
            case '-': opnd.push_back(a - b); break;
            case '*': opnd.push_back(a * b); break;
            case '/': opnd.push_back(floor((double)a / b)); break;
        }
    }

    vector<char> optr;
    vector<double> opnd;
};

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

bfs + dfs O(nm) n是单词个数 m是单词平均长度
这道题的本质是求单源最短路径，应该使用dijkstra算法，这样可以只记录到每个点最短的那些路径，避免把较长的路径也记录下来
dijkstra把从beginWord到其他词（包括endWord）的所有最短路径都找出来（用邻接表）
再用dfs把到endWord的所有最短路径打印出来

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
51
class Solution {
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        unordered_map<string, int> d; // 记录源点到每个点的最短距离
        for (const auto &u : wordList) {
            d[u] = INT_MAX; // 初始化源点到每个点的距离都是无穷大
        }

        unordered_map<string, vector<string>> next;
        queue<string> q; // dijkstra算法本来应该使用优先队列，但是这道题里每次入队列的单词到beginWord的转换步数都是大于等于队列内的其他单词的，所以普通队列即可
        q.push(beginWord);
        d[beginWord] = 0; // 初始化源点到其自己的距离为0
        while (!q.empty()) {
            auto u = q.front();
            q.pop();
            if (u == endWord) break; // 因为只要步数一样就写入图里，所以相当于按层遍历的，最短的可以达到endWord这一层的所有边都已经写到图里了，所以当查看下一层的时候第一次找到endWord就可以跳出循环了
            auto v = u;
            for (auto &&c : v) { // relax
                auto t = c;
                for (char x = 'a'; x <= 'z'; ++x) {
                    c = x;
                    if (x == t || d.count(v) == 0 || d[v] < d[u] + 1) continue; // d[v] < d[u] + 1的意思是v已经访问过了且源点到v的距离应该小于等于源点到u的距离，即v在之前已经可以用更少的转换步数得到，则现在通过u转换得到v的步数不是更少的
                    if (d[v] > d[u] + 1) {
                        d[v] = d[u] + 1;
                        q.push(v);
                    }
                    next[u].push_back(v); // 这里只要u->v不会让到v的最短距离变长就记录下来（因为要找『所有』最短距离，即使d[v] == d[u] + 1也要记录下来），另外因为bfs导致永远是较近的点先被放入，所以一定不会出现先加入『长边』再加入『短边』的情况
                }
                c = t;
            }
        }

        vector<string> v;
        vector<vector<string>> res;
        v.push_back(beginWord);
        dfs(beginWord, endWord, next, v, res);
        return res;
    }

    void dfs(const string &w, const string &e, unordered_map<string, vector<string>> &next, vector<string> &v, vector<vector<string>> &res) {
        if (w == e) {
            res.push_back(v);
            return;
        }
        for (const auto &n : next[w]) {
            v.push_back(n);
            dfs(n, e, next, v, res);
            v.pop_back();
        }
    }
};
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
class Solution {
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        unordered_map<string, int> d;
        for (const auto &w : wordList) {
            d[w] = INT_MAX;
        }
        queue<string> q;
        q.push(beginWord);
        d[beginWord] = 0;
        while (!q.empty()) {
            auto u = q.front(); q.pop();
            if (u == endWord) break;
            auto v = u;
            for (char &c : v) {
                char t = c;
                for (char x = 'a'; x <= 'z'; ++x) {
                    c = x;
                    if (x == t || !d.count(v) || d[v] < d[u] + 1) continue;
                    if (d[v] > d[u] + 1) {
                        d[v] = d[u] + 1;
                        q.push(v);
                    }
                    next[u].push_back(v);
                }
                c = t;
            }
        }
        vs.push_back(beginWord);
        dfs(beginWord, endWord);
        return res;
    }

    void dfs(const string &b, const string &e) {
        if (b == e) {
            res.push_back(vs);
            return;
        }
        for (const auto &n : next[b]) {
            vs.push_back(n);
            dfs(n, e);
            vs.pop_back();
        }
    }

    unordered_map<string, vector<string>> next;
    vector<string> vs;
    vector<vector<string>> res;
};

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

union-find 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
31
class Solution {
public:
    int countComponents(int n, vector<pair<int, int>>& edges) {
        parent.resize(n);
        iota(begin(parent), end(parent), 0);
        res = n;
        for (const auto &e : edges) {
            merge(e.first, e.second);
        }
        return res;
    }

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

    void merge(int x, int y) {
        int px = find(x);
        int py = find(y);
        if (px != py) {
            parent[px] = py;
            --res;
        }
    }

    vector<int> parent;
    int res;
};

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

O(n) stack

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:
    string decodeString(const string &s) {
        stack<int> nums;
        string res;
        for (int i = 0; i < s.length(); ++i) {
            if (isdigit(s[i])) { // 遇到数字直接把整个数拼出来
                int x = 0, j = i;
                for (; j < s.length() && isdigit(s[j]); ++j) {
                    x = x * 10 + s[j] - '0';
                }
                nums.push(x);
                i = j - 1;
            } else if (s[i] == ']') {
                string t;
                while (res.back() != '[') {
                    t += res.back();
                    res.pop_back();
                }
                res.pop_back(); // [出栈
                reverse(begin(t), end(t));
                while (nums.top()-- > 0) {
                    res += t;
                }
                nums.pop(); // 数出栈
            } else { // 字母和[直接压栈
                res += s[i];
            }
        }
        return res;
    }
};

O(n) 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
class Solution {
public:
    string decodeString(string s) {
        int i = 0;
        return helper(s, i);
    }

    string helper(const string &s, int &i) {
        string res;
        for (int n = s.length(); i < n && s[i] != ']'; ++i) {
            if (isdigit(s[i])) {
                int num = 0;
                for (; i < n && isdigit(s[i]); ++i) {
                    num = num * 10 + s[i] - '0';
                }
                auto t = helper(s, ++i); // 跳过[
                while (num-- > 0) {
                    res += t;
                }
            } else {
                res += s[i];
            }
        }
        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
class Solution {
public:
    string decodeString(string s) {
        int i = 0;
        return helper(s, i);
    }

    string helper(const string &s, int &i) {
        string ret;
        while (i < s.length() && s[i] != ']') {
            if (isdigit(s[i])) {
                int num = 0;
                do {
                    num = num * 10 + s[i++] - '0';
                } while (i < s.length() && isdigit(s[i]));
                string t = helper(s, ++i);
                ++i; // 因为helper完最后i会指向上一个]所以需要跳过，放到while循环完最后加也可以
                while (num-- > 0) {
                    ret += t;
                }
            }
            else {
                ret += s[i++];
            }
        }
        return ret;
    }
};

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

这道题考分析，题目要求从1到n每次按其倍数改变灯泡状态，对于灯泡i来说，i的约数要不是偶数个要不是奇数个，奇数个约数的数是完全平方数(square number)，所以题目转变成从1到n找完全平方数的个数，即sqrt(n)
O(logn) time O(1) space

1
2
3
4
5
6
class Solution {
public:
    int bulbSwitch(int n) {
        return sqrt(n);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int bulbSwitch(int n) {
        return mySqrt(n);
    }

    int mySqrt(int n) {
        int lo = 0, hi = n;
        while (lo < hi) {
            long m = (lo + hi + 1) / 2;
            long p = m * m;
            if (p <= n) {
                lo = m;
            } else {
                hi = m - 1;
            }
        }
        return lo;
    }
};

O(sqrt(n)) time O(1) space

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int bulbSwitch(int n) {
        int res = 0;
        for (int i = 1; i * i <= n; ++i) {
            ++res;
        }
        return res;
    }
};

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

DFS O(mn*4k) mn是board的宽和长，k是word长度

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:
    bool exist(vector<vector<char>>& board, string word) {
        if (board.empty() || board[0].empty() || word.empty()) return false;
        m = board.size(), n = board[0].size();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (exist(board, i, j, word, 0)) return true;
            }
        }
        return false;
    }

    bool exist(vector<vector<char>> &board, int i, int j, const string &word, int b) {
        if (b == word.length()) return true;
        if (i < 0 || j < 0 || i >= m || j >= n || board[i][j] != word[b]) return false;
        board[i][j] = '#';
        for (int k = 0; k < 4; ++k) {
            if (exist(board, i + dy[k], j + dx[k], word, b + 1)) return true;
        }
        board[i][j] = word[b];
        return false;
    }

    int m, n, dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0};
};

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

O(1) time O(k) space
用左闭右开区间[b, e)

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
51
52
53
54
55
56
57
58
59
60
61
class MyCircularQueue {
public:
    /** Initialize your data structure here. Set the size of the queue to be k. */
    MyCircularQueue(int k) : k(k) {
        q.resize(k);
    }

    /** Insert an element into the circular queue. Return true if the operation is successful. */
    bool enQueue(int value) {
        if (isFull()) return false;
        q[e] = value;
        e = (e + 1) % k;
        is_empty = false;
        is_full = b == e;
        return true;
    }

    /** Delete an element from the circular queue. Return true if the operation is successful. */
    bool deQueue() {
        if (isEmpty()) return false;
        b = (b + 1) % k;
        is_full = false;
        is_empty = b == e;
        return true;
    }

    /** Get the front item from the queue. */
    int Front() {
        return isEmpty() ? -1 : q[b];
    }

    /** Get the last item from the queue. */
    int Rear() {
        return isEmpty() ? -1 : q[(e + k - 1) % k];
    }

    /** Checks whether the circular queue is empty or not. */
    bool isEmpty() {
        return is_empty;
    }

    /** Checks whether the circular queue is full or not. */
    bool isFull() {
        return is_full;
    }

    int b = 0, e = 0, k;
    vector<int> q;
    bool is_full = false, is_empty = true;
};

/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * MyCircularQueue* obj = new MyCircularQueue(k);
 * bool param_1 = obj->enQueue(value);
 * bool param_2 = obj->deQueue();
 * int param_3 = obj->Front();
 * int param_4 = obj->Rear();
 * bool param_5 = obj->isEmpty();
 * bool param_6 = obj->isFull();
 */

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

topological sort
O(V+E) time O(V+E) space
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
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        visited.resize(numCourses);
        g.resize(numCourses);
        for (const auto &p : prerequisites) {
            g[p[1]].push_back(p[0]);
        }
        for (int i = 0; i < numCourses; ++i) {
            if (visited[i] == 0 && !dfs(i)) return false;
        }
        return true;
    }

    bool dfs(int x) {
        if (visited[x]) return visited[x] == 1;
        visited[x] = -1;
        for (int y : g[x]) {
            if (!dfs(y)) return false;
        }
        visited[x] = 1;
        return true;
    }

    vector<int> visited;
    vector<vector<int>> g; // 邻接链表
};

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

O(n) time
要确认一下单词长度是否会超过limit

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:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        vector<string> res;
        for (int i = 0, n = words.size(); i < n;) {
            int cnt = 0, len = 0;
            while (i + cnt < n && len + words[i + cnt].length() + cnt <= maxWidth) { // 统计这一行所有单词的总长度以及个数
                len += words[i + cnt].length();
                ++cnt;
            }
            string line = words[i];
            for (int j = 1; j < cnt; ++j) {
                if (i + cnt >= n) { // 如果是最后一行，每个单词之间一个空格即可
                    line += " ";
                } else { // 否则按照下面的逻辑放空格，先平均放一样的空格数(maxWidth - len) / (cnt - 1)然后剩余的(maxWidth - len) % (cnt -1)个空格从前往后每个位置加一个，加完为止
                    line.append((maxWidth - len) / (cnt - 1) + (j <= (maxWidth - len) % (cnt - 1)), ' ');
                }
                line += words[i + j];
            }
            line.append(maxWidth - line.length(), ' '); // 不管是长单词单独一行还是最后一行，补齐空格
            res.push_back(line);
            i += cnt;
        }
        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
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        int n = words.size(), cnt = -1; // cnt初始化为-1因为开始第一个单词前边不用加空格
        vector<int> indices; // 把每一行的单词的下标存起来
        vector<string> res;
        for (int i = 0; i < n; ++i) {
            if (cnt + 1 + words[i].length() <= maxWidth) { // 如果当前的单词能放在这一行上
                cnt += 1 + words[i].length(); // 加一个空格和当前单词
                indices.push_back(i); // 把当前单词的下标存起来
            } else {
                stack<int> spaces; // 计算每个单词前边的空格个数
                int slots = indices.size() - 1, total = maxWidth - cnt + slots; // 初始化有多少个位置要放空格以及这一行总的空格个数
                string s = words[indices[0]];
                if (slots == 0) { // 如果只有一个单词（超长单词）直接放即可
                    s.append(total, ' ');
                } else { // 如果不止一个单词
                    while (total > 0) { // 从后往前算平均数，比如18个空格5个单词，四个位置空格数分别为[5, 5, 4, 4]
                        int space = total / slots--;
                        spaces.push(space);
                        total -= space;
                    }
                    for (int j = 1; j < indices.size(); ++j) { // 算好空格数以后开始拼这行
                        s.append(spaces.top(), ' ').append(words[indices[j]]);
                        spaces.pop();
                    }
                }
                res.push_back(s);
                cnt = words[i].length(); // 结束这行以后cnt为当前单词长度，因为words[i]被挤下来了
                indices = {i}; // 结束这行以后indices放入当前单词下标
            }
            if (i == n - 1) { // 如果是最后一个单词，则肯定是最后一行，不计算空格数，直接放即可
                string s = words[indices[0]];
                for (int j = 1; j < indices.size(); ++j) {
                    s += " " + words[indices[j]];
                }
                s += string(maxWidth - s.length(), ' '); // 最后要补足空格
                res.push_back(s);
            }
        }
        return res;
    }
};

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

这个题要看数的范围能不能用rolling hash，不行的话就得用dp
bisection+rolling hash O((m + n)log(min(m, n))) time O(m + n) space
思路就是二分可能的非法结果，找到第一个（最小的）非法结果，即能找到最大的合法结果，对每个非法结果（长度），分别枚举两个数组的子数组进行比对，这里引入rolling hash来加速，即把第一个数组的指定长度的子数组的rolling hash记录下来，再分别计算第二个数组的子数组的rolling hash值进行比对，如果能找到一致的值再挨个比对两个子数组的每个数

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
51
class Solution {
public:
    int findLength(vector<int>& A, vector<int>& B) {
        m = A.size(), n = B.size();
        int lo = 1, hi = min(m, n) + 1; // find first INVALID length，因为可能的合法结果是从0到min(m, n)，所以不合法结果的范围整体偏移1，目的是方便写二分，如果正常二分枚举合法结果，最后要不死循环，要不就得最后单独再判断一次
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (isValid(A, B, mid)) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo - 1;
    }

    bool isValid(const vector<int> &A, const vector<int> &B, int len) {
        long hi_pow = 1, ah = 0, bh = 0;
        for (int i = 0; i < len - 1; ++i) { // 这里求的是base的len - 1次方
            hi_pow = hi_pow * base % M;
            ah = (ah * base + A[i]) % M;
            bh = (bh * base + B[i]) % M;
        }
        unordered_map<long, vector<int>> table;
        for (int i = len - 1; i < m; ++i) {
            if (i >= len) {
                ah = (ah + (M - A[i - len]) * hi_pow) % M; // 这里为了避免产生负数要单独处理
            }
            ah = (ah * base + A[i]) % M;
            table[ah].push_back(i - len + 1);
        }
        for (int i = len - 1; i < n; ++i) {
            if (i >= len) {
                bh = (bh + (M - B[i - len]) * hi_pow) % M;
            }
            bh = (bh * base + B[i]) % M;
            if (table.count(bh)) {
                for (int j : table[bh]) {
                    int k = 0;
                    for (; k < len; ++k) {
                        if (A[j + k] != B[i - len + 1 + k]) break;
                    }
                    if (k == len) return true;
                }
            }
        }
        return false;
    }

    int m, n, M = INT_MAX, base = 100; // 这道题所有数都小于100，否则不能这么用
};

dp O(mn) time O(mn) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int findLength(vector<int>& A, vector<int>& B) {
        int m = A.size(), n = B.size();
        vector<vector<int>> f(m + 1, vector<int>(n + 1));
        int res = 0;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (A[i - 1] == B[j - 1]) {
                    f[i][j] = f[i - 1][j - 1] + 1;
                }
                res = max(res, f[i][j]);
            }
        }
        return res;
    }
};