数组

https://leetcode-cn.com/circle/discuss/6Ghjnw/

本篇主要列举一些输入是一维数组或者二维数组的题目，其中包括了一些可以用二分法和摩尔投票法的题目。

1. 考虑边界？

二分 - 查找元素或者索引

1. 开闭 -> 搜索区间

2. 计算 mid 时需要防止溢出

3. 运算优先级

4. ！！！部分解释错误 慎看 二分查找细节 https://leetcode-cn.com/problems/binary-search/solution/er-fen-cha-zhao-xiang-jie-by-labuladong/

5. while(left < right) 不表示 循环不变量的区间定义是 [left..right)，也就是说，如果我分析出，下一轮搜索区间是 [mid..10]，我会设置 right = 10，而不会设置 right = 11。

   作者：liweiwei1419 链接：https://leetcode-cn.com/problems/search-insert-position/solution/te-bie-hao-yong-de-er-fen-cha-fa-fa-mo-ban-python-/

1. 704. 二分查找：给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值target，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

2. 剑指 Offer 53 - I. 在排序数组中查找数字 I:统计一个数字在排序数组中出现的次数。

3. 35. 搜索插入位置：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
4. 34. 在排序数组中查找元素的第一个和最后一个位置：给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。

   情况 1 ：当 nums[mid] < target 时

   mid 一定不是 target 第一次出现的位置； 由于数组有序，mid 的左边一定比 nums[mid] 还小，因此 mid 的左边一定不是 target 第一次出现的位置； mid 的右边比 nums[mid] 还大，因此 mid 的右边 有可能 存在 target 第一次出现的位置。 因此下一轮搜索区间是 [mid + 1..right]，此时设置 left = mid + 1；

   情况 2 ：当 nums[mid] == target 时

   mid 有可能是 target 第一次出现的位置； mid 的左边也有可能是 target 第一次出现的位置； mid 的右边一定不是 target 第一次出现的位置。 因此下一轮搜索区间在 [left..mid]，此时设置 right = mid。

   情况 3 ：当 nums[mid] > target 时

   mid 一定不是 target 第一次出现的位置； mid 的右边也一定不是 target 第一次出现的位置； mid 的左边有可能是 target 第一次出现的位置，因此下一轮搜索区间在 [left..mid - 1]，此时设置 right = mid - 1。 重点在这里：把情况 ② 和情况 ③ 合并，即当 nums[mid] >= target 的时候，下一轮搜索区间是 [left..mid]，此时设置 right = mid。这样做是因为：只有当区间分割是 [left..mid] 和 [mid + 1..right] 的时候，while(left < right) 退出循环以后才有 left == right 成立。

5. 面试题 08.03. 魔术索引：魔术索引。 在数组A[0…n-1]中，有所谓的魔术索引，满足条件A[i] = i。给定一个有序整数数组，编写一种方法找出魔术索引，若有的话，在数组A中找出一个魔术索引，如果没有，则返回-1。若有多个魔术索引，返回索引值最小的一个。

   跳跃查找

二分 - 旋转排序数组

1. 33. 搜索旋转排序数组：升序排列的整数数组 nums 在预先未知的某个点上进行了旋转（例如， [0,1,2,4,5,6,7] 经旋转后可能变为 [4,5,6,7,0,1,2] ）。请你在数组中搜索 target ，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

   确定有序区间

2. 81. 搜索旋转排序数组 II：假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。

   1 2	1011110111 和 1110111101 这种。 此种情况下 nums[start] == nums[mid]，分不清到底是前面有序还是后面有序，此时 start++ 即可。相当于去掉一个重复的干扰项。

3. 面试题 10.03. 搜索旋转数组：搜索旋转数组。给定一个排序后的数组，包含n个整数，但这个数组已被旋转过很多次了，次数不详。请编写代码找出数组中的某个元素，假设数组元素原先是按升序排列的。若有多个相同元素，返回索引值最小的一个。

   1 2	// 重点1：当left符合时直接返回, 因为找的是最小的索引 重点2：当中间值等于目标值，将右边界移到中间，因为左边可能还有相等的值

4. 153. 寻找旋转排序数组中的最小值：假设按照升序排序的数组在预先未知的某个点上进行了旋转。例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] 。请找出其中最小的元素。

   排除右侧有序

