1. Search in Array
给定一个n个元素有序的（升序）整型数组nums 和一个目标值target ，写一个函数搜索nums中的 target，如果目标值存在返回下标，否则返回 -1。
解：标准的二分查找，这里使用左闭右开。
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
解：插入位置的二分查找，这里使用左闭右开，当目标值不存在的时候，注意最后一轮的左右边界。
给你一个字符数组 letters，该数组按非递减顺序排序，以及一个字符 target。letters里至少有两个不同的字符。返回letters中大于 target 的最小的字符。如果不存在这样的字符，则返回letters 的第一个字符。
解：其实就是插入位置的二分查找。
给你一个m * n的矩阵grid，矩阵中的元素无论是按行还是按列，都以非严格递减顺序排列。 请你统计并返回grid中 负数 的数目。
解：这道题其实不算二分法。从下往上，从做往右。如果 grid[i][j] 碰到负数，那本行右边都是负数。向上一行，如果grid[i][j]为正，j向右走，直到负数。
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回[-1, -1]。
解：第一个思路很简单。因为是整数，那就目标值加减0.5，然后找插入位置即可。另一个思路是老老实实找第一个和最后一个位置。
给你一个区间数组 intervals ，其中intervals[i] = [starti, endi] ，且每个starti 都 不同 。区间 i 的 右侧区间 可以记作区间 j ，并满足 startj>= endi ，且 startj 最小化 。注意 i 可能等于 j 。返回一个由每个区间 i 的 右侧区间 在intervals 中对应下标组成的数组。如果某个区间 i 不存在对应的 右侧区间 ，则下标 i 处的值设为 -1 。
解：用一个元组列表start_index记录每个区间的起点和index。排序。然后对每个区间，去寻找终点在start_index中的插入位置。
设计一个基于时间的键值数据结构，该结构可以在不同时间戳存储对应同一个键的多个值，并针对特定时间戳检索键对应的值。
实现 TimeMap 类：
TimeMap() 初始化数据结构对象
void set(String key, String value, int timestamp) 存储给定时间戳timestamp时的键key和值value。
String get(String key, int timestamp)返回key对应的值，该值的时间戳应小于等于 timestamp。如果有多个这样的值，它将返回最大时间戳的值。如果没有值，则返回空字符串（""）。
解：字典的key在不同时间戳可以储存多个值。那value就用列表。每个列表元素都是一个元组。放入(时间戳，值)。这样就有了一个以时间戳排序的列表。get就用二分法寻找。
实现支持下列接口的「快照数组」- SnapshotArray：
SnapshotArray(int length)- 初始化一个与指定长度相等的 类数组 的数据结构。初始时，每个元素都等于 0。
void set(index, val)- 会将指定索引index处的元素设置为val。
int snap()- 获取该数组的快照，并返回快照的编号snap_id（快照号是调用snap()的总次数减去1）。
int get(index, snap_id)- 根据指定的snap_id选择快照，并返回该快照指定索引 index的值。
解：对每个索引 index 建立一个字典。里面的键值对为 快照编号：值。因此查找的时候，由索引定位到字典。字典的key是快照编号。排序后，可以二分查找。这里需要注意，因为每次快照后，我们并没有在字典中更改key的值。因此，要找到目标快照的前一个快照编号。这里用bisect_right（无相同值，返回插入位置，有相同值，返回相同值后一位），然后减1.
2. Rotated Array
整数数组 nums 按升序排列，数组中的值 互不相同 。在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为[4,5,6,7,0,1,2] 。给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回-1。
解：旋转数组都是先判断左右两边哪边是有序。再判断目标值是否在有序的半边。如果是，就找有序半边，否则就找无序半边。
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
解：旋转数组。先用 left mid 判断哪边有序。如果left < mid 则左边为有序半边，最小值left先记录上。然后改变边界，left = mid + 1。那下次while循环就处理无序的右半边。如果left > mid 则右边为有序半边，最小值 mid 先记录上。然后改变边界，right = mid。那下次while循环就处理无序的左半边。
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。给你一个可能存在 重复 元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
解：这题与上一题的区别在于可能存在相同的元素。解决的办法也很简单：如果mid == left且这两个索引不同，那就left前进一位好了，直到不等，或者两者索引相同。
3. Standard Search
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
解：找到第一个坏的。这里我们用左闭右开。如果mid是坏的，right = mid。有可能mid就是第一个坏的，那其左边都是好的就会找不到坏的。这其实没有关系，因为我们会在找到边界的时候停止，且left + 1.返回 left 即可。
给你一个满足下述两条属性的 m x n 整数矩阵：每行中的整数从左到右按非严格递增顺序排列。每行的第一个整数大于前一行的最后一个整数。给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
解：这个矩阵其实可以拉长了变成一个array。
4. Math
给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false 。完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。不能使用任何内置的库函数，如 sqrt 。
解：用二分法从1到num+1去试。
给你一个非负整数 x ，计算并返回x的 算术平方根 。由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。注意：不允许使用任何内置指数函数和算符 。
解：这道题和上题类似，唯一需要注意的是，返回的是left-1
你总共有n 枚硬币，并计划将它们按阶梯状排列。对于一个由 k 行组成的阶梯，其第 i 行必须正好有 i 枚硬币。阶梯的最后一行 可能 是不完整的。给你一个数字n ，计算并返回可形成 完整阶梯行 的总行数。
解：能形成完整k行阶梯的数字是(k+1)/2*k。输入n，找的n能形成的台阶数。
给你一个 严格升序排列的正整数数组 arr和一个整数k。请你找到这个数组里第k个缺失的正整数。
解：如果没有缺失，那 arr[i] = i + 1，如果刚好是缺失的第k个整数，那 arr[i] = i + 1 + k.
给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数，citations 已经按照升序排列 。计算并返回该研究者的 h 指数。h 指数的定义：h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （n 篇论文中）至少 有 h 篇论文分别被引用了至少 h 次。
解：只要 citations[i] >= i+1就可以当做h的候选。
给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。请你找出并返回只出现一次的那个数。
解：检查 i 的左右，如果左右都满足（靠边或者不等），那 i 就是那个唯一数。如果mid是偶数，且与前一个数相等。那单次数应该出现在右侧；如果mid是奇数，且与前一个数不等，那单次数应该出现在右侧。
给定一个长度为n的整数 山脉 数组arr，其中的值递增到一个峰值元素然后递减。返回峰值元素的下标。
解：判断峰值：左右都小于峰值。
给定一个 排序好 的数组arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。整数 a 比整数 b 更接近 x 需要满足：|a - x| < |b - x| 或者 |a - x| == |b - x| 且 a < b。
解：目标是找到区间的起始点。认真看注释。
给定两个大小分别为 m 和 n 的正序（从小到大）数组nums1 和nums2。请你找出并返回这两个正序数组的 中位数 。算法的时间复杂度应该为 O(log (m+n)) 。
解： 在两个数组内各自找一个分割点 X Y。Y = (len1 + len2 + 1) // 2 - X，以保证在两个序列中，X Y 左边的元素个数合起来有总数的一半。然后比较XY左右的元素，看是否满足中位数的要求。
5. As A Tool
给定一个包含非负整数的数组nums ，返回其中可以组成三角形三条边的三元组个数。
解：先留下正数，排序。然后用两层循环枚举前两条较短的边，接着用二分查找第三条边。
给你两个正整数数组spells 和potions，长度分别为n 和m，其中spells[i]表示第i个咒语的能量强度，potions[j]表示第j瓶药水的能量强度。同时给你一个整数success。一个咒语和药水的能量强度 相乘 如果大于等于success，那么它们视为一对成功的组合。请你返回一个长度为 n的整数数组 pairs，其中 pairs[i]是能跟第 i个咒语成功组合的 药水数目。
解：把药水排序，能成功的条件是药水大于 success/spell
给你一个整数数组 nums 和一个整数 target 。请你统计并返回 nums 中能满足其最小元素与最大元素的 和 小于或等于 target 的 非空 子序列的数目。由于答案可能很大，请将结果对109+ 7取余后返回。
解：双指针法：使用双指针分别指向数组的两端：左指针left指向数组的开始，右指针right指向数组的末尾。如果nums[left] + nums[right]小于等于target，则以nums[left]为最小值，且最大值不超过nums[right]的所有子序列都是合法的。在这种情况下，从left到right之间有2^(right - left)种合法子序列。
给你一个 下标从 0 开始 的正整数数组w ，其中w[i] 代表第 i 个下标的权重。请你实现一个函数pickIndex，它可以 随机地 从范围 [0, w.length - 1] 内（含 0 和 w.length - 1）选出并返回一个下标。选取下标 i的 概率 为 w[i] / sum(w) 。例如，对于 w = [1, 3]，挑选下标 0 的概率为 1 / (1 + 3) = 0.25 （即，25%），而选取下标 1 的概率为 3 / (1 + 3) = 0.75（即，75%）。
解：先生成一个累加和，以 [1, 3] 为例子，累加和为 prefix_sum = [1, 4]，prefix_sum[-1] = 4即为总和。
然后从[1, 4] 中随机抽取一个正整数，随机数落在[1,1] 和 [2,4]的概率分别是25%，75%。因此挑选下标 0 的概率为25%，而选取下标 1 的概率为75%。
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。
解：记住这个方法LIS！建立一个最长严格递增单调栈。如果入栈的元素大于栈顶元素，直接入栈；否则，就用二分法寻找插入位置，替代插入位置的元素（由于用bisect_left返回的位置插入后，替代的是其身后较大的元素，因此也增加了递增单调栈继续增长的可能性）
给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
解：应用LIS方法。先给信封按照宽度从小到大排序。随后高度按照从大到小排序（因为相同宽度，如果高度还从小到大排序，在应用LIS方法的时候，相同宽度的信封可以套娃，应避免）。之后对高度应用LIS即可。
