数组

二分

35.搜索插入位置

1
二分查找  +  target不在数组中, return r + 1;

34.在排序数组中查找元素的第一个和最后一个位置

1
2
3
4
5
6
[3,4,6] target = 2或7，{-1，-1}
[3,4,6] target = 4     {1,1}
[3,4,6] target = 5     {-1,-1}
2个二分查找 寻找左边界和右边界
寻找左边界，nums[target] == target的时候更新right
寻找右边界，nums[target] == target的时候更新left

69.x 的平方根

1
2
3
直接二分查找[0,x] target = x / mid 
特判 x == 0 || x == 1
如果没找到 target, 直接返回 r （舍弃算术平方根的小数部分）

367.有效的完全平方数

1
2
二分查找 [0,num] target = num , 判断 mid * mid == num?
注意将变量设为 long long

双指针

27. 移除元素

1
使用快慢指针，快指针遍历整个数组，慢指针负责寻找不等于val值（本题该移除出来得元素值）的元素，并放进数组里（覆盖）

26.删除有序数组的重复项

1
使用快慢指针，快指针遍历整个数组，慢指针负责寻找不等于val值（本题中的前一个元素值），并放数组里（覆盖）

283.移动零

1
使用快慢指针，快指针遍历整个数组，慢指针负责寻找不等于0的值，最后再将0值覆盖给剩余的元素（注意边界）

844.比较含退格的字符串

1
'#'为删除键，如果为'#',则出栈，如果不为'#'，则入栈

977. 有序数组的平方

1
使用双指针，分别在数组的两端，比较两个指针指向的元素的平方，把较大的放在数组的右边，并移动指针（向中间移动）；只能移动两边中较大的元素，因为无论是正数还是负数，平方后最大的元素只能出现在两边，不能出现在中间！！

滑动窗口

209. 长度最小的子数组
滑动窗口，通过判断数组元素之间的和，对数组长度进行变化

1
2
3
4
5
while (sum >= s) {
              subLength = (j - i + 1); // 取子序列的长度
              result = result < subLength ? result : subLength;
              sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）
          }

904. 水果成篮
思路与算法

我们可以使用滑动窗口解决本题，left 和 right 分别表示满足要求的窗口的左右边界，同时我们使用哈希表存储这个窗口内的数以及出现的次数。

我们每次将 right 移动一个位置，并将 fruits[right] 加入哈希表。如果此时哈希表不满足要求（即哈希表中出现超过两个键值对），那么我们需要不断移动 left，并将 fruits[left] 从哈希表中移除，直到哈希表满足要求为止。

需要注意的是，将 fruits[left]从哈希表中移除后，如果 fruits[left]在哈希表中的出现次数减少为 0，需要将对应的键值对从哈希表中移除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution { public: int totalFruit(vector<int>& fruits){   
          int n = fruits.size(); 
          unordered_map<int, int> cnt; int left = 0, ans = 0; 
          for (int right = 0; right < n; ++right) { 
          ++cnt[fruits[right]]; 
          while (cnt.size() > 2) { 
          auto it = cnt.find(fruits[left]); 
          --it->second; 
          if (it->second == 0) { 
             cnt.erase(it); 
              } 
          ++left; 
      } 
       ans = max(ans, right - left + 1); 
     } 
     return ans; 
   } 
};

76. 最小覆盖子串
滑动窗口—困难

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
class Solution {

    public String minWindow(String s, String t) {

          int slen = s.length();

          int tlen = t.length();

  

          if(slen == 0 || tlen == 0 || slen < tlen){

              return "";

          }

          char[] charArrayS = s.toCharArray();

          char[] charArrayT = t.toCharArray();

  

          int[] winFreq = new int[128];

          int[] tFreq = new int[128];

  

          for(char c : charArrayT){

              tFreq[c]++; //收集 t 中字符个数

          }


          int distance = 0;  // 窗口内 t 字符的个数

          int minLen = slen + 1;

          int begin = 0;

  

          int left = 0,right = 0;

  

          while(right < slen){  //右边界向右滑动，直到滑动窗口内有 t 中所有字符

              if(tFreq[charArrayS[right]] == 0){

                  right++;

                  continue;

              }

  

              if(winFreq[charArrayS[right]] < tFreq[charArrayS[right]]){

                  distance++; // 标记 distance

              }

  

              winFreq[charArrayS[right]]++; // 标记滑动窗口此时最右的字符

              right++; // 向右滑动

  

              while(distance == tlen){  // 滑动窗口内有 t 中所有字符

  

                if(right - left < minLen){

                    minLen = right - left;

                    begin = left;

                }

  

                if(tFreq[charArrayS[left]] == 0){

                  left++;  // 左边界向右滑动

                  continue;

                }


              if(winFreq[charArrayS[left]] == tFreq[charArrayS[left]]){

                  distance--; //标记完 左边界继续向右滑动跳出此循环

              }

  

              winFreq[charArrayS[left]]--;

              left++;

              }

          }

  

          if(minLen == slen + 1){  // 没被赋值的情况

              return "";

          }

  

        return s.substring(begin,begin+minLen);

  

    }

}

59. 螺旋矩阵 II
模拟

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
class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n, 0)); // 使用vector定义一个二维数组
        int startx = 0, starty = 0; // 定义每循环一个圈的起始位置
        int loop = n / 2; // 每个圈循环几次，例如n为奇数3，那么loop = 1 只是循环一圈，矩阵中间的值需要单独处理
        int mid = n / 2; // 矩阵中间的位置，例如：n为3， 中间的位置就是(1，1)，n为5，中间位置为(2, 2)
        int count = 1; // 用来给矩阵中每一个空格赋值
        int offset = 1; // 需要控制每一条边遍历的长度，每次循环右边界收缩一位
        int i,j;
        while (loop --) {
            i = startx;
            j = starty;

            // 下面开始的四个for就是模拟转了一圈
            // 模拟填充上行从左到右(左闭右开)
            for (j = starty; j < n - offset; j++) {
                res[startx][j] = count++;
            }
            // 模拟填充右列从上到下(左闭右开)
            for (i = startx; i < n - offset; i++) {
                res[i][j] = count++;
            }
            // 模拟填充下行从右到左(左闭右开)
            for (; j > starty; j--) {
                res[i][j] = count++;
            }
            // 模拟填充左列从下到上(左闭右开)
            for (; i > startx; i--) {
                res[i][j] = count++;
            }

            // 第二圈开始的时候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
            startx++;
            starty++;

            // offset 控制每一圈里每一条边遍历的长度
            offset += 1;
        }

        // 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
        if (n % 2) {
            res[mid][mid] = count;
        }
        return res;
    }
};