5. 154. 寻找旋转排序数组中的最小值 II和剑指 Offer 11. 旋转数组的最小数字：与上一题的不同点在于数组中可能存在重复的元素。PS：虽然154标注是困难题，但是剑指offer11标注是简单题。个人认为153做完必做154，拓展思维能力。面试时候遇到的题目都比较简略，但是样例丰富，需要自行摸索隐藏条件

   分不清到底是前面有序还是后面有序，此时 right– 即可。相当于去掉一个重复的干扰项。

二分 - 山脉数组

1. 941. 有效的山脉数组：给定一个整数数组 A，如果它是有效的山脉数组就返回 true，否则返回 false。
2. 852. 山脉数组的峰顶索引：给你由整数组成的山脉数组 arr ，返回任何满足 arr[0] < arr[1] < … arr[i - 1] < arr[i] > arr[i + 1] > … > arr[arr.length - 1] 的下标 i 。
        提升：返回峰顶对应的值，即山脉数组的最大值。
3. 1095. 山脉数组中查找目标值：给你一个 山脉数组 mountainArr，请你返回能够使得 mountainArr.get(index) 等于 target 最小 的下标 index 值。PS：较难，建议量力而行。

二维矩阵

1. 剑指 Offer 29. 顺时针打印矩阵：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
   提升：顺时针打印矩阵的最后一个点的坐标（假设坐标从0开始）

2. 54. 螺旋矩阵：给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。PS：与上一题只有返回值的数据类型不同。
3. 59. 螺旋矩阵 II：给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。
4. 48. 旋转图像和面试题 01.07. 旋转矩阵：给定一个 n × n 的二维矩阵表示一个图像。将图像顺时针旋转90度。
       提升：逆时针90度，顺时针或逆时针180度（翻转）。

   写出坐标式子，注意边界

5. 378. 有序矩阵中第K小的元素：给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
        提升：有序矩阵中第K大的元素

   归并 / 二分（用最大值和最小值的中间值，划分区域，左上角）

6. 74. 搜索二维矩阵：编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：每行中的整数从左到右按升序排列。每行的第一个整数大于前一行的最后一个整数。
7. 240. 搜索二维矩阵 II、剑指 Offer 04. 二维数组中的查找和面试题 10.09. 排序矩阵查找：编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：每行的元素从左到右升序排列。每列的元素从上到下升序排列。

滑动窗口

该类题目量力而行，普通求职者遇上的概率不大，面试官为难你或者对你期望比较高的时候很有可能会出这种常见的困难题。

1. 239. 滑动窗口最大值和剑指 Offer 59 - I. 滑动窗口的最大值：给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。
        提升1：修改输出的数据类型，比如：java中将输出改成List
        提升2：输入的数组或者滑动窗口为空

   单调队列（双端队列） $O(n)$ 加入删除各一次， $O(k)$ k

2. 480. 滑动窗口中位数：给你一个数组 nums，有一个大小为 k 的窗口从最左端滑动到最右端。窗口中有 k 个数，每次窗口向右移动 1 位。你的任务是找出每次窗口移动后得到的新窗口中元素的中位数，并输出由它们组成的数组。
        提升：如果数组个数是偶数，则在该窗口排序数字后，返回第N/2个数字。

   优先队列

中位数

与滑动窗口一样，属于常见的困难题，有一定可能遇到，建议量力而行。

1. 295. 数据流的中位数、剑指 Offer 41. 数据流中的中位数和面试题 17.20. 连续中值：如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
        提升：假设数字是不断进入数组的，在每次添加一个新的数进入数组的同时返回当前新数组的中位数。例如输入[1,2,3,4,5]，返回[1,1,2,2,3]。

摩尔投票法

1. 169. 多数元素、面试题 17.10. 主要元素和剑指 Offer 39. 数组中出现次数超过一半的数字：给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。
        思考：如果不保证给定数组总是存在多数元素，还能用摩尔投票法么？如果不能的话，思考下用什么方法做。
2. 229. 求众数 II：给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。

   摩尔投票法，分为两个阶段：配对阶段和计数阶段

   // 配对阶段 // 结果大于0 依次匹配 都不符合就都减票

   // 计数阶段 // 找到了两个候选人之后，需要确定票数是否满足大于 N/3

   如果至多选一个代表，那他的票数至少要超过一半（⌊ 1/2 ⌋）的票数；

   如果至多选两个代表，那他们的票数至少要超过 ⌊ 1/3 ⌋ 的票数；

   如果至多选m个代表，那他们的票数至少要超过 ⌊ 1/(m+1) ⌋ 的票数。

   https://leetcode-cn.com/problems/majority-element-ii/solution/liang-fu-dong-hua-yan-shi-mo-er-tou-piao-fa-zui-zh/

