之前立了flag说这个学期要写技术blog,正好今日喜迎国庆,值此佳节,实乃开启撰写技术博客之旅的好时机。同时,我也希望能与广大CSDNer进行技术交流并获得指导。那么,就从第一篇文章开始吧!
刷题思路
首先简单规划一下准备刷力扣的思路,在参考了若干大佬的文章后,我准备按照 数组→链表→二叉树/树→二分查找→BFS/DFS 的顺序进行刷题。每种类型的题目先刷5-10题,对刷题有个初步的了解以后再进行更深入的刷题。
(算法虐我千百遍,我待算法如初恋。希望能享受在算法的海洋里遨游的过程~)
刷题随想
数组专题做的第一道题其实是twoSum,但感觉好像能写的不多,主要就两种思路:
- 双重for循环遍历,找到加和符合target的两个数就break。
- 运用基于红黑树的map映射(个人将map与python里的字典做类比),通过遍历一遍或两遍hash表实现。
做的第二题是第11题:盛最多水的容器
这道题目实质上是算面积。由于没有任何经验,因此刚开始拿到题目的第一思路就是穷举。后来想了一下,这种方法其实也可以称为双指针(双索引)嘛,只不过两个指针扫描的方向和出发的位置都一毛一样而已:双重for循环,算出所有area,不断更新并记录max area。
但这个算法复杂度就是了,有点可怕。。。
又想了大概10min,依然想不到什么好的思路,便去看了下题解。当点开官方题解,看到“双指针”三个字,以及简要描述后,我一瞬间感觉被闪电击中,思路一下就被激发了:
设置一左一右两个指针(索引)。因为面积的计算公式是:min(height[l],height[r])*(r-l),因此我们每次移动数组元素值较小(height[l]或height[r])的元素的指针;且移动时,l每次往右移动一位,r往左移动一位。这样能在l和r之间的距离缩小的同时,更新min(height[l],height[r])的值。不断重复这个过程,算出每一个area,并更新记录max area的值。此时,仅需扫描一遍数组即可,时间复杂度降为了。
后来,我发现移动左/右指针的过程与快排中的颇为类似。因此,我又优化了一下代码,把
for(int i=0;i<height.size();i++)
改成了
while(l!=r)
这样,执行时间从76ms降到了60ms,超过了约98%的提交者~
最后,附完整代码如下:
//双指针解法
//T:O(n) S:O(1)
class Solution {
public:
int maxArea(vector<int>& height) {
int l=0,r=height.size()-1;
int ma=0;
while(l!=r)
{
int tmp=min(height[l],height[r])*(r-l);
if(tmp>ma) ma=tmp;
if(height[l]<height[r]) l++;
else r--;
}
return ma;
}
};