搜索二维矩阵II

//暴力破解法
//搜索每一行查找要的元素
class Solution {public boolean searchMatrix(int[][] matrix, int target) {//保证每个数字只查询一遍，且瞬间确定哪一行或者哪一列for (int i = 0; i < matrix.length; i++) {for (int j = 0; j < matrix[0].length; j++) {if (matrix[i][j] == target) {return true;}}}return false;}
}二分法
首先，我们确保矩阵不为空。那么，如果我们迭代矩阵对角线，从当前元素对列和行搜索，我们可以保持从当前 (row,col)(row,col) 对开始的行和列为已排序。 因此，我们总是可以二分搜索这些行和列切片。我们以如下逻辑的方式进行 : 在对角线上迭代，二分搜索行和列，直到对角线的迭代元素用完为止（意味着我们可以返回 false ）或者找到目标（意味着我们可以返回 true ）。binary search 函数的工作原理和普通的二分搜索一样,但需要同时搜索二维数组的行和列。
class Solution {private boolean binarySearch(int[][] matrix, int target, int start, boolean vertical) {int lo = start;int hi = vertical ? matrix[0].length-1 : matrix.length-1;while (hi >= lo) {int mid = (lo + hi)/2;if (vertical) { // searching a columnif (matrix[start][mid] < target) {lo = mid + 1;} else if (matrix[start][mid] > target) {hi = mid - 1;} else {return true;}} else { // searching a rowif (matrix[mid][start] < target) {lo = mid + 1;} else if (matrix[mid][start] > target) {hi = mid - 1;} else {return true;}}}return false;}public boolean searchMatrix(int[][] matrix, int target) {// an empty matrix obviously does not contain `target`if (matrix == null || matrix.length == 0) {return false;}// iterate over matrix diagonalsint shorterDim = Math.min(matrix.length, matrix[0].length);for (int i = 0; i < shorterDim; i++) {boolean verticalFound = binarySearch(matrix, target, i, true);boolean horizontalFound = binarySearch(matrix, target, i, false);if (verticalFound || horizontalFound) {return true;}}return false; }参考链接：https://leetcode-cn.com/problems/search-a-2d-matrix-ii/solution/sou-suo-er-wei-ju-zhen-ii-by-leetcode-2/

合并两个有序数组

//合并后排序
class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {//先把两个数组合并，然后进行排序System.arraycopy(nums2,0,nums1,m,n);Arrays.sort(nums1);}
}一般而言，对于有序数组可以通过 双指针法 达到O(n + m)O(n+m)的时间复杂度。
最直接的算法实现是将指针p1 置为 nums1的开头， p2为 nums2的开头，在每一步将最小值放入输出数组中。
由于 nums1 是用于输出的数组，需要将nums1中的前m个元素放在其他地方，也就需要 O(m)O(m) 的空间复杂度。class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {// Make a copy of nums1.int [] nums1_copy = new int[m];System.arraycopy(nums1, 0, nums1_copy, 0, m);// Two get pointers for nums1_copy and nums2.int p1 = 0;int p2 = 0;// Set pointer for nums1int p = 0;// Compare elements from nums1_copy and nums2// and add the smallest one into nums1.while ((p1 < m) && (p2 < n))nums1[p++] = (nums1_copy[p1] < nums2[p2]) ? nums1_copy[p1++] : nums2[p2++];// if there are still elements to addif (p1 < m)System.arraycopy(nums1_copy, p1, nums1, p1 + p2, m + n - p1 - p2);if (p2 < n)System.arraycopy(nums2, p2, nums1, p1 + p2, m + n - p1 - p2);}
}
链接：https://leetcode-cn.com/problems/merge-sorted-array/solution/he-bing-liang-ge-you-xu-shu-zu-by-leetcode/

鸡蛋掉落

题目是这样：你面前有一栋从 1 到 N 共 N 层的楼，然后给你 K 个鸡蛋（K 至少为 1）。现在确定这栋楼存在楼层 0 <= F <= N，在这层楼将鸡蛋扔下去，鸡蛋恰好没摔碎（高于 F 的楼层都会碎，低于 F 的楼层都不会碎）。现在问你，最坏情况下，你至少要扔几次鸡蛋，才能确定这个楼层 F 呢？

也就是让你找摔不碎鸡蛋的最高楼层 F，但什么叫「最坏情况」下「至少」要扔几次呢？我们分别举个例子就明白了。

比方说现在先不管鸡蛋个数的限制，有 7 层楼，你怎么去找鸡蛋恰好摔碎的那层楼？

最原始的方式就是线性扫描：我先在 1 楼扔一下，没碎，我再去 2 楼扔一下，没碎，我再去 3 楼……

以这种策略，最坏情况应该就是我试到第 7 层鸡蛋也没碎（F = 7），也就是我扔了 7 次鸡蛋。

先在你应该理解什么叫做「最坏情况」下了，鸡蛋破碎一定发生在搜索区间穷尽时，不会说你在第 1 层摔一下鸡蛋就碎了，这是你运气好，不是最坏情况。

现在再来理解一下什么叫「至少」要扔几次。依然不考虑鸡蛋个数限制，同样是 7 层楼，我们可以优化策略。

最好的策略是使用二分查找思路，我先去第 (1 + 7) / 2 = 4 层扔一下：

如果碎了说明 F 小于 4，我就去第 (1 + 3) / 2 = 2 层试……

如果没碎说明 F 大于等于 4，我就去第 (5 + 7) / 2 = 6 层试……

以这种策略，最坏情况应该是试到第 7 层鸡蛋还没碎（F = 7），或者鸡蛋一直碎到第 1 层（F = 0）。然而无论那种最坏情况，只需要试 log7 向上取整等于 3 次，比刚才尝试 7 次要少，这就是所谓的至少要扔几次。

PS：这有点像 Big O 表示法计算​算法的复杂度。
实际上，如果不限制鸡蛋个数的话，二分思路显然可以得到最少尝试的次数，但问题是，现在给你了鸡蛋个数的限制 K，直接使用二分思路就不行了。

比如说只给你 1 个鸡蛋，7 层楼，你敢用二分吗？你直接去第 4 层扔一下，如果鸡蛋没碎还好，但如果碎了你就没有鸡蛋继续测试了，无法确定鸡蛋恰好摔不碎的楼层 F 了。这种情况下只能用线性扫描的方法，算法返回结果应该是 7。

有的读者也许会有这种想法：二分查找排除楼层的速度无疑是最快的，那干脆先用二分查找，等到只剩 1 个鸡蛋的时候再执行线性扫描，这样得到的结果是不是就是最少的扔鸡蛋次数呢？

很遗憾，并不是，比如说把楼层变高一些，100 层，给你 2 个鸡蛋，你在 50 层扔一下，碎了，那就只能线性扫描 1～49 层了，最坏情况下要扔 50 次。

如果不要「二分」，变成「五分」「十分」都会大幅减少最坏情况下的尝试次数。比方说第一个鸡蛋每隔十层楼扔，在哪里碎了第二个鸡蛋一个个线性扫描，总共不会超过 20 次​。

最优解其实是 14 次。最优策略非常多，而且并没有什么规律可言。

说了这么多废话，就是确保大家理解了题目的意思，而且认识到这个题目确实复杂，就连我们手算都不容易，如何用算法解决呢？

思路分析

对动态规划问题，直接套我们以前多次强调的框架即可：这个问题有什么「状态」，有什么「选择」，然后穷举。

「状态」很明显，就是当前拥有的鸡蛋数 K 和需要测试的楼层数 N。随着测试的进行，鸡蛋个数可能减少，楼层的搜索范围会减小，这就是状态的变化。

「选择」其实就是去选择哪层楼扔鸡蛋。回顾刚才的线性扫描和二分思路，二分查找每次选择到楼层区间的中间去扔鸡蛋，而线性扫描选择一层层向上测试。不同的选择会造成状态的转移。

现在明确了「状态」和「选择」，动态规划的基本思路就形成了：肯定是个二维的 dp 数组或者带有两个状态参数的 dp 函数来表示状态转移；外加一个 for 循环来遍历所有选择，择最优的选择更新状态：

# 当前状态为 K 个鸡蛋，面对 N 层楼
# 返回这个状态下的最优结果
def dp(K, N):int resfor 1 <= i <= N:res = min(res, 这次在第 i 层楼扔鸡蛋)return res

这段伪码还没有展示递归和状态转移，不过大致的算法框架已经完成了。

我们选择在第 i 层楼扔了鸡蛋之后，可能出现两种情况：鸡蛋碎了，鸡蛋没碎。注意，这时候状态转移就来了：

如果鸡蛋碎了，那么鸡蛋的个数 K 应该减一，搜索的楼层区间应该从 [1…N] 变为 [1…i-1] 共 i-1 层楼；

如果鸡蛋没碎，那么鸡蛋的个数 K 不变，搜索的楼层区间应该从 [1…N] 变为 [i+1…N] 共 N-i 层楼。

PS：细心的读者可能会问，在第i层楼扔鸡蛋如果没碎，楼层的搜索区间缩小至上面的楼层，是不是应该包含第i层楼呀？不必，因为已经包含了。开头说了 F 是可以等于 0 的，向上递归后，第i层楼其实就相当于第 0 层，可以被取到，所以说并没有错误。

因为我们要求的是最坏情况下扔鸡蛋的次数，所以鸡蛋在第 i 层楼碎没碎，取决于那种情况的结果更大：

def dp(K, N):for 1 <= i <= N:# 最坏情况下的最少扔鸡蛋次数res = min(res, max( dp(K - 1, i - 1), # 碎dp(K, N - i)      # 没碎) + 1 # 在第 i 楼扔了一次)return res

递归的 base case 很容易理解：当楼层数 N 等于 0 时，显然不需要扔鸡蛋；当鸡蛋数 K 为 1 时，显然只能线性扫描所有楼层：

def dp(K, N):if K == 1: return Nif N == 0: return 0...

至此，其实这道题就解决了！只要添加一个备忘录消除重叠子问题即可：

def superEggDrop(K: int, N: int):memo = dict()def dp(K, N) -> int:# base caseif K == 1: return Nif N == 0: return 0# 避免重复计算if (K, N) in memo:return memo[(K, N)]res = float('INF')# 穷举所有可能的选择for i in range(1, N + 1):res = min(res, max(dp(K, N - i), dp(K - 1, i - 1)) + 1)# 记入备忘录memo[(K, N)] = resreturn resreturn dp(K, N)

可用的代码：
动态规划加二分搜索
很容易想到用动态规划来做这道题，之前也做过这道题。状态可以表示成 (K, N): K 为鸡蛋数和 N 为楼层数。当从第 X 楼扔鸡蛋的时候，要么鸡蛋不碎，状态变成 (K, N-X)，或者碎掉，状态变成 (K-1, X-1)。

动态规划的时间复杂度为 O(K N^2)O(KN2)，但对于这道题其实是不够高效的，可以做地更快。定义 dp(K, N) 为状态 (K, N) 下最多需要的步数。根据以上分析：

dp(K,N)=1≤X≤Nmin(max(dp(K−1,X−1),dp(K,N−X)))

class Solution {public int superEggDrop(int K, int N) {return dp(K, N);}Map<Integer, Integer> memo = new HashMap();public int dp(int K, int N) {if (!memo.containsKey(N * 100 + K)) {int ans;if (N == 0)ans = 0;else if (K == 1)ans = N;else {int lo = 1, hi = N;while (lo + 1 < hi) {int x = (lo + hi) / 2;int t1 = dp(K-1, x-1);int t2 = dp(K, N-x);if (t1 < t2)lo = x;else if (t1 > t2)hi = x;elselo = hi = x;}ans = 1 + Math.min(Math.max(dp(K-1, lo-1), dp(K, N-lo)),Math.max(dp(K-1, hi-1), dp(K, N-hi)));}memo.put(N * 100 + K, ans);}return memo.get(N * 100 + K);}
}链接：https://leetcode-cn.com/problems/super-egg-drop/solution/ji-dan-diao-luo-by-leetcode/