今天的算法题难度明显上升,做好准备吧。可以自己先试着做一遍,不会也没关系,至少要清楚题目的具体要求。
要开始喽。
一.977有序数组的平方
题目建议:本题关键在于理解双指针思想
1.思路分析
1)暴力代码
本人第一次做这道题的想法是:想象一个图书馆,甲乙丙三人来到一个两层楼高的书架前,书架上的书都是各个数组元素平方后的数字。甲和乙站在二楼负责寻找合适的书并报号,而丙站在一楼清空书架,按照甲乙两人的指示重新放书。至于甲乙两人怎么寻找合适的书:甲站在第一本书的位置,问乙能不能找到比甲还要厚的书,找到的话就交换,于是乙从第二本书开始找,直到走到末尾为止。这样可以保证此时甲拿到的就是最厚的书了。此时,甲把书的名字告诉丙,丙把最厚的书放到下方书架的第一个位置。之后,甲再走到第二本书的位置,乙回到第三本书的位置,再来一遍循环寻找第二厚的书。以此类推。
2)双指针法
数组其实是有序的,只不过负数平方之后可能成为最大数了。那么数组平方的最大值就在数组的两端,不是最左边就是最右边,不可能是中间。此时可以考虑双指针法了,i指向起始位置,j指向终止位置。定义一个新数组result,和A数组一样的大小,让k指向result数组终止位置。
如果 A[ i ] *A[ i ] < A[ j ] * A[ j ] ,那么 result [ k-- ] = A[ j ] * A[ j ] 。
如果 A[ i ] *A[ i ] >= A[ j ] * A[ j ] ,那么 result [ k-- ] = A[ i ] * A[ i ]。
理解起来要是吃力,可以看一下上方视频链接,老师讲的还是蛮清楚的。
2.代码详解
1)暴力代码
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* sortedSquares(int* nums, int numsSize, int* returnSize) {
*returnSize=numsSize;
for(int i=0;i<numsSize;i++){
nums[i]=nums[i]*nums[i];
}
int* result=(int*)malloc(sizeof(int)*numsSize);
int slow=0;
for(int fast=0;fast<numsSize;fast++){
for(int fast2=fast+1;fast2<numsSize;fast2++){
if(nums[fast]>nums[fast2]){
int j=nums[fast];
nums[fast]=nums[fast2];
nums[fast2]=j;
}
}
result[slow++]=nums[fast];
}
return result;
}
2)双指针法
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* sortedSquares(int* nums, int numsSize, int* returnSize) {
*returnSize=numsSize;
int left=0;
int right=numsSize-1;
int* result=(int*)malloc(numsSize*sizeof(int));
for(int slow=numsSize-1;slow>=0;slow--){
int sqLeft=nums[left]*nums[left];
int sqRight=nums[right]*nums[right];
if(sqLeft>=sqRight){
result[slow]=sqLeft;
left++;
}
else {
result[slow]=sqRight;
right--;
}
}
return result;
}
二.209长度最小的数组
题目建议:本题关键在于理解滑动窗口,这个滑动窗口看文字讲解 还挺难理解的,建议大家先看视频讲解。 拓展题目可以先不做。
1.思路分析
以题目中的示例来举例,s=7, 数组是 2,3,1,2,4,3,来看一下查找的过程:
最后找到 4,3 是最短距离。
其实从动画中可以发现滑动窗口也可以理解为双指针法的一种!只不过这种解法更像是一个窗口的移动,所以叫做滑动窗口更适合一些。
在本题中实现滑动窗口,主要确定如下三点:
- 窗口内是什么?
- 如何移动窗口的起始位置?
- 如何移动窗口的结束位置?
窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。
窗口的起始位置如何移动:如果当前窗口的值大于s了,窗口就要向前移动了(也就是该缩小了)。
窗口的结束位置如何移动:窗口的结束位置就是遍历数组的指针,也就是for循环里的索引。
解题的关键在于 窗口的起始位置如何移动,如图所示:
另外,这道题的代码涉及到c语言里的条件运算符,忘记了的话去温习一下。
2.代码详解
int minSubArrayLen(int target, int* nums, int numsSize) {
int left=0;
int right=0;
int length=0;
int minLength=INT_MAX;
int sum=0;
for(;right<numsSize;right++){
sum+=nums[right];
while(sum>=target){
length=right-left+1;
minLength=minLength>length?length:minLength;
sum-=nums[left++];
}
}
minLength=(minLength==INT_MAX?0:minLength);
return minLength;
}
三.螺旋矩阵II
题目建议:本题关键还是在转圈的逻辑,在二分搜索中提到的区间定义,在这里又用上了。
1.思路分析
以下分析仅仅解释代码中的一些比较难理解的小地方。至于大体框架请看上方视频链接。看完之后请在草纸上画一个3*3和4*4的方块图。边看图,边看分析提示。
1)处理这个矩阵,就要像扒洋葱皮一样运用while循环顺时针一层一层地处理这个矩阵。
那为什么一共是n/2层循环呢?你把4*4的方块图沿着中间上下切开,上面的层数就是整个方块图循环的层数。就好比你在纸上画个年轮,你在中间切开,你数一下上边一共有几个线条,那这个年轮就有多少层。
那奇数层怎么办?除去n/2层之后,你会发现永远会剩下一个中心点,那个中心点最后单独赋值就可以了。
2)遍历每一圈的每一条边框时,我们都要严格遵守左闭右开的原则。
3) 对于起始点startX、startY和偏移量offset的赋值与循环之后的变化,拿4*4的矩阵模拟一下流程就清楚了。
2.代码详解
/**
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *returnColumnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
int** generateMatrix(int n, int* returnSize, int** returnColumnSizes) {
//初始化返回的结果数组的大小
*returnSize = n;
*returnColumnSizes = (int*)malloc(sizeof(int) * n);
//初始化返回结果数组ans
int** ans = (int**)malloc(sizeof(int*) * n);
int i;
for(i = 0; i < n; i++) {
ans[i] = (int*)malloc(sizeof(int) * n);
(*returnColumnSizes)[i] = n;
}
int startX=0;
int startY=0;
int offset=1;
int count=1;
int loop=n/2;
int middle=n/2;
while(loop){
int i=startX;
int j=startY;
for(;j<startY+n-offset;j++){
ans[i][j]=count++;
}
for(;i<startX+n-offset;i++){
ans[i][j]=count++;
}
for(;j>startY;j--){
ans[i][j]=count++;
}
for(;i>startX;i--){
ans[i][j]=count++;
}
startX++;
startY++;
offset+=2;
loop--;
}
if(n%2){
ans[middle][middle]=count;
}
return ans;
}
如果你有问题或者有其他想法,欢迎评论区留言,大家可以一起探讨。