Leetcode 刷题打卡记录 包括Solution

228. Summary Ranges

1. class Solution {
   
2. public:
   
3.     string output(const vector<int>& nums, int i, int j) {
   
4.         if (j == i) return to_string(nums[i]);
   
5.         
   
6.         return to_string(nums[i]) + "->" + to_string(nums[j]);
   
7.     }
   
8.     vector<string> summaryRanges(vector<int>& nums) {
   
9.         int i = 0;
   
10.         vector<string> res;
    
11.         if (nums.empty()) return res;
    
12.         int j = 1;
    
13.         for (; j < nums.size(); j++) {
    
14.             if ((long)nums[j] - (long)nums[j-1] != 1) {
    
15.                 res.push_back(output(nums, i, j-1));
    
16.                 i = j;
    
17.             }
    
18.         }
    
19.         res.push_back(output(nums, i, j-1));
    
20.         return res;
    
21.     }
    
22. };

复制代码

240. Search a 2D Matrix II

1. class Solution {
   
2. public:
   
3.     bool searchMatrix(vector<vector<int>> &matrix, int target) {
   
4.         // write your code here
   
5.         if (matrix.size() == 0) return false;
   
6.         
   
7.         int rows = matrix.size();
   
8.         int cols = matrix[0].size();
   
9.         int i = 0, j = cols - 1;
   
10.         while (i < rows && j >= 0) {
    
11.             if (matrix[i][j] == target) {
    
12.                 return true;
    
13.             }
    
14.             if (target > matrix[i][j]) {
    
15.                 ++i;
    
16.             } else {
    
17.                 --j;
    
18.             }
    
19.         }
    
20.         return false;
    
21.     }
    
22. };

复制代码

253. Meeting Rooms II

1. /**
   
2. * Definition for an interval.
   
3. * struct Interval {
   
4. *     int start;
   
5. *     int end;
   
6. *     Interval() : start(0), end(0) {}
   
7. *     Interval(int s, int e) : start(s), end(e) {}
   
8. * };
   
9. */
   
10. class Solution {
    
11. public:
    
12.     int minMeetingRooms(vector<Interval>& intervals) {
    
13.         vector<int> orders;
    
14.         for (auto& a : intervals) {
    
15.             orders.push_back(a.start);
    
16.             orders.push_back(-a.end);
    
17.         }
    
18.         sort(orders.begin(), orders.end(), [](const auto& a, const auto& b) {
    
19.             int absa = abs(a);
    
20.             int absb = abs(b);
    
21.             return absa < absb || (absa == absb && (a < 0));
    
22.         });
    
23.         int res = 0;
    
24.         int rms = 0;
    
25.         for (const auto& n : orders) {
    
26.             if (n >= 0) ++rms;
    
27.             else --rms;
    
28.             res = max(res, rms);
    
29.         }
    
30.         return res;
    
31.     }
    
32. };

复制代码

279. Perfect Squares

1. class Solution {
   
2. public:
   
3.     int calc(const vector<int>& pns, vector<int>& dp, int n) {
   
4.         if (n < 1) return 0;
   
5.         if (dp[n] <= n) {
   
6.             return dp[n];
   
7.         }
   
8.         auto it = lower_bound(pns.begin(), pns.end(), n);
   
9.         if (*it == n) {   
   
10.             dp[n] = 1;
    
11.             return 1;
    
12.         }
    
13.         int res = n;
    
14.         while (--it != --pns.begin()) {
    
15.             int r = calc(pns, dp, n - *it);
    
16.             res = min(r+1, res);
    
17.         }
    
18.         dp[n] = res;
    
19.         return res;
    
20.     }
    
21. 
    
22.     int numSquares(int n) {
    
23.         vector<int> pns;
    
24.         vector<int> dp(n+1, n+1);
    
25.         for(int i = 1; i <= n; i++) {
    
26.             int v = i*i;
    
27.             pns.push_back(v);
    
28.             if (v > n) break;
    
29.         }
    
30.         return calc(pns, dp, n);
    
31.     }
    
32. };

复制代码

289. Game of Life

