Leetcode 刷题打卡记录 包括Solution

0031. Next Permutation

1. class Solution {
   
2. public:
   
3.     void nextPermutation(vector<int>& nums) {
   
4.         if (nums.empty()) return;
   
5.         // look for the first desc from back
   
6.         int i = nums.size() - 1;
   
7.         while (i > 0) {
   
8.             if (nums[i] > nums[i-1])
   
9.                 break;
   
10.             i--;
    
11.         }
    
12.         // the last perm, go back to the original state
    
13.         if (i == 0) {
    
14.             sort(nums.begin(), nums.end());
    
15.             return;
    
16.         }
    
17.         // find the next large number for nums[i-1] behind it
    
18.         sort(nums.begin()+i, nums.end());
    
19.         auto it = upper_bound(nums.begin()+i, nums.end(), nums[i-1]);
    
20.         swap(*(nums.begin()+i-1), *it);
    
21.         sort(nums.begin()+i, nums.end());
    
22.         
    
23.     }
    
24. };

复制代码

0036. Valid Sudoku

1. class Solution {
   
2. public:
   
3.     bool isValidSudoku(vector<vector<char>>& board) {
   
4. 
   
5.         for (int i = 0; i < board.size(); i++) {
   
6.             int buf_r[256] = {0};
   
7.             int buf_c[256] = {0};
   
8.             for (int j = 0; j < board[i].size(); j++) {
   
9.                 // rows
   
10.                 char c = board[i][j];
    
11.                 if (c != '.') {
    
12.                     if (buf_r[c] != 0)
    
13.                         return false;
    
14.                     buf_r[c] = 1;
    
15.                 }
    
16.                 // cols
    
17.                 c = board[j][i];
    
18.                 if (c != '.') {
    
19.                     if (buf_c[c] != 0)
    
20.                         return false;
    
21.                     buf_c[c] = 1;
    
22.                 }
    
23.             }
    
24.         }
    
25.         // diags
    
26.         for (int i = 0; i < board.size(); i+=3) {
    
27.             for (int j = 0; j < board[i].size(); j+=3) {
    
28.                 int buf_x[256] = {0};
    
29.                 for (int k = 0; k < 9; k++) {
    
30.                     char c = board[i + k/3][j + k%3];
    
31.                     if (c != '.') {
    
32.                         if (buf_x[c] != 0)
    
33.                             return false;
    
34.                         buf_x[c] = 1;
    
35.                     }
    
36.                 }
    
37.             }
    
38.         }
    
39.         return true;
    
40.     }
    
41. };

复制代码

0037. Sudoku Solver

1. class Solution {
   
2. private:
   
3.     vector<vector<bool>> bufRows = vector<vector<bool>>(9, vector<bool>(256, false));
   
4.     vector<vector<bool>> bufCols = vector<vector<bool>>(9, vector<bool>(256, false));
   
5.     vector<vector<bool>> bufDias = vector<vector<bool>>(9, vector<bool>(256, false));
   
6. public:
   
7.     bool isValid(vector<vector<char>>& board, int i, int j, char c) {
   
8.         return !bufRows[i][c]
   
9.             && !bufCols[j][c]
   
10.             && !bufDias[i/3*3 + j/3][c];
    
11.     }
    
12.     void setFlag(vector<vector<char>>& board, int i, int j, char c, bool value) {
    
13.         bufRows[i][c] = value;
    
14.         bufCols[j][c] = value;
    
15.         bufDias[i/3*3 + j/3][c] = value;
    
16.     }
    
17.     bool solve(vector<vector<char>>& board, int i, int j) {
    
18.         if (i == 9) return true;
    
19.         if (j == 9) return solve(board, i+1, 0);
    
20.         
    
21.         char c = board[i][j];
    
22.         if (c != '.') return solve(board, i, j+1);
    
23.         
    
24.         for (char d = '1'; d <= '9'; d++) {
    
25.             if (!isValid(board,i, j, d))
    
26.                 continue;
    
27.             setFlag(board, i, j, d, true);
    
28.             board[i][j] = d;
    
29.             if (solve(board, i, j+1))
    
30.                 return true;
    
31.             board[i][j] = '.';
    
32.             setFlag(board, i, j, d, false);
    
33.         }
    
34.         return false;
    
35.     }
    
36.     void solveSudoku(vector<vector<char>>& board) {
    
37.        for (int i = 0; i < 9; i++) {
    
38.            for (int j = 0; j < 9; j++) {
    
39.                char c = board[i][j];
    
40.                if (c == '.')
    
41.                    continue;
    
42.                bufRows[i][c] = true;
    
43.                bufCols[j][c] = true;
    
44.                bufDias[i/3*3 + j/3][c] = true;
    
45.            }
    
46.        }
    
47.         solve(board, 0, 0);
    
48.     }
    
49. };
    
