LeetCode「Hard」问题题解（101～200）

115. Distinct Subsequences

动态规划，f[i][j] 表示 S 的前 i 位形成 T 的前 j 位的子序列的数目。

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

class Solution {
public:
    int numDistinct(string s, string t) {
        int n = s.length(), m = t.length();
        vector<vector<int> > f(n + 1, vector<int>(m + 2));
        f[0][0] = 1;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j <= m; ++j) {
                f[i + 1][j] += f[i][j];
                if (s[i] == t[j])
                    f[i + 1][j + 1] += f[i][j];
            }
        return f[n][m];
    }
};

123. Best Time to Buy and Sell Stock III

枚举切分点，把股票分成前后两段，计算前后两段中单次买卖获得的最大收益。

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

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        int n = prices.size();
        if (n <= 1) return 0;
        vector<int> h(n);
        h[0] = 0;
        int _min = prices[0];
        for (int i = 1; i < n; ++i) {
            if (prices[i] < _min) _min = prices[i];
            h[i] = max(h[i - 1], prices[i] - _min);
        }
        int ans = 0;
        int t = 0;
        int _max = prices[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            if (prices[i] > _max) _max = prices[i];
            t = max(t, _max - prices[i]);
            ans = max(ans, h[i] + t);
        }
        return ans;
    }
};

124. Binary Tree Maximum Path Sum

dfs 遍历树，run(x) 函数返回结果为以结点 x 开头的向下延伸的链的最大路径和。

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

