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

zcctxr / 2023-07-29 / 原文

数组part2

有序数组的平方（力扣977.)

暴力解：先平方再使用快排O(nlogn)
双指针：数组两边的绝对值更大，从两边向中间找到平方值大的数，并从尾向头部插入
1. 先设一个新数组
2. k =numsize -1;
3. for(i=0,j=maxsize-1;i<=j;)
4. if(nums[i]Xnums[i]>nums[j]Xnums[j])

class Solution {
    public int[] sortedSquares(int[] nums) {
        //首尾双指针，想中间行进
        int[] result = new int[nums.length];
        int i = 0;
        int j = nums.length - 1;
        int k = nums.length - 1;
        while(i<=j){
            if(nums[i]*nums[i]<=nums[j]*nums[j]){
                result[k] = nums[j]*nums[j];
                j--;
                k--;
            }else{
                result[k] = nums[i]*nums[i];
                i++;
                k--;
            }
        }
        return result;
    }
}

长度最小的子数组（力扣209.）

思路：如何移动起始位置i？另一个指针j指向终止位置

代码：

for（j=0;j<=maxsize;j++)
sum+=num[j];
直到while(sum>=s)
subL=j-i+1;
result初始为最大值，result=min(result,subL)
i移动->sum=sum-nums[i];i++

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int i = 0;
        int j = 0;
        int sum = 0;
        int result = nums.length + 1;
        int subL = 0;
        //移动后指针
        for(j=0;j<nums.length;j++){
            sum += nums[j];
            while(sum >= target){
                //临时结果值
                subL = j - i +1;
                if(result>subL){
                    result = subL;
                }
                sum = sum - nums[i];
                //移动前指针
                i++;
            }
        }
        return (result==nums.length+1)?0:result;
    }
}

螺旋矩阵（力扣59.）

基本无算法，模拟转圈。
处理转圈的边界条件很多
循环不变量：对每条边的处理规则是左闭右开呢还是左闭右闭呢？
循环是在"条件表达式"和"变量增值之间"执行的

while( n / 2 )//转圈的圈数
startx=0;starty=0;offset=1;count=1;
for(j=starty;j<n-offset;j++)
nums [startx] [j]=count++;
for(i=startx;i<n-offset;i++)
nums [i] [j] = count++;
for(;j>starty;j-- )
nums[i] [j] = count++;
for(;i>startx;i--)
nums[i] [j] =count++;
startx++;starty++;offset++;
if(n%2==1)
name[startx] [starty] =count;

class Solution {
    public int[][] generateMatrix(int n) {
        int temp = n;//暂存n值
        int start = 0;
        int i = 0;
        int j = 0;
        int offset = 0;//表示循环次数
        int count = 1;
        int[][] nums = new int[n][n];
        while( offset++ < n / 2){//判断循环次数
            //第一行循环
            for(j = start;j < n - offset;j++){//下标为0~(n-1)且遵循左闭右开
                nums[start][j] = count++;
            }
            for(i = start;i < n - offset; i++){
                nums[i][j] = count++;
            }
            for(;j > start;j--){//此时边界条件为start
                nums[i][j] = count++;
            }
            for(;i > start;i--){
                nums[i][j] = count++;
            }
            start++;
        }
        //如果n是奇数，则在[start][start]位置设定为最后一位结果
        if(temp % 2 == 1){
            nums[start][start] = count;
        }
        return nums;
    }
}