Leetcode 刷题打卡记录 包括Solution

0058. Length of Last Word

1. class Solution {
   
2. public:
   
3.     int lengthOfLastWord(string s) {
   
4.         if (s.empty()) return 0;
   
5.         
   
6.         int i = s.size()-1;
   
7.         while (i >= 0 && s[i] == ' ')
   
8.             i--;
   
9.         if (i < 0) return 0;
   
10.         
    
11.         int j = i;
    
12.         while (i >= 0 && s[i] != ' ')
    
13.             i--;
    
14.         return j - i;
    
15.     }
    
16. };
    

复制代码

0059. Spiral Matrix II

1. class Solution {
   
2. public:
   
3.     vector<vector<int>> generateMatrix(int n) {
   
4.         vector<vector<int>> v(n, vector<int>(n, 0));
   
5.         int k = 1;
   
6.         int layer = 0;
   
7.         int i = 0, j = 0;
   
8.         while (layer <= (n-1)/2) {
   
9.             // to right
   
10.             while (j < n - layer) {
    
11.                 v[i][j] = k++;
    
12.                 j++;
    
13.             }
    
14.             j--;
    
15.             if (k > n*n) break;
    
16.             
    
17.             // to bottom
    
18.             i++;
    
19.             while (i < n - layer) {
    
20.                 v[i][j] = k++;
    
21.                 i++;
    
22.             }
    
23.             i--;
    
24.             // to left
    
25.             j--;
    
26.             while (j >= layer) {
    
27.                 v[i][j] = k++;
    
28.                 j--;
    
29.             }
    
30.             j++;
    
31.             // to top
    
32.             i--;
    
33.             while (i > layer) {
    
34.                 v[i][j] = k++;
    
35.                 i--;
    
36.             }
    
37.             i++;
    
38.             if (k > n*n) break;
    
39.             
    
40.             layer++;
    
41.             i = j = layer;
    
42.         }
    
43.         return v;
    
44.     }
    
45. };

复制代码

0072 Edit Distance

1. class Solution {
   
2. public:
   
3.     int minDistance(string word1, string word2) {
   
4.         int len1 = word1.size();
   
5.         int len2 = word2.size();
   
6.         vector<vector<int>> dp(len1+1, vector<int>(len2+1, 0));
   
7.         for (int i = 0; i <= len1; i++) {
   
8.             dp[i][0] = i;
   
9.             for (int j = 1; j <= len2; j++) {
   
10.                 if (i == 0) dp[0][j] = j;
    
11.                 else {
    
12.                     if (word1[i-1] == word2[j-1])
    
13.                         dp[i][j] = dp[i-1][j-1];
    
14.                     else {
    
15.                         dp[i][j] = 1 + min(dp[i-1][j-1],  // replace
    
16.                                           min(dp[i-1][j], // delete
    
17.                                              dp[i][j-1])); // insert
    
18.                     }
    
19.                 }
    
20.             }
    
21.         }
    
22.         return dp[len1][len2];
    
23.     }
    
24. };

复制代码

0073

1. class Solution {
   
2. public:
   
3.     void setZeroes(vector<vector<int>>& matrix) {
   
4.         if (matrix.empty()) return;
   
5.         
   
6.         vector<int> rows(matrix.size());
   
7.         vector<int> cols(matrix[0].size());
   
8.         for (int i = 0; i < rows.size(); i++) {
   
9.             for (int j = 0; j < cols.size(); j++) {
   
10.                 if (matrix[i][j] == 0) {
    
11.                     rows[i] = 1;
    
12.                     cols[j] = 1;
    
13.                 }
    
14.             }
    
15.         }
    
16.         
    
17.         for (int i = 0; i < rows.size(); i++) {
    
18.             for (int j = 0; j < cols.size(); j++) {
    
19.                 if (rows[i] == 1 || cols[j] == 1) {
    
20.                     matrix[i][j] = 0;
    
21.                 }
    
22.             }
    
23.         }
    
24.     }
    
25. };

复制代码

Set Matrix Zeroes

0074 Search a 2D Matrix

