算法学习day01数组part02-209、59、977

package LeetCode.arraypart02;
/**
 * 209. 长度最小的子数组
 * 给定一个含有n个正整数的数组和一个正整数 target 。
 * 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 .
 * 示例：
 * 输入：target = 7, nums = [2,3,1,2,4,3]
 * 输出：2
 * 解释：子数组 [4,3] 是该条件下的长度最小的子数组。
 * */
/**
 * 思路：
 * 这是一个双指针的题目
 * 思想是有一个 >=7 的窗口，所以可以叫做滑动窗口
 * 首先定义窗口起始位置和结束位置，循环结束位置，找到大于等于目标值的数组，取数组长度，这个数组长度是动态更新的
 * 然后将起始位置向后移动，寻找下一个满足条件的数组
 * 最终范围 那个最小长度的值
 * */
public class MinimumSizeSubarraySum_209 {
    public static void main(String[] args) {
        int target = 7;
        int [] arr = {2,3,1,2,4,3};
        int result = minSubArrayLen(target,arr);
        System.out.println(result);

    }

    public static int minSubArrayLen(int s, int[] nums) {
        // 滑动窗口
        int left = 0;
        int sum = 0;
        int result = Integer.MAX_VALUE;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (sum >= s) {
                result = Math.min(result, right - left + 1);
                sum -= nums[left];
                left++;
            }
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }

}

package LeetCode.arraypart02;
/**
 * 59. 螺旋矩阵 II
 * 给你一个正整数 n ，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
 * 示例:
 * 输入：n = 3
 * 输出：[[1,2,3],[8,9,4],[7,6,5]]
 */

public class SpiralMatrixII_59 {
    public static void main(String[] args) {
        int n = 4;
        int[][] result = new int[n][n];
        result = generateMatrix(3);
        for (int i = 0; i < result.length; i++) {
            for (int j = 0; j < result.length; j++) {
                System.out.print(result[i][j] + " ");
            }
            System.out.println();
        }

    }
    public static int[][] generateMatrix(int n) {
        int[][] res = new int[n][n];// 定义一个二维数组
        int startx = 0, starty = 0; // 定义每循环一个圈的起始位置
        int loop = n / 2; // 循环几圈，例如n为奇数3，那么loop = 1 只是循环一圈，矩阵中间的值需要单独处理
        int mid = n / 2; // 矩阵中间的位置，例如：n为3， 中间的位置就是(1，1)，n为5，中间位置为(2, 2)
        int count = 1; // 用来给矩阵中每一个空格赋值
        int offset = 1; // 需要控制每一条边遍历的长度，每次循环右边界收缩一位
        int i, j;
        while (loop-- > 0) {
            i = startx;
            j = starty;

            // 下面开始的四个for就是模拟转了一圈
            // 模拟填充上行从左到右(左闭右开)
            for (j = starty; j < n - offset; j++) {
                res[startx][j] = count++;
            }
            // 模拟填充右列从上到下(左闭右开)
            for (i = startx; i < n - offset; i++) {
                res[i][j] = count++;
            }
            // 模拟填充下行从右到左(左闭右开)
            for (; j > starty; j--) {
                res[i][j] = count++;
            }
            // 模拟填充左列从下到上(左闭右开)
            for (; i > startx; i--) {
                res[i][j] = count++;
            }

            // 第二圈开始的时候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
            startx++;
            starty++;

            // offset 控制每一圈里每一条边遍历的长度
            offset += 1;
        }

        // 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
        if (n % 2 == 1) {
            res[mid][mid] = count;
        }
        return res;
    }

}

package LeetCode.arraypart02;

/**
 * 977. 有序数组的平方
 * 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
 * 示例：
 * 输入：nums = [-4,-1,0,3,10]
 * 输出：[0,1,9,16,100]
 * 解释：平方后，数组变为 [16,1,0,9,100]
 * 排序后，数组变为 [0,1,9,16,100]
 * */
/**
 * 思路：
 * 这是一道典型的以空间换时间的题目
 * 如果使用暴力方法，先每个数平方再进行排序，那么复杂度就是O(nlogn)
 * 但是这道题要求是n的复杂度，
 * 所以可以使用双指针的方法
 * 1.首先有一个数组，当然必须是有负数的数组，要不然该题目没有意思
 * 2.题目要求我们从小到大将元素放到新数组中，因为大的元素一定是两头的，所以我们先找大的元素，然后从后往前给新数组赋值
 * 3.最后返回 新数组
 * */
public class SquaresOfASortedArray_977 {
    public static void main(String[] args) {
        int [] nums = {-4,-1,0,3,10};
        int [] result = sortedSquares(nums);
        for (int i = 0; i < result.length; i++) {
            System.out.print(result[i]+" ");
        }

    }
    public static int[] sortedSquares(int[] nums){
        int [] result = new int [nums.length];
        int left = 0;
        int right = nums.length-1;
        int index = nums.length -1;
        while(left<=right){
            if (nums[left]*nums[left] >nums[right]*nums[right]){
                result[index] = nums[left]*nums[left];
                index --;
                left++;
            }else{
                result[index]=nums[right]*nums[right];
                index--;
                right--;
            }
        }
        return result;
    }
}