您现在的位置是：首页 >技术杂谈 >代码随想录算法训练营第二天|977.有序数组的平方 ，209.长度最小的子数组 ，59.螺旋矩阵II网站首页技术杂谈

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

Lyy011220 2023-06-01 20:00:02
简介代码随想录算法训练营第二天|977.有序数组的平方 ，209.长度最小的子数组 ，59.螺旋矩阵II

目录

977.有序数组的平方

1. 将整个数组平方再排序

2. 找到第一个非负数后使用双指针

3.仅使用首尾指针

209.长度最小的子数组(难度:中，不会)

 1.暴力（超时）

 2.滑动窗口

59.螺旋矩阵II(难度：中)

相关题目

其他

qsort()快排

创建二维动态数组

977.有序数组的平方

题目链接：力扣

题目描述：给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例：输入：nums = [-4,-1,0,3,10]
           输出：[0,1,9,16,100]
           解释：平方后，数组变为 [16,1,0,9,100]
           排序后，数组变为 [0,1,9,16,100]

1. 将整个数组平方再排序

这样整还学什么算法

2. 找到第一个非负数后使用双指针

先用二分法找到第一个非负数；在第一个非负数的位置和其前一个位置设置指针，边比较边存。

这个其实和用首尾指针其实没一点区别，一个从内向外比较，一个从外向内，但是比首尾指针繁琐的多。

二分法时间复杂度：O(logn)；比较和存的过程时间复杂度：O(n)。整体时间复杂度：O(n)。

//二分法找到第一个非负数所在下标
int Find_positive(int *nums,int numsSize){
    int left=0;
    int right=numsSize-1;
    while(left<=right){
        int mid=left+(right-left)/2;
        if(nums[mid]==0)    return mid;
        if(nums[mid]>0)     right=mid-1;
        if(nums[mid]<0)     left=mid+1;
    }
    return left;
}
int* sortedSquares(int* nums, int numsSize, int* returnSize){
    int *ret=(int *)malloc(sizeof(int)*numsSize);
    *returnSize=0;
    int num=Find_positive(nums,numsSize);
    int left=num-1;
    int right=num;
    while(left>=0&&right<numsSize){
        int a=nums[left]*nums[left];
        int b=nums[right]*nums[right];
        if(a>b){
            ret[(*returnSize)++]=b;
            right++;
        }else{
            ret[(*returnSize)++]=a;
            left--;
        }
    }
    //对剩余未进行比较元素进行处理
    while(left>=0){
        ret[(*returnSize)++]=nums[left]*nums[left];
        left--;
    }
    while(right<numsSize){
        ret[(*returnSize)++]=nums[right]*nums[right];
            right++;
    }
    return ret;
}

3.仅使用首尾指针

注意到数组本身是有序的，最大值只可能在首尾取到。开辟额外空间，利用首尾指针边比较边存。

时间复杂度：O(n)

int* sortedSquares(int* nums, int numsSize, int* returnSize){
    int *ret=(int *)malloc(sizeof(int)*numsSize);
    *returnSize=numsSize;
    int sign=numsSize;
    int *left=nums;
    int *right=&nums[numsSize-1];
    while(left<=right){
        if((*left)*(*left)>=(*right)*(*right)){
            ret[--sign]=(*left)*(*left);
            left++;
        }else{
            ret[--sign]=(*right)*(*right);
            right--;
        }
    }
    return ret;
}

209.长度最小的子数组(难度:中，不会)

题目链接：力扣

题目描述：给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例：输入：target = 7，nums = [2,3,1,2,4,3]

           输出：2

           解释：子数组[4,3]是该条件下最小的子数组。

 1.暴力（超时）

int minSubArrayLen(int target, int* nums, int numsSize){
    int min=INT_MAX;    //初始结果设为无穷大，便于比较
    for(int i=0;i<numsSize;i++){
        int sum=0;
        for(int j=i;j<numsSize;j++){    //双层循环控制分别从每一位开始加
            if((sum+=nums[j])>=target){
                min=fmin(min,j-i+1);    //j-i+1表示加了多少个数
                break;
            }
        }
    }
    if(min==INT_MAX){    //最终结果还是无穷大，说明不存在子数组和不小于目标值
        return 0;
    }else{
        return min;
    }
}

 2.滑动窗口

这个得再多看看

暴力法使用双层循环，对其进行改进省去一层循环，只能是省去对起始位置的遍历。

        设置终止位置j从0到numsSize-1，找nums[0]+...+nums[j]>=target的情况。之后再去确定i的位置，只要和sum>=target，就减去最前面的一个数，用i来标记，初值设为0，满足条件就加1。

