代码随想录算法训练营第二天 | LeetCode 997. 有序数组的平方、LeetCode 209. 长度最小的子数组、LeetCode 59.螺旋矩阵II

LeetCode 997. 有序数组的平方

 https://leetcode.cn/problems/squares-of-a-sorted-array/

暴力解法

int* sortedSquares(int* nums, int numsSize, int* returnSize){
    *returnSize=numsSize;
    for(int i=0;i<numsSize;i++){
        nums[i]=nums[i]*nums[i];
    }
   for(int i=0;i<numsSize;i++){
       for (int j = 0; j < numsSize - 1 - i; ++j) {
           if(nums[j]>nums[j+1]){
               int temp=nums[j];
               nums[j]=nums[j+1];
               nums[j+1]=temp;
           }
       }
   }
    return nums;
}

双指针法

int* sortedSquares(int* nums, int numsSize, int* returnSize){
    *returnSize=numsSize;
    int i=0,j=numsSize-1;
    int k=numsSize-1;
    while(i<=j){
        if(nums[i]*nums[i]>nums[j]* nums[j]){
            returnSize[k--]=nums[i]*nums[i];
            i++;
        }
        else {
            returnSize[k--]=nums[j]*nums[j];
            j--;
        }

    }
    return returnSize;
}

 LeetCode 209. 长度最小的子数组

https://leetcode.cn/problems/minimum-size-subarray-sum/

第一想法是暴力，然后debug了好几次，时间复杂度也比较大，不能成功ac

int minSubArrayLen(int target, int* nums, int numsSize){
    int min=numsSize;
    int temp;
    int flag=0;
    for(int i=0;i<numsSize;i++){
        int sum=nums[i];
        if(sum<target) {
            for (int j = i + 1; j < numsSize; j++) {

                sum += nums[j];
                if (sum >= target){
                    flag=1;temp = j - i + 1;
                    break;
                }
            }
        }
        else temp=1,flag=1;
        min=(min>temp?temp:min);
    }
    if(flag==0)return 0;
    return min;
}

下面是滑动窗口法（双指针法），滑动窗口法也就是用一个变量j存储末尾位置的下标，用另一个变量i存储开始位置的下标，j采用for循环不断更新直到sum大于等于target，此时更新变量i即开始位置，注意需要用while使开始位置不断向右移动直到sum小于target，用if则只能更新一些i的位置。

int minSubArrayLen(int target, int* nums, int numsSize){
    int min=numsSize+1;
    int i=0;
    int length;
    int sum=0;
    for (int j = 0; j < numsSize; ++j) {//j表示终止位置
        sum+=nums[j];
        while(sum>=target){
            length=j-i+1;
            min=(length>min?min:length);
            sum-=nums[i];
            i++;
        }
    }
    return (min==numsSize+1?0:min);//注意nums数组没有符合的子数组的情况返回0
}

 LeetCode 59.螺旋矩阵II

https://leetcode.cn/problems/spiral-matrix-ii/

这题是一道模拟题，要注意好区间是左开右闭还是左闭右开，下面我采用左闭右开法，难点在于模拟四条边的过程和各个变量的更新

int** generateMatrix1(int n, int* returnSize, int** returnColumnSizes){
    *returnSize = n;
    *returnColumnSizes = (int*)malloc(sizeof(int) * n);
    //初始化返回结果数组re
    int** re = (int**)malloc(sizeof(int*) * n);
    for(int i = 0; i < n; i++) {
        re[i] = (int*)malloc(sizeof(int) * n);
        (*returnColumnSizes)[i] = n;
    }
    int num=1;
    int startx=0;//横向起始位置（i)
    int starty=0;//纵向起始位置（y)
    int offset=1;//偏移量
    int count=1;
    int i,j;
    int loop=n/2;//圈数
    while(loop){

        for( j=starty;j<n-offset;j++) {//第一条边
            re[startx][j] = count++;
        }
        for( i=startx;i<n-offset;i++){//第二条边，此时j已经变成n-offset
            re[i][j]=count++;
        }
        for(;j>starty;j--){//第三条边，此时i已经变成n-offset
            re[i][j]=count++;
        }
        for(;i>startx;i--){//第四条边，此时j已经变成starty
            re[i][j]=count++;
        }
        startx++;
        starty++;
        offset--;
        loop--;
    }
    if(n%2==1){//n为奇数特判，给矩阵中间赋值
        re[n/2][n/2]=count;
    }
    return re;
}

总结：在数组中要注意用好双指针法和保证每个区间的左闭右开原则