网站模板 红色,私密浏览器免费,制作网页教学反思,北京建行网站代码随想录二刷 #xff5c; 数组 #xff5c; 总结篇 基础知识二分查找移除元素有序数组的平方长度最小的数组最小覆盖子串螺旋数组 基础知识
定义#xff1a;数组是存放在连续内存空间上的相同类型数据的集合
特点#xff1a;
数组下标从 0 开始数组内存空间的地址是连… 代码随想录二刷 数组 总结篇 基础知识二分查找移除元素有序数组的平方长度最小的数组最小覆盖子串螺旋数组 基础知识
定义数组是存放在连续内存空间上的相同类型数据的集合
特点
数组下标从 0 开始数组内存空间的地址是连续的
vector 和 array 的区别vector底层实现是 array严格来讲 vector 是容器不是数组
C中二维数组在地址空间上是连续的
二分查找
注意循环不变量原则
左闭右闭 right nums.size() - 1while (left right)right middle - 1;left middle 1; 左闭右开 right nums.size()while (left right)right middleleft middle 1
移除元素
双指针法通过一个快指针和慢指针在一个 for 循环下完成两个 for 循环的工作
相向双指针a指针从左到右b指针从右到左a指针找等于目标值的位置b指针找不等于目标值的位置然后每次找到一个用b指针覆盖a指针
有序数组的平方
双指针法a指针从左到右b指针从右到左两个指针每次比较平方的大小大的存入结果数组并移动指针小的停在原地
时间复杂度O(n) 空间复杂度O(n)
长度最小的数组
滑动窗口双指针的变种这一题需要两个指针都能固定住且一个指针固定另一个可以连续变化
外层for循环更改一个指针内层用while循环连续更新另一个指针。
时间复杂度O(n) 空间复杂度O(1)
最小覆盖子串
创建一个unorder_map 维护目标字符串各字母出现的次数。
再创建一个unordered_map记录遍历过中目标字符串各个字母出现的次数方便修改并且不用在滑动窗口变化时对上一个 map 进行修改
遍历过程中如果达到目标字符串次数就收缩窗口左边界并且记录窗口起点当收缩的窗口不能完全覆盖目标字符串就扩展窗口右边界直到再次能完全覆盖
当右窗口到达终点左边界收缩完成将此时的起点用于分割字符串
螺旋数组
对于正方形的二维数组只需要考虑转多少圈以及最后中间是否只剩一个值如果剩一个值需要再转完圈后单独加中间的值。另外转圈过程要保持循环不变量的原则。
对于矩形二维数组编程一维数组的情况需要在转完圈后单独考虑最内圈剩下的一行或者一列。
总结参考录友海螺人的思维导图 代码随想录
