LeetCode「Hard」问题题解（1～100）

发表于 分类于 阅读次数：

4. Median of Two Sorted Arrays

问题等价为找 nums1 和 nums2 的第 k 大，用递归解决：

  1. 如果 k = 1，递归结束，返回 min(nums1[0], nums2[0])；
  2. 比较 nums1[k / 2 - 1] 和 nums2[k / 2 - 1]：
    • 如果 nums1[k / 2 - 1] <= nums2[k / 2 - 1]，则第 k 大的数一定不落在nums1[0 … k / 2 - 1] 中，删除nums1[0 … k / 2 - 1]；
    • 反之同理，删除nums2[0 … k / 2 - 1]。
  3. k -= k / 2。

时间复杂度 O(log(m + n))，运行时间 49 ms。

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 {
    
    int findKth(vector<int>& nums1, int m, vector<int>& nums2, int n, int k) {
        int h1 = 0, h2 = 0;
        while (true) {
            if (h1 == m) return nums2[h2 + k - 1];
            if (h2 == n) return nums1[h1 + k - 1];
            if (k == 1) return min(nums1[h1], nums2[h2]);
            int le = h1 + k / 2 - 1 < m ? nums1[h1 + k / 2 - 1] : INT_MAX;
            int ri = h2 + k / 2 - 1 < n ? nums2[h2 + k / 2 - 1] : INT_MAX;
            if (le <= ri)
                h1 += k / 2;
            else
                h2 += k / 2;
            k -= k / 2;
        }
    }
    
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        if ((m + n) & 1)
            return findKth(nums1, m, nums2, n, (m + n) / 2 + 1);
        return (findKth(nums1, m, nums2, n, (m + n) / 2) + findKth(nums1, m, nums2, n, (m + n) / 2 + 1)) * 0.5;
    }
};

10. Regular Expression Matching

动态规划，f[i][j] 表示字符串 s 的前 i 位与字符串 p 的前 j 位的匹配情况。

时间复杂度 O(m * n)，运行时间 9 ms。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.length(), n = p.length();
        vector<vector<bool>> f(m + 1, vector<bool>(n + 1, false));
        f[0][0] = true;
        for (int i = 0; i <= m; ++i)
            for (int j = 1; j <= n; ++j)
                if (p[j - 1] == '*')
                    f[i][j] = f[i][j - 2] || (i > 0 && f[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'));
                else
                    f[i][j] = i > 0 && f[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
        return f[m][n];
    }
};

23. Merge k Sorted Lists

把每个链表的头放到单调队列中，每次从中取出最小的数，再加入该列表的下一个数。

时间复杂度 O(m * log(n))，运行时间 188 ms。

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
    struct cmp {
        bool operator() (ListNode *a, ListNode *b) {
            return a->val > b->val;
        }
    };
    
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        priority_queue<ListNode *, vector<ListNode *>, cmp> q;
        int n = lists.size();
        for (int i = 0; i < n; ++i)
            if (lists[i] != NULL)
                q.push(lists[i]);
        if (q.empty()) return NULL;
        ListNode *ans, *p, *a;
        a = q.top(); q.pop();
        if (a->next != NULL) q.push(a->next);
        ans = p = new ListNode(a->val);
        while (!q.empty()) {
            a = q.top(); q.pop();
            if (a->next != NULL) q.push(a->next);
            p->next = new ListNode(a->val);
            p = p->next;
        }
        return ans;
    }
};

25. Reverse Nodes in k-Group

模拟。

运行时间 132 ms。

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *reverseKGroup(ListNode *head, int k) {
        if (head == NULL) return NULL;
        int n = 0;
        ListNode *p = head;
        while (p != NULL) {
            ++n;
            p = p->next;
        }
        int group = n / k;
        ListNode **b;
        b = new ListNode*[k];
        ListNode *pre, *ans;
        ans = pre = p = head;
        for (int i = 0; i < group; ++i) {
            for (int j = 0; j < k; ++j) {
                b[j] = p;
                p = p->next;
            }
            b[0]->next = p;
            for (int j = 0; j + 1 < k; ++j)
                b[j + 1]->next = b[j];
            if (i == 0)
                ans = b[k - 1];
            else
                pre->next = b[k - 1];
            pre = b[0];
        }
        return ans;
    }
};

