[数据结构与算法]【Leetcode刷题笔记02】977.有序数组的平方 209.长度最小的子数组 59.螺旋矩阵II

977.有序数组的平方

题目描述

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

做题思路

由于原数组存在负数，所以平方后最大值可能出现在两端。因此可以采用双指针法，在数组首尾各放置一个指针，比较指针元素平方后的值。较大者放入结果数组末端，同时该指针向中间移动，继续比较。

参考代码

class Solution {
    public int[] sortedSquares(int[] nums) {
        int left=0;//左指针
        int right=nums.length-1;//右指针
        int[] result=new int[nums.length];//结果数组
        int index=result.length-1;//结果数组的指针要放在末端
        while(left<=right){//注意等号
            if(nums[left]*nums[left]>nums[right]*nums[right]){//左指针元素平方比右指针大
                result[index--]=nums[left]*nums[left];//左指针元素平方放入结果数组
                ++left;//左指针移动
            }
            else{
                result[index--]=nums[right]*nums[right];//右指针元素平方放入结果数组
                --right;//右指针移动
            }
        }
        return result;
    }
}

209.长度最小的子数组

题目描述

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度**。**如果不存在符合条件的子数组，返回 0 。

做题思路

由于本题的目标是连续子数组，所以可以想到使用滑动窗口法，也就是双指针法。

将右指针设定为子数组的右端，左指针为左端。首先左指针不动，右指针右移，滑动窗口不断增长，和不断增加，当和≥ target时，此时的长度满足条件，但题目要求长度最小，因此需要与之前成立的长度进行比较，更新最小长度。同时左指针右移，更新滑动窗口。

参考代码

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left=0;//左指针
        int result=Integer.MAX_VALUE;
        int sum=0; 
        for(int right=0;right<nums.length;right++){//左指针不动，右指针右移，构建窗口
            sum+=nums[right];
            while(sum>=target){//此时窗口内的和已经满足条件
                result=Math.min(result,right-left+1);//更新最小长度
                sum-=nums[left++];//左指针右移，开始新一轮窗口
            }
        }
        return result==Integer.MAX_VALUE?0:result;
    }
}

59.螺旋矩阵II

题目描述

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

做题思路

本题的关键点是区间左右的开闭和n奇偶的分别处理，将一圈分为上下左右4个左开右闭的区间。

参考代码

//采取左闭右开区间
class Solution {
    public int[][] generateMatrix(int n) {
        int loop=0;//循环数
        int[][] res=new int [n][n];
        int start=0;//每次循环从(start,start)开始
        int count=1;//填入的数
        int i,j;
        while(loop++<n/2){//注意没有等号，因为第1圈是第0次循环
            for(j=start;j<n-loop;j++){
                res[start][j]=count++;//上面从左到右
            }
            for(i=start;i<n-loop;i++){
                res[i][j]=count++;//右边从上到下
            }
            for(;j>=loop;j--){
                res[i][j]=count++;//下面从右到左
            }
            for(;i>=loop;i--){
                res[i][j]=count++;//左边从下到上
            }
            start++;
        }
        if(n%2==1){//如果n是奇数，中心要单独赋值
            res[n/2][n/2]=count;
        }
        return res;
    }
}