算法D2 | 977.有序数组的平方 ,209.长度最小的子数组 ,59.螺旋矩阵II ,总结

建议大家先独立做题,然后看视频讲解,然后看文章讲解,然后在重新做一遍题,把题目AC,最后整理成今日当天的博客

 977.有序数组的平方 

题目建议: 本题关键在于理解双指针思想 

题目链接:https://leetcode.cn/problems/squares-of-a-sorted-array/

文章讲解:https://programmercarl.com/0977.%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E7%9A%84%E5%B9%B3%E6%96%B9.html

视频讲解: https://www.bilibili.com/video/BV1QB4y1D7ep

这个题蛮直接的,逻辑就是双指针从两头开始计算,把平方最大的结果先放进结果。

Python版本:

C++版本:

产生一个固定长度的空vector,用 vector<int> vec(n); 精华在于,每次初始化一个变量,都把其中的数据类型说清楚。

209.长度最小的子数组

题目建议: 本题关键在于理解滑动窗口,这个滑动窗口看文字讲解 还挺难理解的,建议大家先看视频讲解。  拓展题目可以先不做。 

题目链接:https://leetcode.cn/problems/minimum-size-subarray-sum/

文章讲解:https://programmercarl.com/0209.%E9%95%BF%E5%BA%A6%E6%9C%80%E5%B0%8F%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84.html

视频讲解:https://www.bilibili.com/video/BV1tZ4y1q7XE

这个题目暴力解法是两层forloop,时间复杂度是O(n^2),leetcode系统会判定超时。

这里滑动窗口的概念和以前接触的“滑动窗口”意义有一些不同,这里的滑动窗口长度是可变的,在满足某个条件以后,进行改变。把两层循环优化成一层循环的关键在于,仅当右指针之前的和大于目标值以后,再将左指针左移,且不会再回移左指针。

Python版本:

C++版本:

C++中 inf的表达,这里采用了INT_MAX, 即 整数的最大值; 对应int这个类型的inf。

 59.螺旋矩阵II

题目建议:  本题关键还是在转圈的逻辑,在二分搜索中提到的区间定义,在这里又用上了。 

题目链接:https://leetcode.cn/problems/spiral-matrix-ii/

文章讲解:https://programmercarl.com/0059.%E8%9E%BA%E6%97%8B%E7%9F%A9%E9%98%B5II.html

视频讲解:https://www.bilibili.com/video/BV1SL4y1N7mV/

这个题比较直接,把方向搞清楚了就行,这里我写得和carl不一样,定义了四个方向,按条件判断是否换方向,然后顺序填入数字就完事。

Python版本:

C++版本:

和python版本区别不大,主要学了nested list如何表达(vector<vector<int>>), c++版本写成了forloop而不是while(python版),这个case没什么区别。

c++语法学习:

vector的构造函数有一种是:vector<数据类型> 变量名(n,elem) ,数组里包含是n个elem。内层容器装了n个0,外层容器装了n个内层容器,即n*n的数组,每个元素都是0。

总结 

题目建议:希望大家 也做一个自己 对数组专题的总结

文章链接:https://programmercarl.com/%E6%95%B0%E7%BB%84%E6%80%BB%E7%BB%93%E7%AF%87.html

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容