1.有序数组的平方

题目链接：https://leetcode.cn/problems/squares-of-a-sorted-array/

1.1 暴力思路

  • 让数组每个元素等于本身的平方
  • sort 从小到大排序
1
2
3
4
5
6
7
8
9
10
11
12
// 时间复杂度 O(logn)
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int len = nums.size();
        for(int i = 0; i < len;++i) {
            nums[i] = nums[i] * nums[i];
        }
        sort(nums.begin(),nums.end());
        return nums;
    }
};

1.2 双指针思路

图片链接： 代码随想录 (programmercarl.com)

滑动窗口思想

  • 设立一个新数组（牺牲空间换时间）

  • 两个指针 left = 0， right = 长度 - 1

  • 因为题目明确说明 数组是单调不减的，所以数组两端的数平方必定是最大的，中间的数平方反而最小
    举例 [-6,-3,2,7,8]
    平方 [36,9,4,49,64]
    所以设立两个指针指向两端比较大小，如果right大，添加完要–。

  • 新申请的数组，从末尾添加元素，所以k为数组最后一位，依次向前

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 时间复杂度 O(n)
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int len = nums.size();
        vector<int> arr(len,0);
        int k = len - 1;
        int left = 0;
        int right = len -1;
        while (left <= right) {
            int num1 = nums[left] * nums[left];
            int num2 = nums[right] * nums[right];
            if(num1 >= num2) {
                arr[k--] = num1;
                left++;
            } else {
                arr[k--] =num2;
                right--;
            }

        }
        return arr;
    }
};

2 最小数组和

题目链接： 209. 长度最小的子数组 - 力扣（LeetCode）

2.1 暴力思路

简单的双重for循环，不举例讲解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int result = INT32_MAX; // 最终的结果
        int sum = 0; // 子序列的数值之和
        int subLength = 0; // 子序列的长度
        for (int i = 0; i < nums.size(); i++) { // 设置子序列起点为i
            sum = 0;
            for (int j = i; j < nums.size(); j++) { // 设置子序列终止位置为j
                sum += nums[j];
                if (sum >= s) { // 一旦发现子序列和超过了s，更新result
                    subLength = j - i + 1; // 取子序列的长度
                    result = result < subLength ? result : subLength;
                    break; // 因为我们是找符合条件最短的子序列，所以一旦符合条件就break
                }
            }
        }
        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
        return result == INT32_MAX ? 0 : result;
    }
};

2.2 双指针思路（滑动窗口）

引用图片链接： 代码随想录 (programmercarl.com)

  • 可以理解为 一个left指针，一个right指针

  • 开始left从0保持不动，right依次向右，直到sum的累加和 >= targht

  • 到达 targht后，就要保持 right不动，left向右，sum 减去left之前指向的元素，因为这样能求出sum >= targht的最小区间长度。

    1
    2
    sum -= arr[left];
    left++;

  • 然后直到 sum < targht，right继续向右，再次 >= targht，然后left继续右移，求最小区间长度

  • 这里值得一提的是：不能用 if 判断 sum >= targht，因为if只会判断一次，left 不会依次向后，一定要用while 来找出最小长度。

    1
    2
    3
    4
    5
    while(sum >= target) {
                    ans = min(ans, right - left);
                    sum -= nums[left];
                    left++;
                }

209.长度最小的子数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int len = nums.size();
        int sum = 0;
        int right = 0;
        int left = 0;
        int ans = len+10;
        for(right = 0; right < len;) {
            if(sum < target) {
                sum+=nums[right];
                right++;    
            }
            while(sum >= target) {
                ans = min(ans, right - left);
                sum -= nums[left];
                left++;
            }
            
        }
        return (ans == len + 10 ? 0 : ans);
    }
};

3.螺旋矩阵

题目链接：59. 螺旋矩阵 II - 力扣（LeetCode）

  • 这个题一开始没思路，后面看了卡哥讲解的视频才清楚

  • 主要判断临界条件，什么时候填入，什么时候不填入

  • 这里是采用了 左闭右开 的思路，就是不填入每一行每一列的最后一个元素，在下一个行/列填充开头。

  • 所以 设立的开始 横轴坐标 startx，开始的纵轴坐标 starty，以及位置终止变量 offset（就是判断什么时候填入元素停止输入的值）。

  • 需要注意的是，一共会进行 n / 2 次循环，当n位奇数时会剩下最中间一个元素，特判就行。

  • 详细讲解可以看卡哥的视频

    题目建议： 本题关键还是在转圈的逻辑，在二分搜索中提到的区间定义，在这里又用上了。

    题目链接：https://leetcode.cn/problems/spiral-matrix-ii/

    文章讲解：https://programmercarl.com/0059.%E8%9E%BA%E6%97%8B%E7%9F%A9%E9%98%B5II.html

    视频讲解：https://www.bilibili.com/video/BV1SL4y1N7mV/

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
class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {

        vector<vector<int>> arr(n,vector<int>(n,0));

        int startx = 0;
        int starty = 0;
        int offset = 1;
        int count = 1;
        int i = 0,j = 0;
        int number = n / 2;
        while(number--) {
            
            for(j; j < n - offset;j++) {
                arr[startx][j] = count++;    
            }
            for(i; i < n - offset;i++) {
                arr[i][j] = count++;
            }
            for(;j > starty;--j) {
                arr[i][j] = count++;
             }
            for(;i > startx;--i) {
                 arr[i][j] = count++;
             }
            startx++;
            starty++;
            offset++;

            i = startx;
            j = starty;
        }

        if(n % 2 != 0) {
            arr[i][j] = count;
        }

        return arr;
        
    }
};