Leetcode 刷题打卡记录 包括Solution

140 Word Break II

1. // 16ms
   
2. class Solution {
   
3. private:
   
4.     bool search(vector<string>& res, const string s, int idx, const set<string>& wordMap,
   
5.                map<int, vector<string>>& dp, const int maxLen) {
   
6.         if (idx >= s.size())
   
7.             return true;
   
8.         auto it = dp.find(idx);
   
9.         if (it != dp.end()) {
   
10.             if (it->second.empty())
    
11.                 return false;
    
12.             res = it->second;
    
13.             return true;
    
14.         }
    
15.         for (int i = idx; i < s.size(); i++) {
    
16.             int len = i - idx + 1;
    
17.             if (len > maxLen)
    
18.                 break;
    
19.             auto wd = s.substr(idx, len);
    
20.             if (wordMap.count(wd) < 1)
    
21.                 continue;
    
22.             vector<string> res0;
    
23.             if (search(res0, s, i+1, wordMap, dp, maxLen)) {
    
24.                 if (res0.empty()) {
    
25.                     res.push_back(wd);
    
26.                     break;
    
27.                 } else {
    
28.                     for (auto& w : res0) {
    
29.                         res.push_back(wd + string(" ") + w);
    
30.                     }
    
31.                 }
    
32.             }
    
33.         }
    
34.         dp[idx] = res;
    
35.         return !res.empty();
    
36.     }
    
37.    
    
38. public:
    
39.     vector<string> wordBreak(string s, vector<string>& wordDict) {
    
40.         set<string> wordMap;
    
41.         int maxLen = 0;
    
42.         for(auto& w : wordDict) {
    
43.             wordMap.insert(w);
    
44.             maxLen = max(maxLen, (int)w.size());
    
45.         }
    
46.         map<int, vector<string>> dp;
    
47.         vector<string> res;
    
48.         search(res, s, 0, wordMap, dp, maxLen);
    
49.         
    
50.         return res;
    
51.     }
    
52. };

复制代码

146 LRU Cache

1. class LRUCache {
   
2. private:
   
3.     list<int> orders;
   
4.     unordered_map<int, pair<int, list<int>::iterator>> cache;
   
5.     int capacity;
   
6. public:
   
7.     LRUCache(int capacity) {
   
8.         this->capacity = capacity;
   
9.     }
   
10.    
    
11.     int get(int key) {
    
12.         auto it = cache.find(key);
    
13.         if (it == cache.end())
    
14.             return -1;
    
15.         orders.splice(orders.begin(), orders, it->second.second);
    
16.         it->second.second = orders.begin();
    
17.         return it->second.first;
    
18.     }
    
19.    
    
20.     void put(int key, int value) {
    
21.         auto it = cache.find(key);
    
22.         if (it != cache.end()) {
    
23.             orders.splice(orders.begin(), orders, it->second.second);
    
24.             it->second.second = orders.begin();
    
25.             it->second.first = value;
    
26.         } else {
    
27.             if (orders.size() == capacity) {
    
28.                 cache.erase(cache.find(orders.back()));
    
29.                 orders.pop_back();
    
30.             }
    
31.             orders.push_front(key);
    
32.             cache.emplace(key, make_pair(value, orders.begin()));
    
33.         }
    
34.     }
    
35. };

复制代码

155 Min Stack

1. class MinStack {
   
2.     stack<int> stk;
   
3.     stack<int> stkMin;
   
4. public:
   
5.     /** initialize your data structure here. */
   
6.     MinStack() {
   
7.         
   
8.     }
   
9.    
   
10.     void push(int x) {
    
11.         stk.push(x);
    
12.         if (stkMin.empty() || x <= stkMin.top()) {
    
13.             stkMin.push(x);
    
14.         }
    
15.     }
    
16.    
    
17.     void pop() {
    
18.         if (stk.empty())
    
19.             return;
    
20.         if (stk.top() == stkMin.top())
    
21.             stkMin.pop();
    
22.         stk.pop();
    
23.     }
    
24.    
    
25.     int top() {
    
26.         if (stk.empty())
    
27.             return -1;
    
28.         return stk.top();
    
29.     }
    
30.    
    
31.     int getMin() {
    
32.         if (stkMin.empty())
    
33.             return -1;
    
34.         return stkMin.top();
    
35.     }
    
36. };
    
37. 
    
38. /**
    
39. * Your MinStack object will be instantiated and called as such:
    
40. * MinStack obj = new MinStack();
    
41. * obj.push(x);
    
42. * obj.pop();
    
43. * int param_3 = obj.top();
    
44. * int param_4 = obj.getMin();
    
45. */

复制代码

162 Find Peak Element