30. Substring with Concatenation of All Words

从前往后扫描，维护长度为所有单词长度和的字符串里包含单词表单词的情况，如果符合条件，统计进答案。

变量说明：

  • idx[w] – 单词 w 的编号
  • wc – 单词个数（不包括重复单词）
  • dest[i] – 编号为 i 的单词的个数

时间复杂度 O(n)，运行时间 29 ms。

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<int> findSubstring(string s, vector<string>& words) {
        vector<int> ans;
        int n = s.length();
        int m = words.size();
        if (n == 0 || m == 0) return ans;
        int len = words[0].length();
        int full_len = m * len;
        unordered_map<string, int> idx;
        vector<int> dest(m, 1);
        int wc = m;
        for (int i = 0; i < m; ++i)
            if (idx.count(words[i])) {
                ++dest[idx[words[i]]];
                --wc;
            } else
                idx[words[i]] = i;
        for (int i = 0; i < len; ++i) {
            vector<int> cnt(m, 0);
            int tmp = 0;
            for (int j = i; j + len <= n; j += len) {
                auto cur = s.substr(j, len);
                if (idx.count(cur)) {
                    if (cnt[idx[cur]] == dest[idx[cur]]) --tmp;
                    if (++cnt[idx[cur]] == dest[idx[cur]])
                        ++tmp;
                }
                if (j >= full_len) {
                    auto pre = s.substr(j - full_len, len);
                    if (idx.count(pre)) {
                        if (cnt[idx[pre]] == dest[idx[pre]]) --tmp;
                        if (--cnt[idx[pre]] == dest[idx[pre]])
                            ++tmp;
                    }
                }
                if (tmp == wc) ans.push_back(j - full_len + len);
            }
        }
        sort(ans.begin(), ans.end());
        return ans;
    }
};

32. Longest Valid Parentheses

从前往后扫描一遍字符串进行括号匹配即可，标记匹配成功的字符位置，因为合法的圆括号串中每一位都匹配成功，所以答案是寻找最长的连续被标记匹配成功的字符串。

时间复杂度 O(n)，运行时间 12 ms。

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:
    int longestValidParentheses(string s) {
        int n = s.length();
        stack<int> st;
        vector<bool> match(n, false);
        for (int i = 0; i < n; ++i)
            if (s[i] == '(')
                st.push(i);
            else
                if (!st.empty()) {
                    match[i] = match[st.top()] = true;
                    st.pop();
                }
        
        int ans = 0, tmp = 0;
        for (int i = 0; i < n; ++i)
            if (match[i])
                ++tmp;
            else {
                if (tmp > ans) ans = tmp;
                tmp = 0;
            }
        if (tmp > ans) ans = tmp;
        return ans;
    }
};

37. Sudoku Solver

位运算优化的 dfs 算法。

变量说明：

  • r[x] – 第 x 行的已确定数字
  • c[y] – 第 y 列的已确定数字
  • b[i] – 第 i 个九宫格的已确定数字

运行时间 6 ms。

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
class Solution {
    int nextx[9][9], nexty[9][9], g[9][9];
    int r[9], c[9], b[9];
    
