随想录一期 day2 [977.有序数组的平方|209. 长度最小的子数组|59.螺旋矩阵II(剥洋葱)]

977.有序数组的平方

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

思路

• 递增数组，平方后最大值一定在最左侧或者最右侧，可想到–双指针
• 左右指针向中间靠拢，每次可以得到一个最大值，以此类推，放入结果集中
• 临界条件需要左右指针相等，不会漏掉最后一个数

复杂度

• 时间 O(n)
• 空间 O(n)

class Solution {
    public int[] sortedSquares(int[] nums) {
        int[] rt = new int[nums.length];
        int l = 0 ,r = nums.length-1,pos = r ;
        while(l<=r){
            int lv = nums[l] * nums[l] ;
            int rv = nums[r] * nums[r];
            if(lv < rv){
                rt[pos--] = rv ;
                --r;
            }else{
                rt[pos--] = lv ;
                ++l;
            }
        }
        return rt; 
    }
}

209. 长度最小的子数组

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

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

思考

• 最小数据需要逐个判断子数据的长度，可想到滑动窗口
• 动态子数组的最小长度，可想到快慢指针，快指针得到满足条件的子数组时，移动慢指针
• 慢指针的移动需要借助循环来实现，即需要两层循环

复杂度

• 时间 O(2n)==>O(n)
• 空间 O(1)

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int l = 0 ,r = 0 ,sum = 0, min = Integer.MAX_VALUE;
        while(r < nums.length){
            sum += nums[r];
            while(sum >= target){
                min = Math.min(min,r-l+1);
                sum -= nums[l++];
            }
            ++r;
        }
        return min==Integer.MAX_VALUE ? 0 : min;
    }
}

59.螺旋矩阵II

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

思考

• 按顺时针旋转，旋转一周可得到四条边，分别为上、右、下、左
• 每条边的临界值为0或者n-1，循环为左右闭区间，顾走完一条边就要把这条边消掉，（起名为剥洋葱）
• 走完一周，相当消掉一周的边，是不是很像剥洋葱，一层一层的剥开…

class Solution {
    public int[][] generateMatrix(int n) {
        //四条边left rigth top bottom 根据旋转方向得到每条边的临界值，类似洋葱剥皮
        // 右->做
        int left  = 0 ;
        // 左->右
        int right = n - 1 ; 
        // 上->下
        int bottom = n - 1 ; 
        // 下->上
        int top = 0 ;
        int num = 1 ,total = n * n;
        int [][] res = new int[n][n];
        while(num <= total){
            //左->右  高度（top）不变
            for(int i = left ; i<=right ; i ++){
                res[top][i] = num++;
            }
            top++;  //上层边消掉
            //上->下  右侧（right）不变
            for(int i = top ; i<=bottom ; i++){
                res[i][right] = num++;
            }
            right--; //右侧边消掉
            //右->左 底部（bottom）不变
            for(int i = right ; i>=left ; i--){
                res[bottom][i] = num++;
            }
            bottom--; //下层边消掉
            //下->上 左侧（left）不变
            for(int i = bottom ; i>=top ;i--){
                res[i][left] = num++;
            }
            left++; //左侧边消掉
        }
        return res ;
    }
}