/**
 * 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 {
    int ans;
    
    int run(TreeNode* x) {
        if (x == NULL) return 0;
        int l = run(x->left);
        int r = run(x->right);
        int ret = x->val;
        if (l + x->val > ret)
            ret = l + x->val;
        if (r + x->val > ret)
            ret = r + x->val;
        if (ret > ans) ans = ret;
        if (l + x->val + r > ans)
            ans = l + x->val + r;
        return ret;
    }
    
public:
    int maxPathSum(TreeNode* root) {
        ans = root->val;
        run(root);
        return ans;
    }
};

126. Word Ladder II

bfs 搜索路径。

时间复杂度 O(n ^ 2)，运行时间 629 ms。

class Solution {

    vector<int> f[2];
    int n, width;
    vector<vector<string>> ans;

    bool check(const string& a, const string& b) {
        int c = 0;
        int l = a.length();
        for (int i = 0; i < l; ++i)
            if (a[i] != b[i])
                if (++c > 1)
                    return false;
        return true;
    }

    void gen_ans(int cur, int dest, vector<string>& tmp, vector<string>& wordList) {
        if (cur == dest) {
            ans.push_back(tmp);
            return;
        }
        for (int i = 0; i < n; ++i)
            if (cur != i && f[0][cur] + f[1][i] == width && check(wordList[cur], wordList[i])) {
                tmp.push_back(wordList[i]);
                gen_ans(i, dest, tmp, wordList);
                tmp.pop_back();
            }
    }

public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        n = wordList.size();
        int pt = -1;
        for (int i = 0; i < n; ++i)
            if (wordList[i] == endWord) {
                pt = i;
                break;
            }
        if (pt == -1) return ans;
        wordList.push_back(beginWord);
        f[0].resize(n + 5, 0);
        f[1].resize(n + 5, 0);
        int* q[2]{new int[n + 5]{n}, new int[n + 5]{pt}};
        int* h = new int[2]{0, 0};
        int* t = new int[2]{1, 1};
        int o = 0;
        int step = 1;
        width = n + 5;
        f[0][n] = 1; f[1][pt] = 1;
        while (step < width) {
            int limit = t[o];
            while (h[o] < limit) {
                int i = q[o][h[o]++];
                if (f[o ^ 1][i] > 0 && step + f[o ^ 1][i] - 1 < width)
                    width = step + f[o ^ 1][i] - 1;
                for (int j = 0; j < n; ++j)
                    if (f[o][j] == 0 && check(wordList[i], wordList[j])) {
                        f[o][j] = step + 1;
                        q[o][t[o]++] = j;
                    }
            }
            o ^= 1;
            if (o == 0) ++step;
        }
        if (width == n + 5) return ans;
        vector<string> tmp{beginWord};
        gen_ans(n, pt, tmp, wordList);
        return ans;
    }
};

128. Longest Consecutive Sequence

方法一

哈希，使用 STL 库的 unordered_set 非常方便。

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

class Solution {
    
    const int H1 = 8191;
    const int H2 = 11971;
    const int MOD = 131071;
    
    int hash(long long x) {
        int r = (x * H1 + H2) % MOD;
        return r < 0 ? r + MOD : r;
    }
    
    int tot;
    vector<int> prev;
    vector<int> ind, v, next;
    vector<bool> vis;
    
    void add(int a, int b, int c) {
        // cout << "add " << a << " " << b << " " << c << endl;
        ind.push_back(b);
        v.push_back(c);
        next.push_back(prev[a]);
        prev[a] = tot++;
    }
    
    bool find(long long a) {
        // cout << "find " << a << endl;
        int i = prev[hash(a)];
        while (i != -1) {
            if (v[i] == a) {
                vis[ind[i]] = true;
                return true;
            }
            i = next[i];
        }
        return false;
    }
    
public:
    int longestConsecutive(vector<int>& nums) {
        auto n = nums.size();
        tot = 0;
        prev.resize(MOD + 5, -1);
        for (int i = 0; i < n; ++i)
            add(hash(nums[i]), i, nums[i]);
        vis.resize(n + 5, false);
        int ans = 0;
        for (int i = 0; i < n; ++i)
            if (!vis[i]) {
                int tmp = 1;
                find(nums[i]);
                long long j = nums[i] - 1;
                while (find(j))
                    --j, ++tmp;
                j = nums[i] + 1;
                while (find(j))
                    ++j, ++tmp;
                if (tmp > ans) ans = tmp;
            }
        return ans;
    }
};

方法二

参考别人的解法，代码非常简洁，a[i] 表示数字 i 所在的连续区间长度。

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

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_map<int, int> a;
        int ans = 0;
        for (int i : nums)
            if (!a[i])
                ans = max(ans, a[i] = a[i - a[i - 1]] = a[i + a[i + 1]] = a[i - 1] + 1 + a[i + 1]);
        return ans;
    }
};

132. Palindrome Partitioning II

动态规划，f[i] 表示 s 的前 i 位的最小划分。

时间复杂度 O(n ^ 2)，运行时间 6 ms。

class Solution {
    const int P = 257;
    const int M = 2147483647;
    
    int *pow, *h1, *h2, *f;
    
    void initHash(string &s, int *h, int n) {
        h[0] = 0;
        for (int i = 1; i <= n; ++i)
            h[i] = ((long long)h[i - 1] * P + (int)s[i - 1]) % M;
    }
    
    bool isEqual(int l, int r, int n) {
        int _l = n - r + 1, _r = n - l + 1;
        int H1 = (h1[r] - (long long)h1[l] * pow[r - l]) % M;
        if (H1 < 0) H1 += M;
        int H2 = (h2[_r] - (long long)h2[_l] * pow[_r - _l]) % M;
        if (H2 < 0) H2 += M;
        return H1 == H2;
    }
    
public:
    int minCut(string s) {
        int n = s.length();
        string t = s;
        reverse(t.begin(), t.end());
        pow = new int[n + 1];
        pow[0] = 1;
        for (int i = 1; i <= n; ++i)
            pow[i] = ((long long)pow[i - 1] * P) % M;
        h1 = new int[n + 1];
        h2 = new int[n + 1];
        initHash(s, h1, n);
        initHash(t, h2, n);
        
        f = new int[n + 1];
        f[0] = 0;
        for (int i = 1; i <= n; ++i) {
            f[i] = n + 1;
            for (int j = 0; j < i; ++j)
                if (f[j] + 1 < f[i] && isEqual(j + 1, i, n))
                    f[i] = f[j] + 1;
        }
        return f[n] - 1;
    }
};

135. Candy

每个小孩得到的糖果数由左边小孩的最少糖果数和右边小孩的最少糖果数决定，变量说明：

• limit – 左边小孩的糖果数限制
• cur – 当前小孩的糖果数

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

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        if (n == 0) return 0;
        int ans = 0;
        int limit = 0;
        int i = 0;
        while (i < n) {
            if (i > 0 && ratings[i] > ratings[i - 1]) ++limit; else limit = 0;
            int cur = 1;
            ++ans;
            bool f = false;
            while (i + 1 < n && ratings[i] > ratings[i + 1]) {
                ++i, ++cur, ans += cur;
                f = true;
            }
            if (cur < limit) {
                ans += limit - cur;
                cur = limit;
            }
            if (f) limit = 1; else limit = cur;
            i += 1;
        }
        return ans;
    }
};

140. Word Break II

动态规划。

时间复杂度 O(n ^ 2)，运行时间 6 ms。

class Solution {
    
    unordered_set<string> se;
    vector<bool> f;
    vector<string> ans;
    
    void rush(int i, string s) {
        if (i == 0) {
            ans.push_back(s);
            return;
        }
        string w = "";
        for (int j = i - 1; j >= 0; --j) {
            w = s[j] + w;
            if (f[j] && se.count(w) > 0) {
                auto t = s;
                if (j) t.insert(j, " ");
                rush(j, t);
            }
        }
    }
    
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        int n = s.length();
        if (n == 0) return ans;
        f.resize(n + 5, false);
        for (auto a : wordDict)
            se.insert(a);
        f[0] = true;
        for (int i = 1; i <= n; ++i) {
            string w = "";
            for (int j = i - 1; j >= 0; --j) {
                w = s[j] + w;
                if (f[j] && se.count(w) > 0) {
                    f[i] = true;
                    break;
                }
            }
        }
        if (!f[n]) return ans;
        rush(n, s);
        return ans;
    }
};

145. Binary Tree Postorder Traversal

dfs 遍历一次即可。

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

/**
 * 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 {
    
    vector<int> ans;
    
    void rush(TreeNode* x) {
        if (x == NULL) return;
        rush(x->left);
        rush(x->right);
        ans.push_back(x->val);
    }
    
public:
    vector<int> postorderTraversal(TreeNode* root) {
        rush(root);
        return ans;
    }
};

146. LRU Cache

使用 list 存储最近使用的缓存队列，unordered_map 存储键值和键在队列的位置。

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

class LRUCache {
    
    list<int> q;
    unordered_map<int, list<int>::iterator> p;
    unordered_map<int, int> v;
    int _capacity;
    
public:
    LRUCache(int capacity) {
        _capacity = capacity;
    }
    
    int get(int key) {
        if (v.count(key)) {
            q.erase(p[key]);
            q.push_front(key);
            p[key] = q.begin();
            return v[key];
        } else
            return -1;
    }
    
    void put(int key, int value) {
        if (v.count(key)) {
            q.erase(p[key]);
        } else {
            if (v.size() == _capacity) {
                auto pg = q.back();
                q.pop_back();
                p.erase(pg);
                v.erase(pg);
            }
        }
        q.push_front(key);
        p[key] = q.begin();
        v[key] = value;
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

149. Max Points on a Line

对所有点进行两层循环，第一层循环枚举线上的点 i，第二层循环计算其他点对于 i 的斜率，使用 STL 库点 unordered_map 统计，斜率相同的点共线。

时间复杂度 O(n ^ 2)，运行时间 9 ms。

/**
 * Definition for a point.
 * struct Point {
 *     int x;
 *     int y;
 *     Point() : x(0), y(0) {}
 *     Point(int a, int b) : x(a), y(b) {}
 * };
 */