    bool dfs(vector<vector<char> > &a, int x, int y) {
        if (x == 9) return true;
        int t, v;
        t = ((1 << 9) - 1) & ~(r[x] | c[y] | b[g[x][y]]);
        while (t) {
            v = (int)(log(t - (t & (t - 1))) / log(2) + 0.5);
            a[x][y] = '1' + v;
            r[x] |= 1 << v;
            c[y] |= 1 << v;
            b[g[x][y]] |= 1 << v;
            if (dfs(a, nextx[x][y], nexty[x][y])) return true;
            r[x] &= ~(1 << v);
            c[y] &= ~(1 << v);
            b[g[x][y]] &= ~(1 << v);
            t = t & (t - 1);
        }
        a[x][y] = '.';
        return false;
    }
    
public:
    void solveSudoku(vector<vector<char> > &board) {
        for (int i = 0; i < 9; ++i)
            for (int j = 0; j < 9; ++j)
                g[i][j] = i / 3 * 3 +  j / 3;
        memset(r, 0, sizeof(r));
        memset(c, 0, sizeof(c));
        memset(b, 0, sizeof(b));
        int px = -1, py = -1, hx = 9, hy;
        for (int i = 0; i < 9; ++i)
            for (int j = 0; j < 9; ++j)
                if (board[i][j] == '.') {
                    nextx[i][j] = 9;
                    if (px != -1) {
                        nextx[px][py] = i;
                        nexty[px][py] = j;
                    } else {
                        hx = i;
                        hy = j;
                    }
                    px = i; py = j;
                } else {
                    r[i] |= 1 << (board[i][j] - '1');
                    c[j] |= 1 << (board[i][j] - '1');
                    b[g[i][j]] |= 1 << (board[i][j] - '1');
                }
        dfs(board, hx, hy);
    }
};

41. First Missing Positive

可以使用 O(n) 空间的一位数组作为桶，统计 1～n 的出现情况。由于 O(1) 空间的要求，使用原数组作为桶。

运行时间 3 ms。

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

42. Trapping Rain Water

每个 bar 可以蓄水的高度由它往左的最高的 bar 和往右最高的 bar 决定，遍历 height 数组两次即可求得。

运行时间 9 ms。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        vector<int> f(height);
        for (int i = 0, cur_max = 0; i < n; ++i) {
            if (height[i] > cur_max) cur_max = height[i];
            f[i] = cur_max;
        }
        for (int i = n - 1, cur_max = 0; i >= 0; --i) {
            if (height[i] > cur_max) cur_max = height[i];
            if (cur_max < f[i]) f[i] = cur_max;
        }
        
        int ans = 0;
        for (int i = 0; i < n; ++i)
            ans += f[i] - height[i];
        return ans;
    }
};

44. Wildcard Matching

方法一

动态规划，f[i][j] 表示字符串 s 的前 i 位与字符串 p 的前 j 位的匹配情况。

时间复杂度 O(m * n)，运行时间 102 ms。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.length(), n = p.length();
        vector<vector<bool>> f(m + 1, vector<bool>(n + 1, false));
        f[0][0] = true;
        for (int i = 0; i <= m; ++i)
            for (int j = 1; j <= n; ++j)
                if (p[j - 1] == '*')
                    f[i][j] = f[i][j - 1] || (i > 0 && f[i - 1][j]);
                else
                    f[i][j] = i > 0 && f[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '?');
        return f[m][n];
    }
};

方法二

既然 * 可以匹配任意个字符，只需要记录当前匹配位置的最近的一个 * 的位置即可。

运行时间 25 ms。

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 isMatch(const char *s, const char *p) {
        const char *pre_s = NULL;
        const char *pre_p = NULL;
        while (*s) {
            if (*s == *p || *p == '?') {
                ++s;
                ++p;
            }
            else if (*p == '*') {
                pre_s = s;
                pre_p = ++p;
            }
            else {
                if (pre_s == NULL)
                    break;
                s = ++pre_s;
                p = pre_p;
            }
        }
        while (*p == '*') ++p;
        if (*s || *p) return false;
        return true;
    }
};

45. Jump Game II

贪心策略，每次跳到能跳到最远的地方。

