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

一、 LeetCode977.有序数组的平方

1. 题目链接LeetCode977.有序数组的平方

2. 学习资料：

• 977文章
• 977视频
• 快速排序的写法

3. 思路

解法一：双指针

1. 创建一个与数组大小相同的数组result
2. 创建两个指针 i 和 j， i指针指向数组第一个元素，j指向数组最后一个元素
3. 创建指针 k，k= nums.length-1; k是result的最后一个索引位置
4. 在 i<=j 的时候循环 比较nums[i]*nums[i] 和 nums[j]*nums[j] 的大小
5. 将小的那个数放在result[k]这个位置，并且对应位置的指针进行移动。k--。
    若是 i 位置则 i指针向后移动，i++;
    若是 j 位置， 则 j 指针向前 j--;
6. 返回result数组

解法二：暴力法

一开始两个方法都没有想到，看了学习资料才意识到可以用暴力法
使用暴力法是刷题数量很少的时候能想出并写出的办法。
7. 循环数组，并将数组每个位置的元素赋值为该位置元素的平方
8. 在循环完一轮数组后用快速排序排序循环后的数组
9. 返回排序后的数组

暴力解法中，我自己实现了单边循环的快速排序方法。算是给自己复习一下快排的写法。

4. 代码

• 解法一：双指针法
  时间复杂度 O(n)
  空间复杂度 O(n)

class Solution {
    public int[] sortedSquares(int[] nums) {
        int k = nums.length-1;
        int[] result = new int[nums.length];
        for(int i=0, j= nums.length-1;i<=j;){
            if(nums[i]*nums[i]>=nums[j]*nums[j]){
                result[k] = nums[i]*nums[i];
                k--;
                i++;
            }else{
                result[k] = nums[j]*nums[j];
                k--;
                j--;
            }
        }
        return result;

    }
}

• 解法二：暴力解法
  时间复杂度 O(n + nlogn)

class Solution {
    public int[] sortedSquares(int[] nums) {
        for(int i = 0; i<nums.length;i++){
            nums[i] = nums[i]*nums[i];
        }
        quickSort(nums,0,nums.length-1);
        return nums;

    }
    //快速排序
    public void quickSort(int[] nums,int l, int h){
        if(l >= h){
            return;
        }
        int p = partition(nums,l,h);
        quickSort(nums,l,p-1);
        quickSort(nums,p+1,h);
    }
    public int partition(int[]nums, int l, int h){
        int pv = nums[h];
        int i = l;
        for(int j=l;j<h;j++){
            if(nums[j]<pv){
                swap(nums,i,j);
                i++;
            }
        }
        swap(nums,i,h);
        return i;

    }
    public void swap(int[] a, int i, int j){
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

二、LeetCode209.长度最小的子数组

1. 题目链接: 长度最小的子数组

2. 学习资料：

• 209文章
• 209视频

3. 思路

1. 使用滑动窗口的思想来解题
	i 代表窗口的起始位置
	j 代表窗口的终止位置
	sum 是窗口内元素和
	subLength是窗口的长度
2. 遍历数组，将数组里的元素与窗口内的元素和想加
3. 如果窗口内的元素和大于目标数时，我们缩小窗口的起始位置，
4. 并判断缩小起始位置后的窗口内元素的和是否还满足大于target这个条件
5. 如果满足就接着缩小窗口。

4. 代码

滑动窗口

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int result = Integer.MAX_VALUE;
        int i =0;
        int subLength = 0;
        int sum = 0;
        for(int j = 0; j<nums.length; j++){
            sum += nums[j];
            while(sum >= target){
                subLength = j-i+1;
                result = result < subLength? result : subLength;
                sum = sum - nums[i];
                i++;
            } 
        }
        return result == Integer.MAX_VALUE ? 0 : result;

    }
}

三、LeetCode59.螺旋矩阵II

1. 题目链接59.螺旋矩阵II

2. 学习资料：

• 59文章
• 59视频

3. 思路

按照从左往右，从上向下，从右往左，从下到上的顺序依次填充。

4. 代码

class Solution {
    public int[][] generateMatrix(int n) {
        int left = 0;
        int right = n-1;
        int top =0;
        int bottom = n-1;
        int num =1;
        int target = n*n;
        int[][] matrix = new int[n][n];
        while(num<=target){
            //从左往右
            for(int i = left; i<=right;i++){
                matrix[top][i] = num;
                num++;
            }
            //从上到下
            top++;
            for(int i =top;i<=bottom;i++){
                matrix[i][right] = num;
                num++;
            }
            right--;
            //从右往左
            for(int i= right;i>=left;i--){
                matrix[bottom][i] = num;
                num++;
            }
            bottom--;
            //从下到上
            for(int i = bottom;i>=top;i--){
                matrix[i][left] = num;
                num++;
            }
            left++;

        }
        return matrix;
    }
}