class Solution {
public:
    int maxPoints(vector<Point>& points) {
        int n = points.size();
        if (n <= 2) return n;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            const auto& p1 = points[i];
            unordered_map<long double, int> cnt;
            int base = 1;
            int vert = 0;
            for (int j = i + 1; j < n; ++j) {
                const auto& p2 = points[j];
                if (p1.x == p2.x && p1.y == p2.y)
                    ++base;
                else
                if (p1.x == p2.x)
                    ++vert;
                else
                    ++cnt[((long double) p2.y - p1.y) / ((long double) p2.x - p1.x)];
            }
            ans = max(ans, base + vert);
            for (auto c : cnt)
                ans = max(ans, base + c.second);
        }
        return ans;
    }
};

154. Find Minimum in Rotated Sorted Array II

二分法。

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

class Solution {
public:
    int findMin(vector<int> &num) {
        int n = num.size();
        int l = 0, r = n - 1, mid;
        int ans = num[0];
        while (l < r - 1) {
            mid = (l + r) >> 1;
            if (num[l] < num[mid]) {
                ans = min(ans, num[l]);
                l = mid + 1;
            } else
            if (num[mid] < num[r]) {
                ans = min(ans, num[mid]);
                r = mid - 1;
            } else
                ++l;
        }
        ans = min(ans, min(num[l], num[r]));
        return ans;
    }
};

164. Maximum Gap

桶排序。

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