时间复杂度 O(n)，运行时间 21 ms。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int jump(int A[], int n) {
        int ans = 0;
        int cur, h, t, next_ind;
        for (cur = 0, h = 1, t, next_ind; cur + A[cur] < n - 1; cur = next_ind, ++ans) {
            t = cur + A[cur];
            if (t >= n) t = n - 1;
            next_ind = h;
            while (h <= t) {
                if (A[h] + h >= A[next_ind] + next_ind)
                    next_ind = h;
                ++h;
            }
        }
        if (cur != n - 1) ++ans;
        return ans;
    }
};

51. N-Queens

把原问题转化为求 1～n 的排列，表示每一行的皇后的位置，dfs 算法，保证每条斜线上最多只有一个皇后。

运行时间 8 ms。

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 {
    int n;
    vector<string> map;
    vector<vector<string>> ans;
    vector<int> a;
    vector<bool> bx, by;
    
    void dfs(int i, int n) {
        if (i == n) {
            ans.push_back(map);
            return;
        }
        for (int j = i; j < n; ++j)
            if (!bx[i + a[j]] && !by[i - a[j] + n]) {
                bx[i + a[j]] = by[i - a[j] + n] = true;
                map[i][a[j]] = 'Q';
                swap(a[i], a[j]);
                dfs(i + 1, n);
                swap(a[i], a[j]);
                bx[i + a[j]] = by[i - a[j] + n] = false;
                map[i][a[j]] = '.';
            }
    }
public:
    vector<vector<string> > solveNQueens(int n) {
        map = vector<string>(n, string(n, '.'));
        for (int i = 0; i < n; ++i)
            a.push_back(i);
        bx.resize(n << 1);
        fill(begin(bx), end(bx), false);
        by.resize(n << 1);
        fill(begin(by), end(by), false);
        dfs(0, n);
        return ans;
    }
};

52. N-Queens II

同 51. N-Queens。

运行时间 4 ms。

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 {
    int n, ans;
    vector<int> a;
    vector<bool> bx, by;
    
    void dfs(int i, int n) {
        if (i == n) {
            ++ans;
            return;
        }
        for (int j = i; j < n; ++j)
            if (!bx[i + a[j]] && !by[i - a[j] + n]) {
                bx[i + a[j]] = by[i - a[j] + n] = true;
                swap(a[i], a[j]);
                dfs(i + 1, n);
                swap(a[i], a[j]);
                bx[i + a[j]] = by[i - a[j] + n] = false;
            }
    }
public:
    int totalNQueens(int n) {
        for (int i = 0; i < n; ++i)
            a.push_back(i);
        bx.resize(n << 1);
        fill(begin(bx), end(bx), false);
        by.resize(n << 1);
        fill(begin(by), end(by), false);
        dfs(0, n);
        return ans;
    }
};

57. Insert Interval

分两步：

  1. 删除被 newInterval 覆盖的 interval。
  2. 更新因 newInterval 而扩展的 interavl。

时间复杂度 O(n)，运行时间 16 ms。

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
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
        vector<Interval> ans;
        vector<Interval>::iterator it;
        for (it = begin(intervals); it != end(intervals); ++it) {
            if (it->start <= newInterval.start && newInterval.end <= it->end)
                return intervals;
            if (!(newInterval.start <= it->start && it->end <= newInterval.end))
                ans.push_back(*it);
        }
        vector<Interval>::iterator h, t;
        h = t = end(ans);
        for (it = begin(ans); it != end(ans) && it->start <= newInterval.end; ++it) {
            if (it->start <= newInterval.start && newInterval.start <= it->end)
                h = it;
            if (it->start <= newInterval.end && newInterval.end <= it->end)
                t = it;
        }
        if (h != end(ans) && t != end(ans)) {
            h->end = t->end;
            ans.erase(t);
        } else
        if (h != end(ans)) {
            h->end = newInterval.end;
        } else
        if (t != end(ans)) {
            t->start = newInterval.start;
        } else {
            for (it = begin(ans); it != end(ans); ++it)
                if (it->start > newInterval.end) {
                    ans.insert(it, newInterval);
                    break;
                }
            if (it == end(ans))
                ans.push_back(newInterval);
        }
        return ans;
    }
};

