LeetCode「Hard」问题题解（201～300）

发表于 分类于 阅读次数：

212. Word Search II

对单词表建立 Trie 树，dfs 暴力搜索。

运行时间 62 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
56
class Solution {
    
    struct Node {
        string word;
        vector<Node*> next;
        
        Node() {
            word = "";
            next = vector<Node*>(26, NULL);
        }
    };
    
    Node *root = new Node();
    
    int n, m;
    vector<string> ans;
    
    void rush(Node *cur, int x, int y, vector<vector<char>>& board) {
        if (board[x][y] == '$' || cur->next[board[x][y] - 'a'] == NULL) return;
        cur = cur->next[board[x][y] - 'a'];
        if (cur->word != "") {
            ans.push_back(cur->word);
            cur->word = "";
        }
        auto c = board[x][y];
        board[x][y] = '$';
        if (x > 0) rush(cur, x - 1, y, board);
        if (x + 1 < n) rush(cur, x + 1, y, board);
        if (y > 0) rush(cur, x, y - 1, board);
        if (y + 1 < m) rush(cur, x, y + 1, board);
        board[x][y] = c;
    }
    
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        n = board.size();
        if (n == 0) return ans;
        m = board[0].size();
        if (m == 0) return ans;
        
        for (auto word : words) {
            auto x = root;
            for (char c : word) {
                if (x->next[c - 'a'] == NULL)
                    x->next[c - 'a'] = new Node();
                x = x->next[c - 'a'];
            }
            x->word = word;
        }
        
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                rush(root, i, j, board);
        return ans;
    }
};

214. Shortest Palindrome

方法一

问题为求最长的回文前缀。

时间复杂度 O(n)，运行时间 42 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
class Solution {
    
    string my_reverse(string s) {
        reverse(s.begin(), s.end());
        return s;
    }
    
public:
    string shortestPalindrome(string s) {
        int n = s.length();
        if (n <= 1) return s;
        
        string rs = my_reverse(s);
        string front = "";
        int max1 = 0;
        for (int i = 0; i < (n + 1) / 2; ++i) {
            if (front == rs.substr(n - 1 - i - i, i))
                max1 = i;
            front += s[i];
        }
        
        int max2 = 0;
        front = "";
        for (int i = 0; i <= n / 2; ++i) {
            if (front == rs.substr(n - i - i, i))
                max2 = i;
            front += s[i];
        }
        
        if (max1 >= max2)
            return my_reverse(s.substr(max1 + 1)) + s[max1] + s.substr(max1 + 1);
        else
            return my_reverse(s.substr(max2)) + s.substr(max2);
    }
};

方法二

思路同方法一，使用高效的KMP 算法解决。

时间复杂度 O(n)，运行时间 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:
    string shortestPalindrome(string s) {
        int n = s.length();
        if (n <= 1) return s;
        string rs = s;
        reverse(rs.begin(), rs.end());
        string f = s + "$" + rs;
        int l = f.length();
        vector<int> match(l, 0);
        for (int i = 1, j = 0; i < l; ++i) {
            while (j > 0 && f[j] != f[i])
                j = match[j - 1];
            if (f[j] == f[i]) ++j;
            match[i] = j;
        }
        return rs.substr(0, n - match[l - 1]) + s;
    }
};

218. The Skyline Problem

从左到右扫描，记录当前的覆盖情况，使用 STL 库的 multiset 维护当前的最高覆盖。