50. ```
    
51. ```c++
    
52. class Solution {
    
53. public:
    
54.     bool validatePos(const vector<vector<char>>& board, int i, int j) {
    
55.         // vertical
    
56.         vector<bool> vcols(9, false);
    
57.         for (int m = 0; m < 9; m++) {
    
58.             // cols
    
59.             if (board[m][j] == '.') continue;
    
60.             
    
61.             int num = board[m][j] - '1';
    
62.             if (vcols[num]) {
    
63.                 return false;
    
64.             }
    
65.             vcols[num] = true;
    
66.         }
    
67.         // 3x3
    
68.         vector<bool> vsqrs(9, false);
    
69.         int basei = i/3*3;
    
70.         int basej = j/3*3;
    
71.         for (int m = 0; m < 9; m++) {
    
72.             char c = board[basei+m/3][basej+m%3];
    
73.             if (c == '.') continue;
    
74.             int num = c - '1';
    
75.             if (vsqrs[num]) return false;
    
76.             vsqrs[num] = true;
    
77.         }
    
78.         return true;
    
79.     }
    
80.     bool tryNext(vector<vector<char>>& board, vector<vector<bool>>& cache) {
    
81.         bool started = false;
    
82.         for (int i = 0; i < 9; i++) {
    
83.             for (int j = 0; j < 9; j++) {
    
84.                 char c = board[i][j];
    
85.                 if (c != '.') continue;
    
86.                
    
87.                 // try every possible values
    
88.                 for (int m = 0; m < 9; m++) {
    
89.                     if (!cache[i][m]) continue;
    
90. 
    
91.                     board[i][j] = m + '1';
    
92.                     cache[i][m] = false;
    
93.                     if (validatePos(board, i, j)
    
94.                         && tryNext(board, cache)) {
    
95.                         return true;
    
96.                     }
    
97.                     board[i][j] = '.';
    
98.                     cache[i][m] = true;
    
99.                 }
    
100.                 // tried every possible ways still no luck, must have made a wrong attempt
     
101.                 return false;
     
102.             }
     
103.         }
     
104.         // nothing left to guess
     
105.         return true;
     
106.     }
     
107.     void solveSudoku(vector<vector<char>>& board) {
     
108.         // pre-calc per row
     
109.         vector<vector<bool>> cache(9, vector<bool>(9, true));
     
110.         for (int i = 0; i < 9; i++) {
     
111.             for (int j = 0; j < 9; j++) {
     
112.                 char c = board[i][j];
     
113.                 if (c != '.') {
     
114.                     cache[i][c - '1'] = false;
     
115.                 }
     
116.             }
     
117.         }
     
118.         tryNext(board, cache);
     
119.     }
     
120. };

复制代码

0038. Count and Say

1. class Solution {
   
2. public:
   
3.     string countAndSay(int n) {
   
4.         string base = "1";
   
5.         if (n < 2) return base;
   
6. 
   
7.         while (n > 1) {
   
8.             n--;
   
9.             string out = "";
   
10.             int idx = 0;
    
11.             while (idx < base.size()) {
    
12.                 int count = 0;
    
13.                 char c = base[idx];
    
14.                 int i = idx;
    
15.                 for(; i < base.size(); i++) {
    
16.                     if (base[i] != c) break;
    
17.                     count++;
    
18.                 }
    
19.                 out += to_string(count) + c;
    
20.                 idx = i;
    
21.             }
    
22.             base = out;
    
23.         }
    
24.         return base;
    
25.     }
    
26. };
    
27. 
    
28. int main(int argc, char* argv[]) {
    
29.     cout << Solution().countAndSay(10) << endl;
    
30. 
    
31.     return 0;
    
32. }

复制代码

0042. Trapping Rain Water

