977. 有序数组的平方
思路:给定的数组已经按照从小到大的顺序排序,这也就意味着,从绝对值的角度来看,数组开头和结尾的元素的绝对值更大,中间的元素绝对值更小;而绝对值更大的数,它的平方值也会更大。由此,我们可以考虑建立一个新的数组作为返回数组,并在给定有序数组中不断选择平方最大的元素,将其平方填入新数组中空闲位置的最后一位。而选择平方最大的元素,只需设定两个指针left和right,分别指向数组的开头元素和尾部元素并进行比较。填入数据后,对应的指针向后或向前移动一位,重复以上操作,直到数组所有元素都被遍历到。
时间复杂度:O(n)。因为只是对给定数组进行了一次遍历。
空间复杂度:O(n),因为创建了一个长度为n的数组。
代码如下所示:
209.长度最小的子数组
一开始做题的时候是真的没有思路,后来看到标签是滑动窗口,慢慢想明白了该怎么做。
思路:首先确定两个指针slow和fast,用以确定滑动窗口的大小。fast每次都向前移动一位,然后计算fast与slow之间(包括它们俩)的所有元素的和,并与目标值target比较。如果大于或等于,则将当前fast与slow间的长度与返回值进行比较,如果当前长度更小,则将其赋给返回值,并将和删去slow指向的元素的值,重复上述比较步骤,直到fast完成遍历,且和比target小为止。
时间复杂度:O(n)。
代码块如下所示:
59.螺旋矩阵II
这道题刚开始的时候真的没有思路,是看了题解才知道怎么写的。其实难并不难,确定好循环的圈数,开始位置,以及四条边循环的长度就迎刃而解;但是处理起来很“琐碎”,两次写起来都不够熟练,说明我对代码的处理确实还不够熟悉。还需要再继续进行练习啊。
代码块如下所示: