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

目录

977.有序数组的平方

思路

快排代码

双指针代码 

遇到的问题 

59.螺旋矩阵Ⅱ

思路

代码 

209.长度最小的子数组

思路

代码

977.有序数组的平方

题目链接

代码随想录讲解

思路

（1）题目关键字：

                        1.输入数组非递减：一开始写完快排代码没有用上这个条件，说明可能还有解法，原数组有序，平方后最大值在两端，所以用前后指针比较填充返回数组即可。

                        2.每个元素需要平方

                        3.返回数组也非递减：结合2、3可以想到先平方再排序

                        4.1<=nums.length<=10000：可以选择O(logn)、O(n)、O(nlogn)（快排的时间复杂度），而题目也和排序有关，所以可以考虑一下快排。

快排代码

int cmp(int *a,int *b)
{
    int a1 = *a;
    int b1 = *b;
    
    return a1-b1;
}
int* sortedSquares(int* nums, int numsSize, int* returnSize) {
    int *ret = (int *)malloc(sizeof(int)*numsSize);
    int n = numsSize;
    
    for(int i=0;i<n;i++)
        ret[i] = nums[i]*nums[i];
    qsort(ret,n,sizeof(int),cmp);

    *returnSize = n;
    return ret;
}

双指针代码 

int* sortedSquares(int* nums, int numsSize, int* returnSize) {
    int n = numsSize;
    int *ret = (int *)malloc(sizeof(int)*n);
    *returnSize = n;
    int left,right;

    left = 0;
    right = n-1;
    int m = n-1;//
    while(leftnums[right]*nums[right])
        {
            ret[m--] = nums[left]*nums[left];
            left++;
        }
        else
        {
            ret[m--] = nums[right]*nums[right];
            right--;
        }

    }

    return ret;
}

遇到的问题 

（1）qsort()不会用了

59.螺旋矩阵Ⅱ

思路

        本题是一道模拟题，目标是一个螺旋矩阵，所以先根据题目想象或动手模拟一遍矩阵的形成过程。首先先在一行开始向右填写n个数字；然后向下填写n-1数字；继续向左填写n-1个数字；最后向上填写n-2个数字。

        接下来进入到第二圈，先向右填充n-2个数字，再向下填充n-3个数字，然后向左填充n-3个数字，最后向上填充n-4个数字。

        通过对矩阵的模拟发现，每一圈的操作都是类似的都是按照右、下、左、上的顺序填充数字，区别就是填充几个数字。所以可以考虑循环或者递归来实现填数操作。

        通过以上分析，我只需要写一次右、下、左、上的操作，然后交给循环或递归即可。现在需要考虑循环的边界条件，首先不同循环中开始填数的位置不同，对应的每行每列要填的数的个数也不同。然后在单个循环中通过上面分析，向右填充的次数若给向上填充的一次，则四次填数的次数就全部相等，所以重新考虑一下填数操作，向右不包括右边界点，向下不包括下边界点，向左不包括左边界点，向上自然而然也无法包括上边界点，即统一了次数。

        总结一下分析：我需要确定每次循环左上角坐标，然后需要确定填充数字个数，每行每列填充数字时不包括第二个边界点以便个数统一。

        尝试写代码：

int x,y; //左上角坐标
x = y = 0; //初始坐标

int sum = n-1; //第一圈每行每列需要填充的数字个数

int i = x,j = y;
for(;j<sum;j++) //向右
{
    nums[i][j] = count++;
}

for(;i)

        写到这里发现了问题，想法和实现的对接上出现了问题。通过nums[i][j]来更新数组说明i和j是索引，而for循环中i<sum等又说明i和j是一个计数器，所以出现了错误。 

        一开始的思路是通过for中的i++，j++等来改变横纵坐标从而寻找正确的填数位置，所以需要修改判定条件i<sum等，可以新定义计数器，又因为i == x，j == y所以就不定义i和j为索引了。新代码如下：

int x,y;
int sum = n-1;
int i; //计数器

x = y = 0;
for(i=0;i<sum;i++)
{
    nums[x][y] = count++;
    y++;
}

for(i=0;i<sum;i++)
{
    nums[x][y] = count++;
    x++;
}

for(i=0;i<sum;i++)
{
    nums[x][y] = count++;
    y--;
}

for(i=0;i<sum;i++)
{
    nums[x][y] = count++;
    x--;
}

n*n即有n/2圈（n为奇数时，还要添加最中间的数），每次while大循环开始修改x和y的值即可。然后写完整代码：

代码 

int** generateMatrix(int n, int* returnSize, int** returnColumnSizes) {
    int **nums = malloc(sizeof(int *)*n);
    *returnSize = n;
    *returnColumnSizes = malloc(sizeof(int)*n);
    for(int i=0;i<n;i++)
    {
        nums[i] = malloc(sizeof(int)*n);
        (*returnColumnSizes)[i] = n;
    }

    int count = 1;
    int x,y;
    int sum;
    int i;
    int m = n/2;
    int num = 0; //为了每次修改x、y的值
    int k = 1;//为了每次修改sum的值

    while(m--)
    {
        x = y = num++;
        sum = n-k;
        for(i=0;i<sum;i++)
        {
            nums[x][y] = count++;
            y++;
        }

        for(i=0;i<sum;i++)
        {
            nums[x][y] = count++;
            x++;
        }

        for(i=0;i<sum;i++)
        {
            nums[x][y] = count++;
            y--;
        }

        for(i=0;i<sum;i++)
        {
            nums[x][y] = count++;
            x--;
        }
        k = k+2;
    }
    if(n%2==1)
        nums[num][num] = count;

    return nums;
}

209.长度最小的子数组

题目链接

代码随想录讲解

思路

题目关键字：找子数组且连续：需要关注子数组的左右端点

                      长度最小

                      1<=nums.length<=100000：考虑O(n)、O(logn)、O(nlogn)的算法。

暴力思想：根据左右端点先到暴力解法，第一层for循环移动左端点，第二层for循环移动右端点。

滑动窗口思想：听卡哥讲完能写代码了，但用语言描述其思想还做不到，自己的理解就是改暴力思想（每次移动起始位置，不断寻找终止位置）为每次移动终止位置，而起始位置需要不断寻找。能理解到每次确定符合条件的子数组一定是在该起始位置最优的子数组，但说不出来所以然。

代码

int minSubArrayLen(int target, int* nums, int numsSize) {
    int n = numsSize;
    int left,right;
    int sum = 0;
    int result = n;
    int tag = 1;

    left = right = 0;
    for(;right=target)
        {
            tag = 0;
            result = result>(right-left+1)?(right-left+1):result;
            sum = sum-nums[left];
            left++;
        }
    }

    if(tag) return 0;
    return result;
}