1. class Solution {
   
2. public:
   
3.     int accumulateWater(const vector<int>& height, int left, int right) {
   
4.         int topH = min(height[left], height[right]);
   
5.         int res = 0;
   
6.         for (int i = left + 1; i < right; i++) {
   
7.             if (height[i] < topH) {
   
8.                 res += topH - height[i];
   
9.             }
   
10.         }
    
11.         return res;
    
12.     }
    
13.     int trap(vector<int>& height, int l, int r) {
    
14.         int left = l;
    
15.         int i = left + 1;
    
16.         int maxH = i;
    
17.         int res = 0;
    
18.         while (i <= r) {
    
19.             if (height[i] > height[maxH])
    
20.                 maxH = i;
    
21.             // a bar is same or higher than left bar
    
22.             if (height[i] >= height[left]) {
    
23.                 res += accumulateWater(height, left, i);
    
24.                 left = i++;
    
25.                 maxH = i;
    
26.                 continue;
    
27.             }
    
28.             i++;
    
29.         }
    
30.         // left is the highest
    
31.         if (left < r - 1) {
    
32.             res += accumulateWater(height, left, maxH);
    
33.             return res + trap(height, maxH, r);
    
34.         }
    
35.         return res;
    
36.     }
    
37.     int trap(vector<int>& height) {
    
38.         return trap(height, 0, height.size()-1);
    
39.     }
    
40. };

复制代码

0045. Jump Game II

1. class Solution {
   
2. public:
   
3.     int jump(vector<int>& nums) {
   
4.         if (nums.size() < 2)
   
5.             return 0;
   
6.         int ret = 0;
   
7.         int i = 0;
   
8.         while (i < nums.size()-1) {
   
9.             int val = nums[i];
   
10.             if (i + val >= nums.size() - 1) {
    
11.                 ret++;
    
12.                 break;
    
13.             }
    
14.             int maxj = 0;
    
15.             int nexti = i + 1;
    
16.             for (int j = 1; j <= val; j++) {
    
17.                 if (nums[i+j] + j > maxj) {
    
18.                     maxj = nums[i+j] + j;
    
19.                     nexti = i + j;
    
20.                 }
    
21.             }
    
22.             i = nexti;
    
23.             ret++;
    
24.         }
    
25.         return ret;
    
26.     }
    
27. };
    
28. ```
    
29. ```c++
    
30. // count backwards
    
31. class Solution {
    
32. public:
    
33.     int jump(vector<int>& nums) {
    
34.         if (nums.size() < 2)
    
35.             return 0;
    
36.         if (nums.size() < 3) {
    
37.             return 1;
    
38.         }
    
39.         vector<int> v(nums.size(), nums.size()+1);
    
40.         v[nums.size()-1] = 0;
    
41.         v[nums.size()-2] = 1;
    
42.         for (int i = nums.size()-3; i >= 0; i--) {
    
43.             for (int j = 1; j <= nums[i]; j++) {
    
44.                 if (i+j >= nums.size())
    
45.                     break;
    
46.                 v[i] = min(v[i], v[i+j]+1);
    
47.             }
    
48.         }
    
49.         return v[0];
    
50.     }
    
51. };

复制代码

0054. Spiral Matrix

1. class Solution {
   
2. public:
   
3.     vector<int> spiralOrder(vector<vector<int>>& matrix) {
   
4.         if (matrix.empty() || matrix[0].empty())
   
5.             return vector<int>();
   
6.         
   
7.         vector<int> res;
   
8.         int m = matrix.size();
   
9.         int n = matrix[0].size();
   
10.         int layer = 0;
    
11.         int i = 0, j = 0;
    
12.         while(layer <= (min(m,n)-1)/2) {
    
13.             res.push_back(matrix[i][j]);
    
14.             // to right
    
15.             if (j < n - layer) {
    
16.                 j++;
    
17.                 while(j < n - layer) {
    
18.                     res.push_back(matrix[i][j]);
    
19.                     j++;
    
20.                 }
    
21.                 j--;
    
22.             }
    
23.             // to bottom
    
24.             if (i >= m - 1 - layer)
    
25.                 break;
    
26.             i++;
    
27.             while (i < m - layer) {
    
28.                 res.push_back(matrix[i][j]);
    
29.                 i++;
    
30.             }
    
31.             i--;
    
32.             
    
33.             // to left
    
34.             if (j <= layer)
    
35.                 break;
    
36.             j--;
    
37.             while (j >= layer) {
    
38.                 res.push_back(matrix[i][j]);
    
39.                 j--;
    
40.             }
    
41.             j++;
    
42.             
    
43.             // to top
    
44.             if (i <= layer)
    
45.                 break;
    
46.             i--;
    
47.             while (i > layer) {
    
48.                 res.push_back(matrix[i][j]);
    
49.                 i--;
    
50.             }
    
51.             layer++;
    
52.             i = layer;
    
53.             j = layer;
    
54.         }
    
55.         return res;
    
56.     }
    
57. };