65. Valid Number

方法一 DEPRECATED

忽略前后的空格，分两类判断：普通数字（包括负数和小数），科学计数法数字。

运行时间 9 ms。

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
class Solution {
    
    bool isPureNumber(string s, bool allowDot = true) {
        if (s[0] == '+' || s[0] == '-') s.erase(0, 1);
        bool num = false;
        bool dot = false;
        for (char ch : s) {
            if (ch >= '0' && ch <= '9')
                num = true;
            else
            if (ch == '.') {
                if (!allowDot) return false;
                if (dot) return false;
                dot = true;
            }
            else
                return false;
        }
        return num;
    }
    
    bool isENumber(string s) {
        auto p = s.find('e');
        if (p == string::npos) return false;
        return isPureNumber(s.substr(0, p)) && isPureNumber(s.substr(p + 1), false);
    }
    
public:
    bool isNumber(string s) {
        while (s[0] == ' ') s.erase(0, 1);
        while (s[s.length() - 1] == ' ') s.erase(s.length() - 1);
        return isPureNumber(s) || isENumber(s);
    }
};

方法二

后来想到的，直接用正则表达式，代码很清晰。

1
2
3
4
5
6
7
8
func isNumber(s string) bool {
    integer := `[+-]?\d+`
    real := `[+-]?(\d+\.\d*|\d*\.\d+)`
    science := fmt.Sprintf("(%s|%s)[eE]%s", integer, real, integer)
    combined := fmt.Sprintf("^ *(%s|%s|%s) *$", integer, real, science)
    m, _ := regexp.MatchString(combined, s)
    return m
}

68. Text Justification

模拟。

运行时间 0 ms。

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
class Solution {
    int minLen(vector<string>::iterator it1, vector<string>::iterator it2) {
        int ret = 0;
        for (auto it = it1; it != it2; ++it) {
            ret += (*it).length();
            if (it != it1) ++ret;
        }
        return ret;
    }
    
    string makeWords(vector<string>::iterator it1, vector<string>::iterator it2, const int& limit) {
        string ret = *it1;
        int k = it2 - it1 - 1;
        int left = limit;
        for (auto it = it1; it != it2; ++it)
            left -= (*it).length();
        if (k == 0) return ret + string(left, ' ');
        string small = string(left / k, ' ');
        string big = small + ' ';
        int big_left = left % k;
        for (auto it = it1 + 1; it != it2; ++it) {
            if (big_left) {
                ret += big;
                --big_left;
            } else
                ret += small;
            ret += *it;
        }
        return ret;
    }
    
    string makeLastWords(vector<string>::iterator it1, vector<string>::iterator it2, const int& limit) {
        string ret = *it1;
        for (auto it = it1 + 1; it != it2; ++it) {
            ret += ' ';
            ret += *it;
        }
        ret += string(limit - ret.length(), ' ');
        return ret;
    }
    
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        vector<string> ans;
        if (words.empty()) return ans;
        auto last = begin(words);
        for (auto it = begin(words) + 1; it != end(words); ++it)
            if (minLen(last, it + 1) > maxWidth) {
                ans.push_back(makeWords(last, it, maxWidth));
                last = it;
            }
        ans.push_back(makeLastWords(last, end(words), maxWidth));
        return ans;
    }
};

72. Edit Distance

动态规划，f[i][j] 表示 word1 的前 i 位与 word2 的前 j 位匹配所需的最少操作数。

时间复杂度 O(m * n)，运行时间 9 ms。

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 minDistance(string word1, string word2) {
        int n = word1.length();
        int m = word2.length();
        if (n == 0 || m == 0) return n + m;
        vector<vector<int>> f = vector<vector<int>>(n + 1, vector<int>(m + 1, max(n, m) + 2));
        f[0][0] = 0;
        for (int i = 1; i <= n; ++i)
            f[i][0] = i;
        for (int i = 1; i <= m; ++i)
            f[0][i] = i;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j) {
                if (word1[i - 1] == word2[j - 1])
                    f[i][j] = f[i - 1][j - 1];
                else
                    f[i][j] = f[i - 1][j - 1] + 1;
                f[i][j] = min(f[i][j], min(f[i][j - 1], f[i - 1][j]) + 1);
            }
        return f[n][m];
    }
};

