代码随想录刷题随记2：有序数组的平方，滑动窗口，螺旋矩阵II

代码随想录刷题随记2

977. 有序数组的平方

主要需要注意的是数组里面有负数所以平方以后可能不再满足递增的关系
暴力解法是平方以后对数组进行排序这样的复杂度是$O(NlogN+N)$

双指针方法

leetcode链接
题解链接
尽管负数平方后可能存在最大值，最大值也只能从数组的两端挑选出来。所以取两个指针分别指向数组的两端，找出最大值进行填充，然后指针移动。这样的复杂度可以达到O(N)
解题代码：

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
    int leftptr=0;
    int rightptr=nums.size()-1;
    vector<int> newnum=vector<int>(nums.size(),0);
    int index=nums.size()-1;
    while(index>=0){
       int left= nums[leftptr]*nums[leftptr];
       int right=nums[rightptr]*nums[rightptr];
       left>right? newnum[index]=left:newnum[index]=right;
       left>right? leftptr++:rightptr--;
       index--;
    }
    return  newnum;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

209. 长度最小的子数组

leetcode链接

这道题目暴力解法当然是 两个for循环，然后不断的寻找符合条件的子序列，也就是说每个位置都可能是子序列的起点。时间复杂度是O(n^2)。
从暴力解法中可以看出一点滑动的影子，所以可以利用滑动窗口的方法尝试解决此问题。
滑动窗口常见的结构是维护窗口内的最大值或者最小值问题
滑动窗口结构可以用双端队列的方式实现也可以用双指针的形式实现
参考题解
解题代码：

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
    int startptr=0;
    int endptr=0;
    int retlen=INT32_MAX;
    int sum=0;
    for(endptr=0;endptr<nums.size();endptr++){
        sum+=nums[endptr];
        while(sum>=target){//注意这里是while 而不是if
            int length=endptr-startptr+1;
            retlen=length>retlen?retlen:length;
            sum-=nums[startptr++];
        }
    }
    return retlen==INT32_MAX? 0:retlen;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

每个元素在滑动窗后进来操作一次，出去操作一次，每个元素都是被操作两次，所以时间复杂度是 2 × n 也就是O(n)。

59.螺旋矩阵II

leetcode链接
本题并不涉及到什么算法，就是纯按照螺旋的规则填充二维数组。
看了一下卡哥的解题思路，感觉对我来说还是有亿点抽象了，尝试用有限状态机的思路模拟了一下，发现是可以oc的而且代码看着更好理解一些。
解题代码如下：

enum class STATE {
    Right,
    Down,
    Left,
    Up
};

class Solution {
public:
    
    vector<vector<int>> generateMatrix(int n) {
        STATE  st=STATE::Right;
        vector<vector<int>> matrix(n,vector<int>(n,0));
        int num=n;
        int count=1;
        int c=n*n;
        int pos_x=0;
        int pos_y=0;
        while(c>0){
         matrix[pos_x][pos_y]=count;
         count++;
         num--;
         if(num<=0){
           //换状态
           switch (st){
            case STATE::Right :
                 st=STATE::Down;
                 n=n-1;
                 pos_x=pos_x+1;
                 break;
            case STATE::Down:
                 st=STATE::Left;
                 n=n;
                 pos_y=pos_y-1;
                 break;
            case STATE::Up:
                 st=STATE::Right;
                 n=n;
                 pos_y=pos_y+1;
                 break;
            case STATE::Left:
                 st=STATE::Up;
                 n=n-1;
                 pos_x=pos_x-1;
                 break;
           }
           num=n;
           
         }
         else{
             switch (st){
            case STATE::Right :
                 pos_y=pos_y+1;
                 break;
            case STATE::Down:
                 pos_x=pos_x+1;
                 break;
            case STATE::Up:
                pos_x=pos_x-1;
                 break;
            case STATE::Left:
                pos_y=pos_y-1;
                 break;
             }
         }  
         c--;
        }
        return matrix;
    }
};
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