代码随想录第十二期集训营-第二天
今天是集训营的第二天,任务是完成977、209以及59三道题,今天之后代码随想录第一部分数组就全部完成,这两天的题目解法分为两大类,一类是二分查找,另一类是双指针。
977.有序数组的平方
这题是有序数组,如果要是没有负数,就很简单,直接全平方就好,但是有负数,就说明平方后的最大值有可能是负数的平方,出现在数组末尾。找最大值时,肯定是比较两端,最大值一定不在中间,只要求出两端的平方之后比较,就能找到最大值。
还有要注意的是,新数组是正序排列,所以你找到最大值之后要放在新数组的末尾,也就是说要倒序for循环遍历新数组。
class Solution { public int[] sortedSquares(int[] nums) { int length = nums.length; int firstIndex = 0; int lastIndex = length - 1; int[] res = new int[length]; for(int i = nums.length - 1;i >= 0;i--){ if(nums[firstIndex] * nums[firstIndex] >= nums[lastIndex] * nums[lastIndex]){ res[i] = nums[firstIndex]*nums[firstIndex]; firstIndex++; }else{ res[i] = nums[lastIndex]*nums[lastIndex]; lastIndex--; } } return res; } }
209.长度最小的子数组
这题用滑动窗口做,什么是滑动窗口,简单来说还是双指针,只不过我们要两个指针之间的元素集合,就像一个窗户在移动一样,还是用两个指针一个for循环替代两个for循环。做滑动窗口的关键就是要确定怎么找到滑动窗口的起始位置和终止位置,终止位置就是for循环中的索引,起始位置是自己设定变量,在for循环内移动即可。那如果说起始位置是for循环的索引会怎么样呢?那我们是不是还需要有一样东西还表示终止位置,先固定住起始位置指针,再移动终止位置指针,这不就又成了双层for循环了吗。
在本题中,我们要知道三个点:
1.窗口的集合代表什么?代表了满足sum >= target的集合
2.怎么移动终止指针?for循环动就好
3.怎么移动起始指针?满足sum>=target时就可以移动,压缩窗口
class Solution { public int minSubArrayLen(int target, int[] nums) { int begin = 0; int res = Integer.MAX_VALUE; int sum = 0; for(int end = 0;end < nums.length;end++){ sum += nums[end]; //判断是否大于等于target while(sum >= target){ //截取出当前窗口的长度,和res比较 int subLength = end - begin + 1; res = res <= subLength ? res : subLength; //然后把这个窗口起始值从sum中扣除,窗口的起始位置往前移动一位 sum = sum - nums[begin]; begin++; } } return res != Integer.MAX_VALUE ? res : 0; } }
59.螺旋矩阵
这题就是模拟题,关键就是要知道遍历各条边时,从哪开始到哪结束,这个范围一定要统一好。这题最好是画图,看得更直观
class Solution { public int[][] generateMatrix(int n) { int[][] res = new int[n][n]; //遍历次数 int count = 0; int start = 0; int num = 1; int column = 0; int row = 0; while(count++ < n/2){ //从左到右 /* 这里n-count就是在确定遍历范围,假如我要存放在3*3的矩阵,从左到右添加第一行元素时我就管前两个,最后一个放到从上到下遍历,后面都是这个道理。 */ for(column = start;column < n - count;column++){ res[start][column] = num; num++; System.out.print(res[0][column]); } //从上到下 for(row = start;row < n - count;row++){ res[row][column] = num; num++; System.out.print(res[row][column]); } //从右到左 for(;column >= count;column--){ res[row][column] = num; num++; System.out.print(res[row][column]); } //从下上 for(;row >= count;row--){ res[row][column] = num; num++; System.out.print(res[row][column]); } start++; } if(n % 2 != 0){ res[n/2][n/2] = num; } return res; } }
第二天打卡成功!
#2022毕业即失业取暖地##2022毕业生求职现身说法##2022毕业的你对23届的寄语##如何判断面试是否凉了#