一、977.有序数组的平方
题目链接:
学习前:
思路:
双向指针。left是从左往右遍历数组,right是从优往左遍历数组,将left和right中绝对值较大数的平方从右往左放入新数组中;新思路:if(left+right>=0)right,else left
时间复杂度:O(n)
空间复杂度:O(1)
学习后:
复习
二、209.长度最小的子数组
题目链接:
学习前:
思路: 暴力解法/滑动窗口。
- 暴力解法:2个for循环,外层循环指向子数组的第一个元素,内层循环结束时指向子数组的最后一个元素或者没找到子数组循环结束,并增加了flag标志位进行优化。
- 滑动窗口:left和right两个指针,left指向子数组的第一个元素,right指向子数组的最后一个元素,然后不断移动left,找到长度最小的子数组,当不满足条件时,继续移动right寻找。
时间复杂度:暴力解法O(n^2),滑动窗口O(n)
空间复杂度:均为O(1)
学习后:
复习
三、59.螺旋矩阵II
题目链接:
学习前:
思路:
正方形的四条边,等分成四条不同方向的边,包含头去掉尾,即[头,尾);若n为奇数,则最后一圈只有一个值,循环结束后再赋值。
时间复杂度:O(n^2)
空间复杂度:O(1)
学习后:
-
要遵循循环不变量原则,这里是指每一圈的四条边的操作规则是不变的,头闭尾开
-
定义区间的端点值,左端点为startX和startY,右端点均为n-offset,其中offset为右边界收缩量;循环次数为loop=n/2,因为每一圈中首和尾均被遍历。
-
第一步优化:由于是正方形矩阵,startX和startY合并为start
-
第二步优化:offset和loop合并,loop=0,loop++,loop<n/2
-
第三步优化:start也不需要了,将局部变量i和j扩大范围,左端点为loop,右端点为n-loop,即[loop,n-loop)
-
四、学习总结
- 时间:1.5h+1h
- 数组总结
- 基本涉及到循环和区间问题,对于循环,采用双指针(包含左右相向指针、快慢指针、滑动窗口)降低时间复杂度。
- 在数组有序时,应用比较多
- 循环不变量原则:在循环中,某一些操作是相同的