代码随想录算法刷题 day02
1.有序数组的平方（leecode977）
链接：https://leetcode.cn/problems/squares-of-a-sorted-array/
问题描述：
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
处理想法
- 暴力法
- 先nums[]每个元素求平方
- 对平方后数组进行排序（相当于快速排序，时间复杂度比较高）
- 相向双指针法
- 数组是非递减排序，确定数组平方后的最大值一定是最左边或者最右边产生的。
- 目前确定的数组最大值来源可以确定，那么新建的数组排序可以从大到小来排序。
注意点
- 和二分查找、移除元素不一样，该算法需要重新创建一个数组来保存结果
- 在循环结构查找最大值，并从右边插入这个过程之中
- 新建数组每确定一个比当前最大元素更小的一个元素就需要向左移动一个index
- 使用最左边的元素迭代最左边的元素才需要右移，否则不需要，所以left++不能直接放在for循环里面，右侧同理
代码实现
class Solution {
public int[] sortedSquares(int[] nums) {
//解题前提：有序数组的平方最大值一定在最左边或者最右边
//相向双指针法
//左右边界
int left = 0;
int right = nums.length - 1;
//需要新建一个数组对平方结果进行存储
int[] result = new int[nums.length];
//相向双指针找平方结果，由大到小，所以是数组先从最后一个最大的元素开始排序
//确定最大的索引位置
int index = nums.length - 1;
//循环建立结果数组
while(left <= right){
if (nums[left] * nums[left] > nums[right] * nums[right]){
result[index] = nums[left] * nums[left];
//index不断向前移动
index--;
left++;
}else{
result[index] = nums[right] * nums[right];
//index不断向前移动
index--;
right--;
}
}
//不要忘了最终需要返回的目标result[]
return result;
}
}
示意图
2. 长度最小的子数组（leecode209）
链接：https://leetcode.cn/problems/minimum-size-subarray-sum/
问题描述
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
处理想法
- 暴力
- 两个for循环列出全部符合要求的解
- 滑动窗口-------->两个指针构成滑动窗口，确定最小sub_nums
- 首先找到元素和大于target的满足要求的数组和为sum
- 对于找到满足要求的数组再去删减元素，做到内部元素最少且满足要求
- 外层for确定找到 >= target的数组，指针确定的右边界
- 当找到满足要求的数组长度后，缩减元素，left向右移动后就不会再重新开始
代码实现
class Solution {
public int minSubArrayLen(int target, int[] nums) {
//有边界是不停往右试探的，是不确定的
//错误写法：int right = nums.length - 1;
int left = 0;
//sum用来确定有边界的时候，不断缩小sum,直到再减就小于target
int sum = 0;
//初始化数组中最短的长度，所以选取了Java中int类型的最大值
//如果设置为0，这样初始化是不对的，要设置一个大值
int smallest = Integer.MAX_VALUE;
for (int right = 0;right < nums.length;right++){
//往右移动right，直到找到sum大于target
sum += nums[right];
//只要sum>=target，就可以开始把左边指针开始往右移动，缩减元素个数（包括等于）
while(sum >= target){
//用目前的最短的长度更新掉smallest最短长度
int currentLength = right - left + 1;
smallest = Math.min(smallest, currentLength);
sum = sum - nums[left];
left++;
}
}
//如果smallest = max.value表明没找到
//找到返回的是smallest
return smallest == Integer.MAX_VALUE ? 0 : smallest;
}
}
示意图
注意提示
nums数组是一个全部都是正整数的数组------------------>数组right边界每次右移，内部元素和都是增加的，左边数组，每次右移都是缩小的，因此第一次找到了满足要求的解，在此基础上右移right指针和left指针，对内部元素和的增加减少都是符合规律的**。如果有负数，那么右移指针和内部元素和大小就没有必然关系了**
螺旋矩阵II（leecode59）
链接：https://leetcode.cn/problems/spiral-matrix-ii/
问题描述
给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
处理想法
- 按照转圈的方向，数组增降排序，统一边界规则
- 总结一下最外层一圈，最上面一排有n-1个
- 内层第二圈，最上面一排有n-2 个
- 设置一个值来表示每一圈的变化
- 设置出x,y表示每一圈，每一条横竖开始的表示，一个二维的表示，横着发展的时候，纵坐标不变
循环不变量：【 ，】还是【 ，)统一规则
代码实现
class Solution {
public int[][] generateMatrix(int n) {
//储存结果result[][]二维数组
int result[][] = new int[n][n];
//标记每一次循环转圈开始的位置
int startRow = 0, startCol = 0;
//循环次数：奇数循环次数 = n / 2 + 1 （最后中间多一横）
//偶数循环次数为n / 2
int loop = n / 2 ;
int offset = 1;//卡住边界
int count = 1;//标记第一个点（记录数）
int i,j;
int mid = n / 2 ;
//开始循环,loop表示的是循环次数，loop+1表示的是每次循环右边的边界
while(loop > 0){
i = startRow;
j = startCol;
//模拟每一次循环的上左到上右（左闭右开）
//其中的行号不变，只有列号发生改变
for(j = startCol;j < n - offset;j++){
result[startRow][j] = count++;
}
//模拟每一次循环的上右到下右（左闭右开）
//其中的行号变化，只有列号不变
for(i = startRow;i < n - offset;i++){
result[i][j] = count++;
}
//这个过程中左边数组的元素到右边是递减的
//模拟每一次循环的下右到下左（左闭右开）
//其中的行号不变，只有列号发生改变
for(;j > startCol;j--){
result[i][j] = count++;
}
//模拟每一次循环的下左到上左（左闭右开）
//其中的行号变化，只有列号不变
for(;i > startRow;i--){
result[i][j] = count++;
}
//第二圈开始的时候，需要添加一些条件
startRow++;
startCol++;
offset++;
loop--;
}
//n为奇数，补充最后一个元素
if(n % 2 == 1){
result[mid][mid] = count;
}
return result;
}
}
示意图