1. class Solution {
   
2. public:
   
3.     int findPeakElement(vector<int>& nums) {
   
4.         if (nums.empty())
   
5.             return -1;
   
6.         if (nums.size() == 1)
   
7.             return 0;
   
8. 
   
9.         // flag = 1 if nums[i] > nums[i-1] else flag = 0
   
10.         int flag = 1;
    
11.         for (int i = 1; i < nums.size(); i++) {
    
12.             if (nums[i] > nums[i-1]) {
    
13.                 flag = 1;
    
14.             }
    
15.             else if (nums[i] < nums[i-1]) {
    
16.                 if (flag == 1)
    
17.                     return i-1;
    
18.                 flag = 0;
    
19.             } else {
    
20.                 flag = 0;
    
21.             }
    
22.         }
    
23.         if (flag == 1)
    
24.             return nums.size()-1;
    
25.         return -1;
    
26.     }
    
27. };

复制代码

162 Find Peak Element
Solution with log(n)

1. // log(n)
   
2. class Solution {
   
3. public:
   
4.     int findPeakElement(vector<int>& nums) {
   
5.         if (nums.empty())
   
6.             return -1;
   
7.         if (nums.size() == 1)
   
8.             return 0;
   
9. 
   
10.         int l = 0, r = nums.size()-1;
    
11.         while (l <= r) {
    
12.             int m = l + (r-l)/2;
    
13.             if ((m == 0 || nums[m-1] < nums[m]) &&
    
14.                 (m == nums.size()-1 || nums[m+1] < nums[m]))
    
15.                 return m;
    
16.             if (m > 0 && nums[m-1] > nums[m] )
    
17.                 r = m - 1;
    
18.             else
    
19.                 l = m + 1;
    
20.         }
    
21.         return -1;
    
22.     }
    
23. };

复制代码

wglacier 发表于 2019-2-8 16:18
162 Find Peak Element
Solution with log(n)
[mw_shl_code=cpp,true]// log(n)

Some thoughts on the solution: Suppose the middle element is nums[m], there are only 2 cases:

The middle one satisfy: nums[m-1] < nums[m] > nums[m+1]
Either nums[m-1] > nums[m] or nums[m+1] > nums[m]
let's assume nums[m-1] > nums[m], and let's see why the left part (nums[0] to nums[m-1])must satify the condition.
2a. From nums[m-1] all the way to the left is decreasing, this means nums[m-1] is the one
2b. From nums[m-1] all the way to the left is increasing, this means nums[0] is the one
2c. There are some peaks or valleys between nums[m-1] and nums[0], in either case we can gurrantee peaks.
I used nums[0] above to simplify, but keep in mind that if you always choose the part with higher number, you can keep the boundary conditions in next round (nums[left] > nums[left-1] and nums[right] > nums[right+1]).
Last thing I'd like to point out is no adjacent elements are the same which is critical to this method (nums[i] ≠ nums[i+1]).

173 Binary Search Tree Iterator

1. /**
   
2. * Definition for a binary tree node.
   
3. * struct TreeNode {
   
4. *     int val;
   
5. *     TreeNode *left;
   
6. *     TreeNode *right;
   
7. *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
   
8. * };
   
9. */
   
10. class BSTIterator {
    
11. private:
    
12.     stack<TreeNode*> stk;
    
13. public:
    
14.     BSTIterator(TreeNode* root) {
    
15.         inStack(root);
    
16.     }
    
17.    
    
18.     void inStack(TreeNode* p) {
    
19.         if (!p) return;
    
20. 
    
21.         stk.push(p);
    
22.         while (p->left) {
    
23.             p = p->left;
    
24.             stk.push(p);
    
25.         }
    
26.     }
    
27.    
    
28.     /** [url=home.php?mod=space&uid=160137]@return[/url] the next smallest number */
    
29.     int next() {
    
30.         auto t = stk.top();
    
31.         stk.pop();
    
32.         inStack(t->right);
    
33.         
    
34.         return t->val;
    
35.     }
    
36.    
    
37.     /** @return whether we have a next smallest number */
    
38.     bool hasNext() {
    
39.         return !stk.empty();
    
40.     }
    
41. };
    
42. 
    
43. /**
    
44. * Your BSTIterator object will be instantiated and called as such:
    
45. * BSTIterator* obj = new BSTIterator(root);
    
46. * int param_1 = obj->next();
    
47. * bool param_2 = obj->hasNext();
    
48. */

复制代码