class Solution {
public:
    int maximumGap(vector<int> &num) {
        int n = num.size();
        if (n < 2) return 0;
        int minNum = INT_MAX, maxNum = INT_MIN;
        for (int i = 0; i < n; ++i) {
            if (num[i] < minNum) minNum = num[i];
            if (num[i] > maxNum) maxNum = num[i];
        }
        if (minNum == maxNum) return 0;
        int blockSize = (int)ceil(((double)maxNum - minNum) / (n - 1));
        int blockCnt = (maxNum - minNum) / blockSize + 1;
        vector<int> minBlock(n, INT_MAX);
        vector<int> maxBlock(n, INT_MIN);
        for (int i = 0, j; i < n; ++i) {
            j = (num[i] - minNum) / blockSize;
            if (num[i] < minBlock[j]) minBlock[j] = num[i];
            if (num[i] > maxBlock[j]) maxBlock[j] = num[i];
        }
        int pre = minNum;
        int ans = 0;
        for (int i = 0; i < blockCnt; ++i)
            if (!(minBlock[i] == INT_MAX && maxBlock[i] == INT_MIN)) {
                ans = max(ans, minBlock[i] - pre);
                pre = maxBlock[i];
            }
        return ans;
    }
};

174. Dungeon Game

二份答案。

运行时间 22 ms。

class Solution {
public:
    int calculateMinimumHP(vector<vector<int> > &dungeon) {
        int m = dungeon.size();
        int n = dungeon[0].size();
        long long l = 1, r = 2147483647;
        int mid, ans, o0, o1;
        long long *f[2];
        bool *b[2];
        f[0] = new long long[n + 1];
        f[1] = new long long[n + 1];
        while (l <= r) {
            mid = (l + r) / 2;
            o0 = 1; o1 = 0;
            f[0][0] = dungeon[0][0];
            for (int i = 1; i < n; ++i)
                f[0][i] = -mid;
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (i || j) f[o1][j] = -mid;
                    if (i && f[o0][j] > -mid && f[o0][j] + dungeon[i][j] > f[o1][j])
                        f[o1][j] = f[o0][j] + dungeon[i][j];
                    if (j && f[o1][j - 1] > -mid && f[o1][j - 1] + dungeon[i][j] > f[o1][j])
                        f[o1][j] = f[o1][j - 1] + dungeon[i][j];
                }
                o0 = o1; o1 ^= 1;
            }
            if (f[o0][n - 1] > -mid) {
                ans = mid;
                r = mid - 1;
            } else
                l = mid + 1;
        }
        delete[] f[0];
        delete[] f[1];
        return ans;
    }
};

188. Best Time to Buy and Sell Stock IV

方法一

动态规划，滚动数组节省空间。f[j][i] 表示在前 i 个股票中交易 j 次的最大收益。

时间复杂度 O(n * k)，运行时间 6 ms。

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        if (k >= n / 2) {
            int ans = 0;
            for (int i = 1; i < n; ++i)
                ans += max(0, prices[i] - prices[i - 1]);
            return ans;
        }
        vector<int> f[2];
        f[0].resize(n + 3, 0);
        f[1].resize(n + 3);
        int o1 = 0, o2 = 1;
        int ans = 0;
        for (int j = 0; j < k; ++j, o1 ^= 1, o2 ^= 1) {
            f[o2][0] = f[o1][0];
            auto g = f[o1][0] - prices[0];
            for (int i = 1; i <= n; ++i) {
                f[o2][i] = f[o2][i - 1];
                if (i >= 2) {
                    g = max(g, f[o1][i - 2] - prices[i - 2]);
                    f[o2][i] = max(f[o2][i], prices[i - 1] + g);
                }
            }
            if (f[o2][n] > ans) ans = f[o2][n];
        }
        return ans;
    }
};

方法二

动态规划。f[1][i][j] 表示在前 i 个股票中买入 j 次的最大收益（当前持有股票），f[0][i][j] 表示对应的不持有股票的状态。

时间复杂度 O(n * k)，运行时间 6 ms。

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        if (k >= n / 2) {
            int ans = 0;
            for (int i = 1; i < n; ++i)
                ans += max(0, prices[i] - prices[i - 1]);
            return ans;
        }
        vector<int> f[2];
        f[0].resize(k + 3, 0);
        f[1].resize(k + 3, INT_MIN);
        for (int i = 0; i < n; ++i) {
            auto p = prices[i];
            for (int j = min(k, i / 2 + 1); j > 0; --j) {
                // sell
                f[0][j] = max(f[0][j], f[1][j] + p);
                // buy
                f[1][j] = max(f[1][j], f[0][j - 1] - p);
            }
        }
        int ans = 0;
        for (auto t : f[0])
            ans = max(ans, t);
        return ans;
    }
};