代码随想录算法训练营第二天| 977,209,59

977.有序数组的平方

* 数组平方后，最大值一定是在两侧 因为可以采用双指针

package algor.trainingcamp;import java.util.Arrays;/*** @author lizhe* @version 1.0* @description: https://leetcode.cn/problems/squares-of-a-sorted-array/** 有序数组的平方* 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。* @date 2023/4/6 12:30** 数组平方后，最大值一定是在两侧 因为可以采用双指针** 感觉这道难度在于是否能想到双指针 最大值在两侧 => 双指针解法*/
public class LeetCode977 {public int[] sortedSquares(int[] nums) {int idx = nums.length - 1;int[] res = new int[nums.length];int left = 0;int right = nums.length - 1;while(left <= right){if(nums[left] * nums[left] >= nums[right] * nums[right]){res[idx--] = nums[left] * nums[left];left++;}else{res[idx--] = nums[right] * nums[right];right--;}}return res;}public static void main(String[] args) {LeetCode977 demo = new LeetCode977();Arrays.stream(demo.sortedSquares(new int[]{-5, -1, 2, 3, 10})).forEach(System.out::println);}
}

209.长度最小的子数组

* 标准的滑动窗口题，主要是滑动窗口到达临界点如何处理左右边界

package algor.trainingcamp;/*** @author lizhe* @version 1.0* @description: https://leetcode.cn/problems/minimum-size-subarray-sum/** 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。** 来源：力扣（LeetCode）* 链接：https://leetcode.cn/problems/minimum-size-subarray-sum* 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。* @date 2023/4/6 12:42** 标准的滑动窗口，重点是在滑动窗口的临界点如何进行状态变化 和 记录终态** * 在临界点时: leftBound++,sum -= nums[leftBound],* * 全局变量记录len 对比每一次的结果 取最小*/
public class LeetCode209 {public int minSubArrayLen(int target, int[] nums) {int sum = 0;int len = Integer.MAX_VALUE;int leftBound = 0;// rightBound: 滑动窗口右侧for(int rightBound = 0;rightBound < nums.length;rightBound++){sum += nums[rightBound];/*** 达到滑动窗口临界*/while(sum >= target){int curLen = rightBound - leftBound + 1;len = Math.min(curLen, len);sum -= nums[leftBound];leftBound++;}}return len == Integer.MAX_VALUE ? 0 : len;}public static void main(String[] args) {LeetCode209 demo = new LeetCode209();System.out.println(demo.minSubArrayLen(7, new int[]{2, 3, 1, 2, 4, 3}));}
}

59.螺旋矩阵II

按照四个方向（左右）（上下）（右左）（下上）向内进行渐进模拟

package algor.trainingcamp;/*** @author lizhe* @version 1.0* @description: TODO* @date 2023/4/6 12:59** 给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，* 且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。** 注意: 每一次操作之后，下次操作需要更加接近中心点*/
public class LeetCode59 {public int[][] generateMatrix(int n) {int[][] res = new int[n][n];int left = 0, right = n - 1;int up = 0, down = n - 1;int number = 1;while (number <= n * n) {// 左上到右上for (int i = left; i <= right; i++) {res[up][i] = number;++number;}++up;// 右上到右下for (int i = up; i <= down; i++) {res[i][right] = number;++number;}--right;// 右下到左下for (int i = right; i >= left; i--) {res[down][i] = number;++number;}--down;// 左下到左上for (int i = down; i >= up; i--) {res[i][left] = number;++number;}++left;}return res;}
}