1. class Solution {
   
2.     int isLive(const vector<vector<int>>& board, int rows, int cols, int i, int j) {
   
3.         if (i < 0 || j < 0 || i >= rows || j >= cols) return 0;
   
4.         return board[i][j];
   
5.     }
   
6.     int getLiveNeighbors(const vector<vector<int>>& board, int rows, int cols, int i, int j) {
   
7.         return isLive(board, rows, cols, i-1, j-1) +
   
8.             isLive(board, rows, cols, i-1, j) +
   
9.             isLive(board, rows, cols, i-1, j+1) +
   
10.             isLive(board, rows, cols, i, j+1) +
    
11.             isLive(board, rows, cols, i+1, j+1) +
    
12.             isLive(board, rows, cols, i+1, j) +
    
13.             isLive(board, rows, cols, i+1, j-1) +
    
14.             isLive(board, rows, cols, i, j-1);
    
15.     }
    
16.     void check(vector<vector<int>>& board, int i, int j) {
    
17.         int rows = board.size();
    
18.         int cols = board[0].size();
    
19.         
    
20.         if (j == cols) {
    
21.             check(board, i+1, 0);
    
22.             return;
    
23.         }
    
24.         if (i == rows) return;
    
25.         
    
26.         int state;
    
27.         int neighbors = getLiveNeighbors(board, rows, cols, i, j);
    
28.         if (board[i][j] == 0) {
    
29.             if (neighbors == 3) state = 1;
    
30.             else state = 0;
    
31.         } else {
    
32.             if (neighbors < 2 || neighbors > 3)
    
33.                 state = 0;
    
34.             else
    
35.                 state = 1;
    
36.         }
    
37.         check(board, i, j+1);
    
38.         board[i][j] = state;
    
39.     }
    
40. public:
    
41.     void gameOfLife(vector<vector<int>>& board) {
    
42.         if (board.empty() || board[0].empty()) return;
    
43.         
    
44.         check(board, 0, 0);
    
45.     }
    
46. };

复制代码

297. Serialize and Deserialize Binary Tree (recursive)

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 Codec {
    
11. public:
    
12. 
    
13.     // Encodes a tree to a single string.
    
14.     string serialize(TreeNode* root) {
    
15.         if (!root) return string("#");
    
16.         
    
17.         string res = to_string(root->val);
    
18.         res += string(",") + serialize(root->left);
    
19.         res += string(",") + serialize(root->right);
    
20.         return res;
    
21.     }
    
22. 
    
23.     TreeNode* deserialize(string& data, int& i) {
    
24.         if (i >= data.size())
    
25.             return nullptr;
    
26.         
    
27.         auto pos = data.find(",", i);
    
28.         if (pos == string::npos)
    
29.             pos = data.size();
    
30.         auto tok = data.substr(i, pos-i);
    
31.         i = pos + 1;
    
32.         if (tok == "#") {
    
33.             return nullptr;
    
34.         }
    
35.         TreeNode* t = new TreeNode(stoi(tok));
    
36.         t->left = deserialize(data, i);
    
37.         t->right = deserialize(data, i);
    
38.         return t;
    
39.     }
    
40.    
    
41.     // Decodes your encoded data to tree.
    
42.     TreeNode* deserialize(string data) {
    
43.         int i = 0;
    
44.         return deserialize(data, i);
    
45.     }
    
46. };
    
47. 
    
48. // Your Codec object will be instantiated and called as such:
    
49. // Codec codec;
    
50. // codec.deserialize(codec.serialize(root));

复制代码

297. Serialize and Deserialize Binary Tree
non-recursive version, traverse by layer

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 Codec {
    
11. public:
    
12. 
    
13.     // Encodes a tree to a single string.
    
14.     string serialize(TreeNode * root) {
    
15.         // write your code here
    
16.         if (!root) return "";
    
17.         
    
18.         vector<TreeNode*> q(1, root);
    
19.         string res;
    
20.         while (!q.empty()) {
    
21.             vector<TreeNode*> q2;
    
22.             for (auto p : q) {
    
23.                 if (!res.empty()) res += ",";
    
24.                 if (!p) res += "#";
    
25.                 else {
    
26.                     res += to_string(p->val);
    
27.                     q2.push_back(p->left);
    
28.                     q2.push_back(p->right);
    
29.                 }
    
30.             }
    
31.             q.swap(q2);
    
32.         }
    
33.         return res;
    
34.     }
    
35. 
    
36.     TreeNode* getNode(string& data, int& i) {
    
37.         auto pos = data.find(",", i);
    
38.         if (pos == string::npos)
    
39.             pos = data.size();
    
40.         auto tok = data.substr(i, pos - i);
    
41.         i = pos + 1;
    
42.         
    
43.         TreeNode* t = nullptr;
    
44.         if (tok != "#") {
    
45.             t = new TreeNode(stoi(tok));
    
46.         }
    
47.         return t;
    
48.     }
    
49.     TreeNode * deserialize(string data) {
    
50.         TreeNode* root = nullptr;
    
51.         list<TreeNode*> q;
    
52.         int i = 0;
    
53.         while (i < data.size()) {
    
54.             auto t = getNode(data, i);
    
55.             if (q.empty()) {
    
56.                 root = t;
    
57.                 q.push_back(t);
    
58.                 continue;
    
59.             }
    
60.             TreeNode* parent = q.front(); q.pop_front();
    
61.             parent->left = t;
    
62.             if (t) q.push_back(t);
    
63.             
    
64.             t = getNode(data, i);
    
65.             parent->right = t;
    
66.             if (t) q.push_back(t);
    
67.         }
    
68.         return root;
    
69.     }
    
70. };
    