int minSubArrayLen(int target, int* nums, int numsSize){
    int min=INT_MAX;
    int i=0;
    int sum=0;
    for(int j=0;j<numsSize;j++){    //j指终止位置
        sum+=nums[j];
        while(sum>=target){      //找到以0为起始，j为终止的和不小于目标值的元素个数
            min=fmin(min,j-i+1); //也就是j-i+1，再考虑从下标0开始每次去除一个元素
            sum-=nums[i++];      //sum相应减去对应值，如果仍然不小于目标值，起始位置加1
        }
    }
     if(min==INT_MAX){
        return 0;
    }else{
        return min;
    }
}

59.螺旋矩阵II(难度：中)

题目链接：力扣

题目描述：给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

示例：输入：n=3

           输出：[[1,2,3],[8,9,4],[7,6,5]]

如下图所示。

 螺旋矩阵

 对于偏移数的设置与代码随想录中不同，我觉得设为1更容易理解。这个不会就看一遍视频吧！

int** generateMatrix(int n, int* returnSize, int** returnColumnSizes){
    *returnSize=n;
    *returnColumnSizes=(int *)malloc(sizeof(int)*n);
    int ** nums=(int **)malloc(sizeof(int*)*n);
    for(int i=0;i<n;i++){   //初始化结果数组
        nums[i]=(int *)malloc(sizeof(int)*n);
        (*returnColumnSizes)[i]=n;
    }
    int sign=1;     //偏移数为1
    int digit=1;    //初始值为1
    int loop=n/2;   //表明需要转几圈
    int startx=0,starty=0;
    while(loop){     
    int i,j;
        for(j=starty;j<n-sign;j++){
            nums[startx][j]=digit++;
        }
        for(i=startx;i<n-sign;i++){
            nums[i][j]=digit++;
        }
        for(;j>starty;j--){
            nums[i][j]=digit++;
        }
        for(;i>startx;i--){
            nums[i][j]=digit++;
        }
        sign++;    //偏移数每次加1
        startx++;starty++;loop--;
    }
    if(n%2!=0){    //如果n是奇数，最后会空出中心位置
        nums[startx][starty]=digit;
    }
    return nums;
}

相关题目

54.螺旋矩阵

这种东西最好只出现在程序填空里面

int* spiralOrder(int** matrix, int matrixSize, int* matrixColSize, int* returnSize){
    int *ret=(int *)malloc(sizeof(int)*(matrixSize*(*matrixColSize)));
    int index=0;
    int sign=1;     //偏移量
    int loop=fmin(matrixSize,(*matrixColSize))/2;  //遍历圈数
    int num=fmin(matrixSize,*matrixColSize);
    int startx=0,starty=0;  //初始位置
    int i,j;
    while(loop){
        for(j=starty;j<(*matrixColSize)-sign;j++){
            ret[index++]=matrix[startx][j];
        }
        for(i=startx;i<matrixSize-sign;i++){
            ret[index++]=matrix[i][j];
        }
        for(;j>starty;j--){
            ret[index++]=matrix[i][j];
        }
        for(;i>startx;i--){
            ret[index++]=matrix[i][j];
        }
        startx++;starty++;sign++;loop--;
    }
    if(num%2!=0){
        if(matrixSize>(*matrixColSize)){
            for(i=startx;i<=matrixSize-sign;i++){
                ret[index++]=matrix[i][starty];
            }
        }else{
            for(j=starty;j<=(*matrixColSize)-sign;j++){
                ret[index++]=matrix[startx][j];
            }
        }
    }
    *returnSize=index;
    return ret;
}

其他

qsort()快排

void qsort (

    void* base, //要排序的目标数组
    size_t num,     //待排序的元素个数
    size_t width,    //一个元素的大小，单位是字节
    int(*cmp)(const void* e1, const void* e2)

);   

cmp是函数指针，指向比较两元素的函数，需要自己写

 整形：

int cmp_int(const void* e1, const void* e2)
{
	return *(int*)e1 - *(int*)e2;    //升序
}

字符型：

int cmp_char(const void* e1, const void* e2)
{
    return *(char*)e1 - *(char*)e2;
}

字符串型：（字符串比较用strcmp）

int cmp_str(const void* e1, const void* e2)
{
	return strcmp(*(char**)e1, *(char**)e2);
}

创建二维动态数组

int ** nums=(int **)malloc(sizeof(int*)*n);
for(int i=0;i<n;i++){ 
    nums[i]=(int *)malloc(sizeof(int)*n);
}
风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。

站长推荐