76. Minimum Window Substring

从左往右扫描一遍字符串 s，维护出现的字母的计数器。

时间复杂度 O(n)，运行时间 12 ms。

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 {
    int pcnt[256], cnt[256];
    int types;

    void add(char ch) {
        if (pcnt[ch])
            if (++cnt[ch] == pcnt[ch])
                types += pcnt[ch];
    }

    void remove(char ch) {
        if (pcnt[ch])
            if (cnt[ch]-- == pcnt[ch])
                types -= pcnt[ch];
    }

public:
    string minWindow(string s, string t) {
        if (t == "") return "";
        memset(pcnt, 0, sizeof(pcnt));
        memset(cnt, 0, sizeof(cnt));
        types = 0;
        int ls = s.length();
        int lt = t.length();
        for (int i = 0; i < lt; ++i)
            ++pcnt[t[i]];
        int a_h, a_len = ls + 1;
        for (int head = 0, tail = 0; tail < ls; ++tail) {
            add(s[tail]);
            while (types == lt) {
                if (tail - head + 1 < a_len) {
                    a_len = tail - head + 1;
                    a_h = head;
                }
                remove(s[head++]);
            }
        }
        if (a_len == ls + 1) return "";
        return s.substr(a_h, a_len);
    }
};

84. Largest Rectangle in Histogram

最优情况下，矩形的高度一定是某一个 bar 的高度，计算每个 bar 向左向右能延伸的矩形的最大长度。f[i] 表示高度为 height[i] 且右端位于 i 的矩形的最大面积，g[i] 表示高度为 height[i] 且左端位于 i 的矩形的最大面积，最终答案为 max{f[i] + g[i] - height[i]}。

时间复杂度 O(n)，运行时间 32 ms。

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 {
    void dp(vector<int>& height, vector<int>& f) {
        int n = height.size();
        stack<pair<int, int>> st;
        st.push(make_pair(-1, -1));
        for (int i = 0; i < n; ++i) {
            while (height[i] <= st.top().second)
                st.pop();
            f[i] = (i - st.top().first) * height[i];
            st.push(make_pair(i, height[i]));
        }
    }
    
public:
    int largestRectangleArea(vector<int>& height) {
        int n = height.size();
        if (n == 0) return 0;
        vector<int> f, g;
        f.resize(n);
        g.resize(n);
        dp(height, f);
        reverse(begin(height), end(height));
        dp(height, g);
        int ans = 0;
        for (int i = 0; i < n; ++i)
            ans = max(ans, f[i] - height[n - 1 -i] + g[n - 1 - i]);
        return ans;
    }
};

85. Maximal Rectangle

同 84. Largest Rectangle in Histogram。

时间复杂度 O(m * n)，运行时间 23 ms。

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
class Solution {
    int m, n;
    vector<int> h, f, g;
    
    void dp(vector<int>& f) {
        stack<pair<int, int>> st;
        st.push(make_pair(-1, -1));
        for (int i = 0; i < n; ++i) {
            while (h[i] <= st.top().second)
                st.pop();
            f[i] = (i - st.top().first) * h[i];
            st.push(make_pair(i, h[i]));
        }
    }
    
    int dp() {
        dp(f);
        reverse(begin(h), end(h));
        dp(g);
        reverse(begin(h), end(h));
        int ret = 0;
        for (int i = 0; i < n; ++i)
            ret = max(ret, f[i] - h[i] + g[n - 1 - i]);
        return ret;
    }
    
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        m = matrix.size();
        if (m == 0) return 0;
        n = matrix[0].size();
        if (n == 0) return 0;
        h.resize(n);
        f.resize(n);
        g.resize(n);
        for (int i = 0; i < n; ++i)
            h[i] = matrix[0][i] - '0';
        int ans = dp();
        for (int i = 1; i < m; ++i) {
            for (int j = 0; j < n; ++j)
                h[j] = matrix[i][j] == '1' ? h[j] + 1 : 0;
            ans = max(ans, dp());
        }
        return ans;
    }
};