200. Number of Islands, Medium
class Solution {
private:
    void expand(vector<vector<char>>& grid, int i, int j) {
        if (i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size())
            return;
        if (grid[i][j] == '0') return;
        grid[i][j] = '0';
        expand(grid, i+1, j);
        expand(grid, i-1, j);
        expand(grid, i, j+1);
        expand(grid, i, j-1);
    }
public:
    int numIslands(vector<vector<char>>& grid) {
        int res = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == '0') continue;
                res++;
                expand(grid, i, j);
            }
        }
        return res;
    }
};

218. The Skyline Problem

1. class Solution {
   
2. public:
   
3.     vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
   
4.         struct node {
   
5.             int x; // x pos
   
6.             int h; // height
   
7.             node(int _x, int _h)
   
8.                 : x(_x), h(_h)
   
9.                 {}
   
10.         };
    
11.         
    
12.         // put everything into a vector with (x, height). the height of right end is negative
    
13.         vector<node> nodes;
    
14.         for (const auto& b : buildings) {
    
15.             nodes.push_back(node(b[0], b[2]));  // left end
    
16.             nodes.push_back(node(b[1], -b[2])); // right end
    
17.         }
    
18.         // sort the nodes based on:
    
19.         // 1. smaller x first
    
20.         // 2. higher height for left end first
    
21.         // 3. lower height for right end first
    
22.         sort(nodes.begin(), nodes.end(), [](const auto& a, const auto& b) {
    
23.             return a.x < b.x || (a.x == b.x && a.h > b.h);
    
24.         });
    
25.         
    
26.         // map from height => count of the same height
    
27.         // note element in map in c++ is ordered
    
28.         map<int, int> queue;
    
29.         int maxHeight = 0;
    
30.         vector<pair<int, int>> res;
    
31.         for (const auto& n : nodes) {
    
32.             // if it is left end
    
33.             if (n.h > 0) {
    
34.                 queue[n.h]++;
    
35.                 if (n.h > maxHeight) {
    
36.                     maxHeight = n.h;
    
37.                     res.emplace_back(n.x, n.h);
    
38.                 }
    
39.             } else { // it is the right end
    
40.                 auto h = -n.h;
    
41.                 if (--queue[h] > 0) continue;
    
42. 
    
43.                 // this building is out
    
44.                 queue.erase(h);
    
45. 
    
46.                 // only care if it is the current highest one
    
47.                 if (h < maxHeight) continue;
    
48. 
    
49.                 // if this is the last building in the group
    
50.                 if (queue.empty()) {
    
51.                     maxHeight = 0;
    
52.                 } else {
    
53.                     // get the height of the second highest building
    
54.                     maxHeight = (--queue.end())->first;
    
55.                 }
    
56.                 res.emplace_back(n.x, maxHeight);
    
57.             }
    
58.         }
    
59.         return res;
    
60.     }
    
61. };

复制代码

224. Basic Calculator

1. class Solution {
   
2.     void pushOrReduce(stack<string>& stk, string& str) {
   
3.         if (stk.empty() || !(stk.top() == "+" || stk.top() == "-")) {
   
4.             stk.push(str);
   
5.         } else {
   
6.             // + or -
   
7.             int op2 = stoi(str);
   
8.             string op = stk.top(); stk.pop();
   
9.             int op1 = stoi(stk.top()); stk.pop();
   
10.             string r = to_string(op == "+"? op1 + op2 : op1 - op2);
    
11.             pushOrReduce(stk, r);
    
12.         }
    
13.     }
    
14. public:
    
15.     int calculate(string s) {
    
16.         string nums = "";
    
17.         stack<string> stk;
    
18.         vector<string> tokens;
    
19.         // split tokens
    
20.         for (char c : s) {
    
21.             if (!isdigit(c)) {
    
22.                 if (!nums.empty()) {
    
23.                     tokens.push_back(nums);
    
24.                     nums = "";
    
25.                 }
    
26.                 if (isspace(c))
    
27.                     continue;
    
28.                 tokens.push_back(string(1, c));
    
29.             } else {
    
30.                 nums += string(1, c);
    
31.             }
    
32.         }
    
33.         if (!nums.empty()) {
    
34.             tokens.push_back(nums);
    
35.         }
    
36.         // calc
    
37.         for (string& str : tokens) {
    
38.             if (str == "(" || str == "+" || str == "-")
    
39.                 stk.push(str);
    
40.             else {
    
41.                 if (str == ")") {
    
42.                     str = stk.top(); stk.pop();
    
43.                     if (stk.top() == "(") {
    
44.                         stk.pop();
    
45.                         pushOrReduce(stk, str);
    
46.                     } else {
    
47.                         cout << "error" << endl;
    
48.                     }
    
49.                 } else {
    
50.                     // is number
    
51.                     pushOrReduce(stk, str);
    
52.                 }
    
53.             }
    
54.         }
    
55.         return stoi(stk.top());
    
56.     }
    
57. };

复制代码