时间复杂度 O(n * log(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
class Solution {
    
    multiset<int> bs;
    
public:
    vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
        vector<pair<int, int>> ans;
        if (buildings.size() == 0) return ans;
        vector<pair<int, int>> l;
        for (auto b : buildings) {
            l.push_back({b[0], b[2]});
            l.push_back({b[1], -b[2]});
        }
        sort(l.begin(), l.end());
        bs.insert(0);
        int pb = l[0].first, ph = -1;
        for (auto b : l) {
            if (b.first != pb) {
                if (*bs.rbegin() != ph) {
                    ans.push_back({pb, *bs.rbegin()});
                    ph = *bs.rbegin();
                }
                pb = b.first;
            }
            if (b.second > 0)
                bs.insert(b.second);
            else
                bs.erase(bs.find(-b.second));
        }
        if (ph != 0) ans.push_back({l[l.size() - 1].first, 0});
        return ans;
    }
};

224. Basic Calculator

建立两个栈分别存储数字和符号。

时间复杂度 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
class Solution {
    
    stack<int> num;
    stack<char> sign;
    
    void calc() {
        while (sign.top() != '(') {
            int b = num.top(); num.pop();
            int a = num.top(); num.pop();
            char c = sign.top(); sign.pop();
            num.push(c == '+' ? a + b : a - b);
        }
    }
    
public:
    int calculate(string s) {
        if (s == "") return 0;
        auto it = s.begin();
        sign.push('(');
        while (true) {
            while (it != s.end() && *it == ' ') ++it;
            if (it == s.end()) break;
            if (*it == '(') {
                sign.push('(');
                ++it;
            } else
            if (*it == ')') {
                sign.pop();
                calc();
                ++it;
            } else
            if (*it == '+' || *it == '-')
                sign.push(*it++);
            else {
                int a = 0;
                while (it != s.end() && *it >= '0' && *it <= '9')
                    a = a * 10 + (*it++ - '0');
                num.push(a);
                calc();
            }
        }
        return num.top();
    }
};

233. Number of Digit One

按位统计。

时间复杂度 O(1)，运行时间 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
class Solution {
public:
    int countDigitOne(int n) {
        if (n <= 0) return 0;
        vector<int> p{1};
        int k = 0, x = n, pp = 1;
        while (x > 9) {
            pp *= 10;
            p.push_back(pp);
            x /= 10;
            ++k;
        }
        bool greater = false;
        int ans = 0;
        for (int i = k; i >= 0; --i) {
            int d = n / p[i] % 10;
            int l = n / p[i] / 10;
            int r = n % p[i];
            ans += l * p[i];
            if (d == 1) ans += r + 1;
            if (d > 1) ans += p[i];
        }
        return ans;
    }
};

239. Sliding Window Maximum

维护递减的单调队列。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> ans;
        deque<int> s;
        for (int i = 0; i < n; ++i) {
            while (!s.empty() && s.front() <= i - k) s.pop_front();
            while (!s.empty() && nums[s.back()] <= nums[i])
                s.pop_back();
            s.push_back(i);
            if (i >= k - 1)
                ans.push_back(nums[s.front()]);
        }
        return ans;
    }
};

273. Integer to English Words