1. class Solution {
   
2. public:
   
3.     bool searchMatrix(vector<vector<int>>& matrix, int target) {
   
4.         if (matrix.empty()) return false;
   
5.         
   
6.         int m = matrix.size();
   
7.         int n = matrix[0].size();
   
8.         int r1 = 0, r2 = m - 1;
   
9.         int c1 = 0, c2 = n - 1;
   
10.         while (r1 <= r2 && c1 <= c2) {
    
11.             if (r1 < r2) {
    
12.                 int rm = (r1 + r2)/2;
    
13.                 int r = matrix[rm][0];
    
14.                 if (r == target) return true;
    
15.                 if (r > target) {
    
16.                     if (rm > 0 && matrix[rm-1][0] <= target) {
    
17.                         r1 = r2 = rm -1;
    
18.                         continue;
    
19.                     }
    
20.                     r2 = rm - 1;
    
21.                 } else { // rm < target
    
22.                     if (matrix[rm][n-1] >= target) {
    
23.                         r1 = r2 = rm;
    
24.                         continue;
    
25.                     }
    
26.                     r1 = rm + 1;
    
27.                 }
    
28.             } else { // fixed a row
    
29.                 int cm = (c1 + c2)/2;
    
30.                 int r = matrix[r1][cm];
    
31.                 if (r == target) return true;
    
32.                 if (r > target) {
    
33.                     c2 = cm - 1;
    
34.                 } else {
    
35.                     c1 = cm + 1;
    
36.                 }
    
37.             }
    
38.         }
    
39.         return false;
    
40.     }
    
41. };
    
42. 
    
43. int main(int argc, char* argv[]) {
    
44. 
    
45.     while (true) {
    
46.         int n;
    
47.         cin >> n;
    
48.         vector<vector<int>> v = {
    
49.             {1,3,5,7}, {10,11,16,20},{23,30,34,50}
    
50. 
    
51.         };
    
52.         
    
53.         cout << boolalpha << Solution().searchMatrix(v, n);
    
54.         cout << endl;
    
55.     }
    
56.     return 0;
    
57. }

复制代码

0075 Sort Colors

1. class Solution {
   
2. public:
   
3.     void sortColors(vector<int>& nums) {
   
4.         int b = nums.size()-1;
   
5.         int r = 0;
   
6.         int i = 0;
   
7.         while (i < nums.size()) {
   
8.             int clr = nums[i];
   
9.             if (clr == 2) {
   
10.                 if (i >= b) return;
    
11.                 swap(nums[i], nums[b]);
    
12.                 b--;
    
13.                 continue;
    
14.             }
    
15.             if (clr == 0) {
    
16.                 //if (r >= i) return;
    
17.                 swap(nums[i], nums[r]);
    
18.                 r++;
    
19.                 i++;
    
20.                 continue;
    
21.             }
    
22.             i++;
    
23.         }
    
24.     }
    
25. };

复制代码

不错不错好多我也做过了～加油！

LZ加油！

0076 Minimum Window Substring

1. class Solution {
   
2. public:
   
3.     string minWindow(string s, string t) {
   
4.         vector<int> buf(256, 0);
   
5.         for (int i = 0; i < t.size(); i++) {
   
6.             buf[t[i]]++;
   
7.         }
   
8.         int head = 0, start = 0, minLen = INT_MAX;
   
9.         int charsToFind = 0;
   
10.         for (int i = 0; i < s.size(); i++) {
    
11.             char c = s[i];
    
12.             // buf[c] == 0 means the char is in buf but already have enough number of that char
    
13.             if (buf[c]-- <= 0) continue;
    
14.             
    
15.             charsToFind++;
    
16.             if (charsToFind == t.size()) {
    
17.                 // slide left to minimum window
    
18.                 while (buf[s[head]]++ < 0) ++head;
    
19.                 if (i - head + 1 < minLen) {
    
20.                     minLen = i - head + 1;
    
21.                     start = head;
    
22.                 }
    
23.                
    
24.                 ++head;
    
25.                 --charsToFind;
    
26.             }
    
27.         }
    
28.         if (minLen > s.size()) return string("");
    
29.         return s.substr(start, minLen);
    
30.     }
    
31. };

复制代码