复制代码

0055. Jump Game

1. class Solution {
   
2. public:
   
3.     bool canJump(vector<int>& nums) {
   
4.             int maxj = 0;
   
5.             for (int i = 0; i < nums.size(); i ++) {
   
6.                 if (i > maxj)
   
7.                     return false;
   
8.                 maxj = max(maxj, nums[i] + i);
   
9.                 if (maxj >= nums.size() - 1)
   
10.                     return true;
    
11.             }
    
12.         return false;
    
13.     }
    
14. };
    
15. 
    
16. int main(int argc, char* argv[]) {
    
17.     vector<vector<int>> v = {
    
18.         {3,2,1,0,4},
    
19.         {5,9,3,2,1,0,2,3,3,1,0,0}
    
20.         };
    
21.    
    
22.     for (auto vv : v)
    
23.      cout << Solution().canJump(vv) << endl;
    
24.     return 0;
    
25. }

复制代码

0056. Merge Intervals

1. struct Interval {
   
2.     int start;
   
3.     int end;
   
4.     Interval() : start(0), end(0) {}
   
5.     Interval(int s, int e) : start(s), end(e) {}
   
6. };
   
7. 
   
8. class Solution {
   
9. public:
   
10.     vector<Interval> merge(vector<Interval>& intervals) {
    
11.         if (intervals.size() < 2)
    
12.             return intervals;
    
13. 
    
14.         sort(intervals.begin(), intervals.end(), [](Interval& a, Interval& b) {
    
15.             return a.start < b.start;
    
16.         });
    
17.         vector<Interval> res;
    
18.         int i = 0;
    
19.         while (i < intervals.size() - 1) {
    
20.             auto& a = intervals[i];
    
21.             auto& b = intervals[i+1];
    
22.             if (a.end < b.start) {
    
23.                 res.push_back(a);
    
24.             } else {
    
25.                 b.start = a.start;
    
26.                 b.end = max(b.end, a.end);
    
27.             }
    
28.             i++;
    
29.         }
    
30.         res.push_back(intervals[intervals.size() - 1]);
    
31.         return res;
    
32.     }
    
33. };
    
34. 
    
35. int main(int argc, char* argv[]) {
    
36.     vector<Interval> v = {
    
37.         Interval(1,5),
    
38.         Interval(3,2),
    
39.         Interval(5,8)
    
40.         };
    
41. 
    
42.     auto vv = Solution().merge(v);
    
43.     for(auto a : vv)   
    
44.         cout << a.start << ' ' << a.end << endl;
    
45.     return 0;
    
46. }

复制代码

0057. Insert Interval

1. class Solution {
   
2. public:
   
3.     vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
   
4.         if (intervals.empty()) {
   
5.             vector<Interval> res;
   
6.             res.push_back(newInterval);
   
7.             return res;
   
8.         }
   
9. 
   
10.         sort(intervals.begin(), intervals.end(), [](Interval&a, Interval& b) {
    
11.             return a.start < b.start;
    
12.         });
    
13. 
    
14.         if (newInterval.end < intervals[0].start) {
    
15.             intervals.insert(intervals.begin(), newInterval);
    
16.             return intervals;
    
17.         }
    
18.         vector<Interval> res;
    
19.         auto n = newInterval;
    
20.         for (int i = 0; i < intervals.size(); i++) {
    
21.             auto& t = intervals[i];
    
22.             // the new is after t, put t in res
    
23.             if (n.start > t.end) {
    
24.                 res.push_back(t);
    
25.                 continue;
    
26.             }
    
27.             // the new is before t
    
28.             if (n.end < t.start) {
    
29.                 res.push_back(n);
    
30.                 res.insert(res.end(), intervals.begin()+i, intervals.end());
    
31.                 return res;
    
32.             }
    
33.             // need merge
    
34.             n.start = min(n.start, t.start);
    
35.             n.end = max(n.end, t.end);
    
36.         }
    
37.         res.push_back(n);
    
38.         return res;
    
39.     }
    
40. };

复制代码