977.有序数组的平方
题目链接：https://leetcode.cn/problems/squares-of-a-sorted-array/
文章讲解：https://programmercarl.com/0977.%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E7%9A%84%E5%B9%B3%E6%96%B9.html
视频讲解： https://www.bilibili.com/video/BV1QB4y1D7ep
package com.secondday.array;
/**
* 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按非递减顺序排序。
*
* 示例 1：
*
* 输入：nums = [-4,-1,0,3,10]
* 输出：[0,1,9,16,100]
* 解释：平方后，数组变为 [16,1,0,9,100]，排序后，数组变为 [0,1,9,16,100]
*/
public class SortSqArray {
public static void main(String[] args) {
int[] nums = {-4,-1,0,3,10};
nums = sortSquare(nums);
for (int n : nums){
System.out.print(n+" ");
}
}
//相向指针写法
public static int[] sortSquare(int[] nums){
int left = 0;
int right = nums.length-1;
int[] result = new int[nums.length];
int k = nums.length-1;
while (left<=right){
if (nums[left] * nums[left] < nums[right]*nums[right]){
result[k--] = nums[right]*nums[right];
--right;
}else {
result[k--] = nums[left]*nums[left];
++left;
}
}
return result;
}
}
小结
使用双向指针，循环条件注意left = right 边界问题，if考虑了<的情况，else考虑了>=的情况，开辟新空间新数组result来实现排序的目的
209.长度最小的子数组
题目链接：https://leetcode.cn/problems/minimum-size-subarray-sum/
文章讲解：https://programmercarl.com/0209.%E9%95%BF%E5%BA%A6%E6%9C%80%E5%B0%8F%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84.html
视频讲解：https://www.bilibili.com/video/BV1tZ4y1q7XE
package com.secondday.array;
/**
* 给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
*
* 示例：
*
* 输入：s = 7, nums = [2,3,1,2,4,3]
* 输出：2
* 解释：子数组 [4,3] 是该条件下的长度最小的子数组。
* 提示：
*
* 1 <= target <= 10^9
* 1 <= nums.length <= 10^5
* 1 <= nums[i] <= 10^5
*/
public class MinLengthArray {
public static void main(String[] args) {
int[] nums = {2,3,1,2,4,3};
System.out.println(minSubArrayLen(nums,7));
}
public static int minSubArrayLen(int[] nums,int s){
int i = 0; //起始指针
int result = Integer.MAX_VALUE;
int sum = 0; //滑动窗口的值
for (int j = 0; j<=nums.length-1;j++){ //j是终止指针
sum += nums[j];
//滑动窗口的起始位置考虑
while (sum>=s){ //当出现>=7的情况
//计算出最小长度
int minSubLen = j-i+1;
result = Math.min(result,minSubLen);
//终止循环的条件
sum -= nums[i]; //向后移动一位，减去滑动窗口的头一位
//起始位置+1
i++;
}
}
return result == Integer.MAX_VALUE ? 0 : result; //出现0的情况就是异常，无法满足>=7的情况
}
}
小结
在O(1)的空间上使用双向指针，并且时间为O（n）的情况，调节指针的位置以便能达到滑动的效果
- result值的设定
- 起始指针跟终止指针的指向
- 计算符合最小长度的情况
- 异常判断
59.螺旋矩阵II
题目链接：https://leetcode.cn/problems/spiral-matrix-ii/
文章讲解：https://programmercarl.com/0059.%E8%9E%BA%E6%97%8B%E7%9F%A9%E9%98%B5II.html
视频讲解：https://www.bilibili.com/video/BV1SL4y1N7mV/
package com.secondday.array;
/**
* 给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。
* 示例:
* 输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ]
*/
public class GenerateMatrix {
public static void main(String[] args) {
int[][] res = generateMatrix(3);
for (int i = 0; i < res.length; i++) {
for (int j = 0; j <res.length ; j++) {
System.out.print(res[i][j]+" ");
}
System.out.println();
}
}
public static int[][] generateMatrix(int n){
int loop =0; //控制循环次数
int startx = 0; //每次循环开始点
int starty = 0; 每次循环开始点
int[][] res = new int[n][n];
int i,j; //行、列
int count = 1; //定义填充数字
int offset = 1; //控制右开的缩进
while (loop++ < n/2){ //控制循环次数
//遵循左闭右开的原则 -->循环不变量
//模拟上侧从左到右
for (j = starty;j<n-offset;j++){ //假设n=4，数组下标填充到2，空出3的位置留给下一次填充，并且此时索引j=3，因为最后还会再进行一次判断
res[startx][j] =count++;
}
//模拟右侧从上到下
for (i=startx;i<n-offset;i++){
res[i][j] =count++; //此时的j是不变，j=3
}
//模拟下侧从右到左
for (;j>starty;j--){
res[i][j] = count++; //此时i是不变的，j从下标为3的情况进行填充，空出starty的位置留给下一次填充，并且此时的j=0
}
//模拟左侧从下到上
for (;i>startx;i--){
res[i][j] = count++; //此时的j是不变的，j=0
}
//由上四个for循环已经走完一圈 ,初始位置需要变化，还有offset末端距离也需要变化,offset是用来控制右开的距离缩进
startx++;
starty++;
offset++;
}
//如果n是偶数正常填充完毕，如果n是奇数的话中间会空出一个位置，中间的位置另外填充
if (n % 2 == 1){
res[startx][starty] = count++;
}
return res;
}
}
小结
模拟题，没有计算，看到题目知道结果，使用代码的方式进行表达出来。技巧：
- 先找出圈数，外层循环，使用一个loop变量进行控制
- 描写矩阵要遵从左闭右开的原则，使用offset变量控制右开，避免右开被赋值填充
- 画好外层考虑下一层的位置
- 最后考虑奇偶的问题，因为偶数中间不会空，奇数会空
