双蛋问题 (The Two Egg Problem) || 鹰蛋问题

问题问题

100层楼,底层扔鸡蛋不会碎，高层扔鸡蛋会碎，有M个蛋，最少扔多少次可以找到临界层？
最坏情况下

• 1.一个鸡蛋的时候 从 1楼开始扔，最坏情况 100 次
• 2.无数个鸡蛋时，二分法，50 25 12 6 3 2 1，最坏情况 7 次
• 3.两个鸡蛋时，10 20 30 40 50 60 70 80 90 100 最坏情况 10 + 9 次
• 4.两个鸡蛋时，k k-1,k-2,k-3—-1, (k + 1) * k / 2>=100,k = 14,
  14 27 39 50 60 69 77 84 90 95 99 100 最坏情况 14 次
• 5.f(i,j) i 代表鸡蛋个数,j代表楼层
  f(i,j)=min(max(f(i,f-1) + 1,f(i-1,j-f)+1)) i<=f<=j
  根据函数使k,n规划可计算出结果 k—-

fMedian 的计算二分查找

• 1.T1 = dp[i - 1][f - 1] 是单调递增函数
• 2.T2 = dp[i][j - f] 是单调递减函数
• 3.max(dp[i - 1][f - 1],dp[i][j - f]),就是两个函数的交点
• 4.交点可能是浮点数，如果是整数，fmin=fmax=fmedian 如果是浮点数，离散化，求出交点位置的左右点

特征

摆动排序

摆动排序一

描述

给你一个没有排序的数组，请将原数组就地重新排列满足如下性质
nums[0] <= nums[1] >= nums[2] <= nums[3]….

分析

先对数组进行排序，然后依次把两两相邻的元素进行交换，最终成为一个波动递增的数列，满足题目要求

1 2 3 4 5 6 7 8 9
1 3 2 5 4 7 6 9 8

最大化最小值问题

描述

有一类常见问题叫做最小值最大化或者最大值最小化。这类问题一般是用二分搜索来解决。

　　首先二分搜索解决的问题必须具备单调性这个性质，这是使用二分搜索的必要条件，我们分析两个问题。

　　1.最小值最大化：我们假设x为最大的最小值，那么x-1是满足条件的，但他并不满足最大，x+1是不满足条件的，假设我们左边界是L,右边界是R，我们二分一个答案ans，ans为最后一个满足条件的数，我们是不是可以类比二分搜索（一）中的last_less_equal()或者last_less()这个问题和这两者是差不多的。

　　2.最大值最小化：我们假设x为最小的最大值，那么x-1是不满足条件的，x+1是满足条件的，但他不满足最小，假设我们左边界是L,右边界是R，我们二分一个答案ans，ans为第一个满足条件的数，我们是不是可以类比二分搜索（一）中的lower_bound()或者upper_bound()这个问题和这两者是差不多的。

　　所以综上所述并根据我在二分搜索（一）——各种二分中的描述：最小值最大化的二分区间是右闭左开(L,R]，每次二分的中心为M=(L+R+1)/2；最大值最小化的二分区间是左闭右开，[L,R),每次二分的中心为M=(L+R)/2。

相关题目

两个有序数组的第K小元素问题

问题描述

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的第K小的元素，并且要求算法的时间复杂度为 O(log(m + n))。

归并法

思路分析

将两个有序数组归并为一个有序数组

RMQ问题

RMQ (Range Minimum/Maximum Query)问题是指：对于长度为n的数列A，回答若干询问RMQ(A,i,j)(i,j<=n)，返回数列A中下标在i,j里的最小(大）值，也就是说，RMQ问题是指求区间最值的问题。

线段树

ST算法

矩形

矩形

1.扫描线算法
2.线段树
3.矩形切割算法
4.坐标压缩
5.二维线段树
6.矩形树
7.树状数组
8.空间压缩

矩形面积一

描述

链接

在二维平面上计算出两个由直线构成的矩形重叠后形成的总面积。

问题描述

有n种硬币，面值分别为 V1,V2,…,Vn。每种都有无限多。给定非负整数S，问可以选用多少个硬币，使得面值之和恰好为S？输出硬币数目的最小值

贪心算法

贪心算法的解不一定是最优解
但是贪心算法的解有用途，可以作为DFS的剪枝条件,搜索过程中解大于贪心算法的解时break
参考DFS实现

动态规划

公式
dp[i] = Math.min(dp[i], dp[i - coin] + 1)
动态规划实现

DFS

当 amount==0amount==0 时剪枝，因为大面值硬币需要更多小面值硬币替换，继续减少一枚或几枚大硬币搜索出来的答案【如果有】肯定不会更优。
当 amount!=0，但已经使用的硬币数 cnt 满足了 cnt+1>=ans 时剪枝，因 amount 不为 0，至少还要使用 1 枚硬币，则继续搜索得到的答案不会更优。是 break 不是 continue，因为少用几枚面值大的硬币搜索出的方案【如果有】肯定需要更多枚面值小的硬币来替换掉这枚大的硬币【同剪枝 1 理由】，而使用这几枚大的硬币都搜索不到更好的解，故应该是 break。
使用贪心算法先算出一个解，作为剪枝条件
DFS实现

参考

leetcode题目
题解