刷题记录-数组

7.7 数组题目笔记

leetcode 找到最小无序区间的长度，此无序区间修改后整体数组是升序的。

思路：使用双指针法，按照交叉从两侧逼近中间的方式获取最小区间的边界，然后利用边界取得最小无序区间长度。判断无序的条件是，最大值初始化为第一个，若当前值小于最大值，说明出现了无序，此时更新右边界。最小值和边界更新的思路一致。这种方法可以实现o(n)的时间复杂度，一次遍历。

leetcode 将数组中所有0值移到最后，其他值的相对顺序不变。

思路：借助原数组空间实现in-place交换。因为将“0”移到最后，该值是可知的，所以使用快慢指针的方法，慢指针作为待更新的数组下标位置，快指针为迭代的下标。可以实现一次遍历。同类型题目，sort colors

7.12

leetcode 长度为1+n的数组中，元素范围为1-n，找出重复的数字

思路：二分法。二分n值，每次统计二分值左右元素的个数，缩小重复数字所在的范围，最后确定该值。注意点是二分时begin和end的边界。

leetcode 二维棋盘上，从左上到右下的最短路径，或者是可行路径的条数。

思路：动态规划，用dp数组记录中间状态，找出递推关系，得出结果。

leetcode 装水最多的容器

思路：从两侧向中间靠拢，移动两侧板子中较短的一个，记录移动过程中的最大值。
延申：蓄水池，二维的，求能够蓄水的最大数量

记录当前位置两侧最高的柱子值，选取两者最短的一个作为侧面板，用当前高度减去两侧较短的高度，即为当前柱子可蓄水数。依次遍历每个柱子即可得到蓄水最大数量。
用栈记录递减柱子的index，直至找到递增的柱子，说明这个柱子存在蓄水的能力，然后利用栈中记录的index，计算蓄水量。依次遍历柱子数组即可得到结果。
思路与装水最多容器相似。从两侧向中间逼近，找出两侧柱子中较小的一个，然后往前遍历，记录蓄水量。直至遍历结束，获得最后结果。

leetcode 求连续子数组的和为K的数量

思路：题目关键为连续子数组。用sum记录累加的结果，用hash_map记录过程中存在的sum的出现次数。这样就能依次遍历，得出和为K的连续子数组的数量。注意边界条件：m[0]=1

leetcode 合并有交叉的数组

思路：先排序，然后将当前组合push进结果中，然后更新结果中的值即可。

leetcode 找到有序数组中重复数字的第一个和最后一个的位置

思路：分两步找边界。注意点是比较时的等号情况。
拓展：求旋转数组中target的位置
思路：先判定哪一部分是旋转数组，然后注意等号的情况。

leetcode 跳跃游戏，每个元素值表示能跳的长度，判断是否能够跳到最后

思路：用变量记录能跳到的最大坐标，不断更新。循环条件是当前位置不大于最大坐标且小于数组长度。若最后能够遍历到末尾，则可以跳到，否则，跳不到。
拓展：已知一定可以跳到最后，求最少跳跃次数。
思路：只有当不得已才跳，需要记录前一次能够跳到的最大位置。若当前下标小于等于依次遍历的坐标，需要跳一次了。此时更新跳跃次数和当前下标。