71. 
    
72. // Your Codec object will be instantiated and called as such:
    
73. // Codec codec;
    
74. // codec.deserialize(codec.serialize(root));

复制代码

621. Task Scheduler

1. /*
   
2.     Take 'AAABBCCDD' as an example.
   
3.     A appears the most (3 times), so we have 2 groups in between 'A's:
   
4.         A  A  A
   
5.     we can insert the rest of the chars into the two groups:
   
6.         A bcd A bcd A
   
7. 
   
8.     Take 'AAABBBCCDD' as an example.
   
9.     A and B appear the most (3 times each), so we put them together and form 2 groups in between:
   
10.         AB  AB  AB
    
11.     between 'AB' we have 2 groups which we can insert chars:
    
12.       AB cd AB cd AB
    
13. */
    
14. class Solution {
    
15. public:
    
16.     int leastInterval(string tasks, int n) {
    
17.         if (tasks.empty()) return 0;
    
18.         
    
19.         const int CHAR_COUNT = 26;
    
20.         int buf[CHAR_COUNT] = {};
    
21.         for (auto& c : tasks) {
    
22.             buf[c - 'A']++;
    
23.         }
    
24.         // sort the array in desc order
    
25.         sort(buf, buf+CHAR_COUNT, [](auto& a, auto& b) {
    
26.             return a > b;
    
27.         });
    
28.         int i = 1;  // find out how many chars have the same count as the first one
    
29.         while (i < CHAR_COUNT && buf[i] == buf[0])
    
30.             ++i;
    
31.         int groups = buf[0] - 1; // groups we can insert chars into
    
32.         return max(groups*(n-i+1) + // how many chars we have to insert into the groups (excluding the most frequent ones)
    
33.                      buf[0]*i,      // number of the most frequent chars
    
34.                       (int)tasks.size());   // in case the most frequent chars are less than the rest, we just fill in the rest into the groups
    
35.     }
    
36. };

复制代码

感觉我刷题有时候不会了或者没思路就想看答案。。。而且会强迫自己背别人的算法。然后mock interview导致自己一点想法没有，还没自信

312. Burst Balloons
Recursive

1. class Solution {
   
2.     int get(const vector<int>& nums, int i) {
   
3.         if (i < 0 || i >= nums.size())
   
4.             return 1;
   
5.         return nums[i];
   
6.     }
   
7.     int check(const vector<int>& nums, int start, int end, vector<vector<int>>& dp ) {
   
8.         if (start > end) return 0;
   
9.         
   
10.         if (dp[start][end] > 0) {
    
11.             return dp[start][end];
    
12.         }
    
13.         int res = nums[start];
    
14.         // iterate assuming nums[i] will be bursted last
    
15.         for (int i = start; i <= end; i++) {
    
16.             int r = check(nums, start, i-1, dp) +
    
17.                        get(nums, start-1)*nums[i]*get(nums, end+1) +
    
18.                         check(nums, i+1, end, dp);
    
19.             res = max(res, r);
    
20.         }
    
21.         dp[start][end] = res;
    
22.         return res;
    
23.     }
    
24. public:
    
25.     int maxCoins(vector<int>& nums) {
    
26.         vector<vector<int>> dp(nums.size(), vector<int>(nums.size(), 0));
    
27.         
    
28.         return check(nums, 0, nums.size()-1, dp);
    
29.     }
    
30. };

复制代码