今天是代码随想录训练营的第2天记录，但现在其实已经是代码随想录的第3天了😭昨天有点事情拖慢了进度，今天要补上昨天的内容外加今天的内容💪💪
今天是数组阶段的最后 3 道题目。977：有序数组的平方；209：长度最小的子数组；59：螺旋矩阵II
977：有序数组的平方
题目描述：
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例：
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
解法 一：暴力破解
之前刷过一遍了，读了题目之后的第一想法还是暴力破解。这个方法可以说是没有任何算法技巧，完全就是看一下自己的代码能力。由于第一次做的时候并没有写这个解法，我这次刷题的时候就特意写一下。
class Solution {
public int[] sortedSquares(int[] nums) {
for(int i = 0; i < nums.length; i++){
nums[i] = nums[i] * nums[i];
}
Arrays.sort(nums);
return nums;
}
}
顺便记录一下Java中Array.sort()的写法：
- Array.sort(int[] a), 按数组元素大小从小到大排序
- Array.sort(int[] a, int fromIndex, int toIndex), 从fromIndex到toIndex的位置从小到大排序
- 以上2种方法只能从小到大排序，入药从大到小排序，则需要用到Java的泛型Comparator。
解法二：双指针
基本思路：
- 用2个指针i和j，分别指在数组的两端。设置一个result数组用来储存结果。因为平方过后的最大数只能在两端，不可能在数组中间。
- 每一次对比i和j指向元素的平方大小，大的那个放入result中，并且移动指向大的数值的那个指针。直到遍历原数组所有的元素。
class Solution {
public int[] sortedSquares(int[] nums) {
//初始化设置
int right = nums.length - 1;
int left = 0;
int[] result = new int[nums.length];
int index = result.length - 1;
//循环开始，设置条件
while(left <= right){
if (nums[left] * nums[left] > nums[right] * nums[right]){
result[index--] = nums[left] * nums[left];
++left;
}else{
result[index--] = nums[right] * nums[right];
--right;
}
}
return result;
}
}
209：长度最小的子数组
题目描述：
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0。
示例：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
基本思路：
利用滑动窗口原理，定义两个指针，第一个指针用来读取数据并进行相加，形成子序列，当子序列的数之和
大于等于target时，则记录当前子序列的长度，并开始移动第二个指针进行子序列缩短，当子序列之和小于target时，再次移动第一个指针，直到结束；
class Solution {
public int minSubArrayLen(int target, int[] nums) {
//定义一个最大的数来判断result是否被更新了
int result = Integer.MAX_VALUE;
int i = 0;
int sum = 0;
/*
循环逻辑：
1.j遍历数组元素进行相加
2.当数组元素>=target时，框定子序列
3.i开始往后读数，并从sum中依次减去元素
*/
for (int j =0; j < nums.length;j++){
sum +=nums[j];
while(sum >= target){
int subLength = j-i+1;
result = Math.min(result,subLength);
sum -= nums[i++];
}
}
return result == Integer.MAX_VALUE? 0 : result;
}
}
59：螺旋矩阵II
题目描述：
给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
解题思路：
定义：空矩阵；起始位置；循环次数；偏移量；中间值；每个空格的赋值
1.固定起始位置X，Y
2.摸清旋转顺序(左闭右开)，制定offset，遵循循环不变量的原则
tipp：四个循环怎么写
·上行：从左往右
·右列：从上往下
·下行：从右往左
·左列：从下往上
3.更新起始位置，偏移量，循环次数
4.单独处理中间值
class Solution {
public int[][] generateMatrix(int n) {
int[][] res = new int[n][n];
//循环次数
int loop = n/2;
//定义起始位置
int startX = 0;
int startY = 0;
//给每个空格赋值
int count = 1;
//定义偏移量,每一圈循环需要控制每一条边的遍历的长度
int offset = 1;
//处理中间格
int mid = n/2;
while(loop >0){
int i = startX;
int j = startY;
//上边：x动y不动
for(j = startY; j < startY + n - offset; j++){
res[startX][j] = count++;
}
//右列：x不动y动
//矩阵使用更新后的j
for(i = startX; i < startX + n - offset; i++){
res[i][j] = count++;
}
//下行：x动y不动
for(; j > startY; j--){
res[i][j] = count++;
}
//左列：x不动y动
for(; i > startX;i--){
res[i][j] = count++;
}
startX++;
startY++;
//偏移量加2，因为左右都走了一格
offset +=2;
loop--;
}
if (n%2 !=0){
res[mid][mid] = count;
}
return res;
}
}