时间复杂度 O(1)，运行时间 3 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 {
    
    const string BELOW20[20] = {"", "One", "Two", "Three", "Four","Five","Six","Seven","Eight","Nine","Ten", "Eleven","Twelve","Thirteen","Fourteen","Fifteen","Sixteen","Seventeen","Eighteen","Nineteen"};
    const string BELOW100[10] = {"", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
    
    string trans(int n, string prefix, string suffix) {
        if (n == 0) return "";
        string ret;
        if (n >= 100) {
            ret += " " + BELOW20[n / 100] + " Hundred";
            n %= 100;
        }
        if (n >= 20) {
            ret += " " + BELOW100[n / 10];
            n %= 10;
        }
        if (n)
            ret += " " + BELOW20[n];
        ret = prefix + ret.substr(1) + suffix;
        return ret;
    }
    
public:
    string numberToWords(int num) {
        if (num == 0) return "Zero";
        if (num < 1000) return trans(num, "", "");
        if (num < 1000000) return trans(num / 1000, "", " Thousand") + trans(num % 1000, " ", "");
        if (num < 1000000000) return trans(num / 1000000, "", " Million") + trans(num / 1000 % 1000, " ", " Thousand") + trans(num % 1000, " ", "");
        return trans(num / 1000000000, "", " Billion") + trans(num / 1000000 % 1000, " ", " Million") + trans(num / 1000 % 1000, " ", " Thousand") + trans(num % 1000, " ", "");
    }
};

282. Expression Add Operators

dfs 搜索，使用「撤回」的方式处理 * 和 + - 的优先级问题，搜索过程中记录最近一次的 + - 运算。

变量说明：

  • res – 当前表达式结果
  • last_v – 最近一次 + - 运算的数值
  • last_sign – 最近一次 + - 运算的符号
  • fml – 当前表达式

运行时间 123 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 {
    
    vector<string> ans;
    
    void dfs(const string &num, int p, int n, const int &target, long long res, long long last_v, char last_sign, string fml) {
        if (p == n) {
            if (res == (long long) target)
                ans.push_back(fml);
            return;
        }
        long long x = 0;
        string sx = "";
        for (int i = p; i < n; ++i) {
            x = x * 10 + (num[i] - '0');
            sx += num[i];
            if (i > p && num[p] == '0') break;
            if (last_sign == '$') {
                dfs(num, i + 1, n, target, x, x, '+', sx);
            } else {
                dfs(num, i + 1, n, target, res + x, x, '+', fml + '+' + sx);
                dfs(num, i + 1, n, target, res - x, x, '-', fml + '-' + sx);
                if (last_sign == '+')
                    dfs(num, i + 1, n, target, res - last_v + last_v * x, last_v * x, '+', fml + '*' + sx);
                else
                    dfs(num, i + 1, n, target, res + last_v - last_v * x, last_v * x, '-', fml + '*' + sx);
            }
        }
    }
    
public:
    vector<string> addOperators(string num, int target) {
        int n = num.length();
        dfs(num, 0, n, target, 0, 0, '$', "");
        return ans;
    }
};

295. Find Median from Data Stream

方法一

建立二叉搜索树，维护中位数相关的两元素的指针。

运行时间 213 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
class MedianFinder {
    
    int size;
    set<pair<int, int>> s;
    set<pair<int, int>>::iterator a, b;
    
public:
    /** initialize your data structure here. */
    MedianFinder() {
        size = 0;
    }
    
    void addNum(int num) {
        auto x = make_pair(num, ++size);
        s.insert(x);
        if (size == 1) {
            b = s.begin();
        } else
        if (size == 2) {
            a = b = s.begin();
            ++b;
        } else
        if (size & 1) {
            if (x < *a) {
                b = a;
                --a;
            } else
            if (*a < x && x < *b) {
                --b;
            }
        } else {
            if (*a < x && x < *b) {
                ++a;
            } else
            if (x > *b) {
                a = b;
                ++b;
            }
        }
    }
    
    double findMedian() {
        return size & 1 ? b->first : (a->first + b->first) * 0.5;
    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

方法二

维护两个堆，一个大根堆和一个小根堆，大根堆存最小的一半元素，小根堆存另一半元素，中位数可由两个堆的堆顶计算得出。

运行时间 176 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 MedianFinder {
    
    priority_queue<int> small, large;
    
public:
    /** initialize your data structure here. */
    MedianFinder() {
        
    }
    
    void addNum(int num) {
        small.push(num);
        large.push(-small.top());
        small.pop();
        if (small.size() < large.size()) {
            small.push(-large.top());
            large.pop();
        }
    }
    
    double findMedian() {
        return small.size() > large.size() ? small.top() : (small.top() - large.top()) * 0.5;
    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

297. Serialize and Deserialize Binary Tree

前序遍历。

运行时间 79 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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
    
    string my_data;
    
    TreeNode* my_deserialize() {
        int d = my_data.find_first_of(',');
        auto cur = my_data.substr(0, d);
        my_data.erase(0, d + 1);
        if (cur == "null") return nullptr;
        auto ret = new TreeNode(stoi(cur));
        ret->left = my_deserialize();
        ret->right = my_deserialize();
        return ret;
    }
    
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if (root == nullptr) return "null,";
        return to_string(root->val) + ',' + serialize(root->left) + serialize(root->right);
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        my_data = data;
        return my_deserialize();
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));
0%