算法练习第二天|977.有序数组的平方 ，209.长度最小的子数组 ，59.螺旋矩阵II

算法可视化工具
leetcode-977、leetcode-209、59.螺旋矩阵II

977.有序数组的平方

@Test
    public void sortSquare(){
        //题意：给你一个按 非递减顺序 排序的整数数组 nums，
        // 返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

        //思路：square最大值,要么在最左边要么在最右边
        int[] result = sortSquare(new int[]{-7,-3,2,3,11});
    }

    private int[] sortSquare(int[] nums) {
        int[] result = new int[nums.length];
        //考虑是非递减顺序，所以先从最后一个元素赋值
        int currentIndex = nums.length -1;
        //low=high的时候是最小值，即新数组第一个元素
        for(int low = 0,  high=currentIndex; low <= high;){
            if(nums[low]*nums[low] < nums[high]*nums[high]){
                result[currentIndex] = nums[high]*nums[high];
                currentIndex--;
                high--;

            }else{
                result[currentIndex] = nums[low]*nums[low];
                low ++;
                currentIndex--;
            }
        }
        return result;
    }

209.长度最小的子数组

@Test
    public void minSubArrayLen(){
        //给定一个含有 n 个正整数的数组和一个正整数 target 。
        //
        //找出该数组中满足其总和大于等于 target 的长度最小的
        // 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。
        // 如果不存在符合条件的子数组，返回 0 。
        findMinSubArrayLen(new int[]{2,3,1,2,4,3},7);

    }

    //暴力解法，外循环变更起始位置，内循环变更结束位置
    private int findMinSubArrayLen(int[] nums,int target) {
        int sum;
        int subLength = 0;
        int result = Integer.MAX_VALUE;;
        for(int i = 0;i<nums.length;i++){
            //重置sum
            sum = 0;
            for(int j = i;j<nums.length;j++){
                sum +=nums[j];
                if(sum >= target){
                    subLength = j-i+1;
                    result = result < subLength ? result :subLength;
                    break;
                }
            }
        }
        return result == Integer.MAX_VALUE ? 0: result;
    }
    //滑动窗口，循环控制结束位置
    private int findMinSubArrayLen(int target, int[] nums) {

        int result = Integer.MAX_VALUE;
        int subLength;
        int sum = 0;
        int low = 0;
        for (int high = 0;high< nums.length;high++){
            sum += nums[high];
            while(sum >= target){
                subLength = high - low +1;
                result = result < subLength ? result : subLength;
                此时这个区间满了，慢指针向移动一位
                sum -= nums[low++];

            }

        }
        return result == Integer.MAX_VALUE ? 0: result;
    }

59.螺旋矩阵II

@Test
    public void generateSquare(){
        generateMatrix(3);

    }


    public int[][] generateMatrix(int n) {

        int res[][] = new int[n][n];
        //循环次数
        int loop = 0;
        //index
        int i,j;
        //初始value
        int count = 1;
        //起点
        int start = 0;
        //使用左闭右开
        while(loop++ < n/2){
            //上侧从左到右
            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){
            res[start][start] = count;
        }
        return res;
    }