子序列/子数组

子序列可以不连续，子数组连续

1. 491. 递增子序列：给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。
        提升：输出最长的递增子序列 / 输出最长的非递减子序列 / 输出最长的递减子序列 / 输出最长的非递增子序列
2. 300. 最长递增子序列：给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
        提升1：输出最长的非递减子序列的长度 / 输出最长的递减子序列的长度 / 输出最长的非递增子序列的长度
        提升2：将上述题目中的子序列改成子数组（必须连续）。输出最长递增子数组长度，最长递增子数组具体数组，最长非递减子数组长度，最长非递减子数组具体数组，最长递减子数组长度，最长递减子数组具体数组，最长非递增子数组长度，最长非递增子数组具体数组。PS：量力而行，做到其中一个以后再改其他的。

   1. 暴力二进制枚举 看题目2^2500 不可能 $O(N·2^N)$
   2. DFS遍历 超时
   3. dp[i] 的值代表 nums 以 nums[i] 结尾的最长子序列长度。 $O(N^2)$
   4. dp+二分 $O(N·logN)$ // tail[i] 表示：长度为 i + 1 的 所有 上升子序列的结尾的最小值。

3. 53. 最大子序和和面试题 16.17. 连续数列：给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
       提升：输出组成最大子序和的具体数组，如有多对，尝试输出任意一个/所有可以构成最大子序和的组合

   dp[i]：表示以 nums[i] 结尾 的 连续 子数组的最大和。

4. 209. 长度最小的子数组：给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
5. 581. 最短无序连续子数组：给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。请你找出符合题意的最短子数组，并输出它的长度。
6. 718. 最长重复子数组：给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
7. 907. 子数组的最小值之和：给定一个整数数组 A，找到 min(B) 的总和，其中 B 的范围为 A 的每个（连续）子数组。

   单调栈

8. 560. 和为K的子数组：给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

   不能滑动窗口，因为不知道缩放条件，因为数组有正有负

9. 152. 乘积最大子数组：给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

二分+贪心

笔试常考题，用动规可能超出时间限制。

1. 1011. 在 D 天内送达包裹的能力：传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。

   假定「D 天内运送完所有包裹的最低运力」为 ans，那么在以 ans 为分割点的数轴上具有「二段性」：

   数值范围在 $(-\infty, ans)$ 的运力必然「不满足」 D 天内运送完所有包裹的要求 数值范围在 $[ans, +\infty)$ 的运力必然「满足」 D天内运送完所有包裹的要求

2. LCP 12. 小张刷题计划：为了提高自己的代码能力，小张制定了 LeetCode 刷题计划，他选中了 LeetCode 题库中的 n 道题，编号从 0 到 n-1，并计划在 m 天内按照题目编号顺序刷完所有的题目（注意，小张不能用多天完成同一题）。在小张刷题计划中，小张需要用 time[i] 的时间完成编号 i 的题目。此外，小张还可以使用场外求助功能，通过询问他的好朋友小杨题目的解法，可以省去该题的做题时间。为了防止“小张刷题计划”变成“小杨刷题计划”，小张每天最多使用一次求助。我们定义 m 天中做题时间最多的一天耗时为 T（小杨完成的题目不计入做题总时间）。请你帮小张求出最小的 T是多少。

   数值范围在 $(-\infty, 0)$ 的运力必然「不满足」要求 数值范围在 $[0, +\infty)$ 的运力必然「满足」 要求

3. 875. 爱吃香蕉的珂珂：珂珂喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 H 小时后回来。珂珂可以决定她吃香蕉的速度 K （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。返回她可以在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。

   边界/溢出/计算次数加速

4. 1482. 制作 m 束花所需的最少天数：给你一个整数数组 bloomDay，以及两个整数 m 和 k 。现需要制作 m 束花。制作花束时，需要使用花园中 相邻的 k 朵花 。花园中有 n 朵花，第 i 朵花会在 bloomDay[i] 时盛开，恰好 可以用于 一束 花中。请你返回从花园中摘 m 束花需要等待的最少的天数。如果不能摘到 m 束花则返回 -1 。

结束语

只是粗略把我笔记中数组和二分的常考（或者说是面试前必备）的题目列举了下。我并不能保证大家笔试面试中肯定会遇到以上题目，但说实话：上述的题目及其变型都不算太难，但是细节差别比较大，可能会导致大家在写的时候出很多问题，如果不在面试前多思考多解决的话，只能靠运气过面试了。