87. Scramble String

dfs 算法，建立数据结构 CP 判断字符串字符组成是否相同。

运行时间 4 ms。

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
class Solution {
    int n;
    
    struct CP {
        int cnt[256];
        int diff;
        
        CP() {
            memset(cnt, 0, sizeof(cnt));
            diff = 0;
        }
        
        void add(const char& c) {
            if (cnt[c]++ == 0) ++diff;
            if (cnt[c] == 0) --diff;
        }
        
        void remove(const char& c) {
            if (cnt[c]-- == 0) ++diff;
            if (cnt[c] == 0) --diff;
        }
    };
    
    bool scramble(const string& s1, int h1, const string& s2, int h2, int len) {
        if (len <= 2) return true;
        unique_ptr<CP> cp1(new CP());
        unique_ptr<CP> cp2(new CP());
        for (int i = 1; i < len; ++i) {
            cp1->add(s1[h1 - 1 + i]);
            cp2->add(s1[h1 - 1 + i]);
            cp1->remove(s2[h2 - 1 + i]);
            cp2->remove(s2[h2 + len - i]);
            if (cp1->diff == 0 && scramble(s1, h1, s2, h2, i) && scramble(s1, h1 + i, s2, h2 + i, len - i))
                return true;
            if (cp2->diff == 0 && scramble(s1, h1, s2, h2 + len - i, i) && scramble(s1, h1 + i, s2, h2, len - i))
                return true;
        }
        return false;
    }
    
public:
    bool isScramble(string s1, string s2) {
        n = s1.length();
        if (n == 0) return true;
        unique_ptr<CP> cp(new CP());
        for (int i = 0; i < n; ++i) {
            cp->add(s1[i]);
            cp->remove(s2[i]);
        }
        if (cp->diff != 0) return false;
        return scramble(s1, 0, s2, 0, n);
    }
};

97. Interleaving String

动态规划，f[i][j] 表示 s1 的前 i 位与 s2 的前 j 位能否组合成 s3 的前 i + j 位。

时间复杂度 O(m * n)，运行时间 8 ms。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int n = s1.length();
        int m = s2.length();
        if (n + m != s3.length()) return false;
        vector<vector<bool>> f(n + 1, vector<bool>(m + 1, false));
        f[0][0] = true;
        for (int i = 0; i <= n; ++i)
            for (int j = 0; j <= m; ++j)
                if (f[i][j] && i + j < n + m) {
                    if (s1[i + 1 - 1] == s3[i + 1 + j - 1])
                        f[i + 1][j] = true;
                    if (s2[j + 1 - 1] == s3[i + j + 1 - 1])
                        f[i][j + 1] = true;
                }
        return f[n][m];
    }
};

99. Recover Binary Search Tree

顺序遍历树找到两个异常节点。

时间复杂度 O(n)，运行时间 48 ms。

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
/**
 * 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 {
    TreeNode* pre;
    TreeNode* p1;
    TreeNode* p2;
    
    void go(TreeNode* x) {
        if (x->left != NULL) go(x->left);
        if (pre != NULL && pre->val > x->val) {
            if (p1 == NULL) {
                p1 = pre;
                p2 = x;
            } else
                p2 = x;
        }
        pre = x;
        if (x->right != NULL) go(x->right);
    }
    
    void swap(int &a, int &b) {
        int c = a;
        a = b;
        b = c;
    }
    
public:
    void recoverTree(TreeNode* root) {
        pre = p1 = p2 = NULL;
        go(root);
        swap(p1->val, p2->val);
    }
};
0%