Involving knowledge points
Violence, single pointer
Collection of binary search algorithms
Title
You are given k identical eggs and access to a building with n floors from floor 1 to floor n.
It is known that there is a floor f, satisfying 0 <= f <= n. Any eggs dropped from a floor higher than f will break. Eggs dropped from floor f or a floor lower than it will not break.
For each operation, you can take an unbroken egg and drop it from any floor x (satisfying 1 <= x <= n). If the egg breaks, you can't use it again. If an egg does not break after being dropped, it can be reused in subsequent operations.
Please calculate and return the minimum number of operations required to determine the exact value of f?
Example 1:
Input: k = 1, n = 2
Output: 2
explain:
The egg falls from the 1st floor. If it breaks, we will definitely find f = 0 .
Otherwise, the egg falls from the 2nd floor. If it breaks, we will definitely find f = 1 .
If it doesn’t break, then f = 2 must be obtained.
So in the worst case we need to move 2 times to determine what f is.
Example 2:
Input: k = 2, n = 6
Output: 3
Example 3:
Input: k = 3, n = 14
Output: 4
Tip:
1 <= k <= 100
1 <= n <= 104
Violent solution
Analysis
f takes [0,n], a total of n + 1 possibilities, pre[i] represents i possible (j-1) eggs, how many rounds are needed to eliminate them
dp[i] represents i possibilities, how many rounds are needed to eliminate j eggs
If there is only one egg, test the lowest floor. If it is broken, you will get the answer; if it is not broken, you will rule out a possibility. When there is only one possibility, there is no need to try, so: when j is 0, dp[i]=i-1;
Suppose there are j (j>2) eggs, and if they are dropped on a certain floor, if they are not broken, there are x possibilities; if they are broken, there are i-x possibilities.
Then dp[i] = 1 + max(dp[x],pre[x-1]), x takes the value [1,i-1]
Stupid way to enumerate x.
Time complexity
Time complexity O(knn), timeout.
Code
class Solution {
public:
int superEggDrop(int k, int n) {
vector pre(n + 2);//f takes [0,n), a total of n + 1 possibilities, pre[i] represents i possibility, how many rounds of elimination are needed for j eggs
for (int i = 0; i <= n + 1; i + + )
{
pre[i] = i – 1;
}
for (int j = 1; j < k; j + + )
{
vector dp(n + 2,1000*100);
dp[1] = 0;
for (int i = 2; i <= n + 1; i + + )
{
for (int x = 1; x < i; x + + )
{
dp[i] = min(dp[i], 1 + max(dp[x], pre[i – x]));
}
}
pre.swap(dp);
}
return pre.back();
}
};
Two points
Analysis
Key considerations: max(dp[x], pre[i – x]));
Case 1: dp[x] <= pre[i-x]
x1 and x2 are legal x, and if x1
Case 2: dp[x] > pre[i-x]
Similarly: only the smallest x needs to be considered
The largest x in case one is xLeft, and the smallest x in case two is xRight, then xRightxLeft + 1
Therefore, only xRight is required. Note: xRight may not exist.
In the second case, if the conditions are met, if multiple conditions are met, the first one will be returned, and the left open and right closed space will be divided into two.
Time complexity
O(nklogn). The time complexity of enumerating the number of eggs is O(k), the time complexity of enumerating the possible numbers is O(n), and the time complexity of calculating xRight is O(logn).
Code
class Solution {<!-- -->
public:
int superEggDrop(int k, int n) {<!-- -->
vector<int> pre(n + 2);//f takes [0,n), a total of n + 1 possibilities, pre[i] represents i possibility, how many rounds of elimination are needed for j eggs
for (int i = 0; i <= n + 1; i + + )
{<!-- -->
pre[i] = i - 1;
}
for (int j = 1; j < k; j + + )
{<!-- -->
vector<int> dp(n + 2, 1000 * 100);
dp[0] = dp[1] = 0;
for (int i = 2; i <= n + 1; i + + )
{<!-- -->
int left = 0, right = i;
while (right - left > 1)
{<!-- -->
const auto mid = left + (right - left) / 2;
if (dp[mid] > pre[i - mid])
{<!-- -->
right = mid;
}
else
{<!-- -->
left = mid;
}
}
if (right < i )
{<!-- -->
auto x = right;
dp[i] = min(dp[i], 1 + max(dp[x], pre[i - x]));
}
if (right >= 2)
{<!-- -->
auto x = right-1;
dp[i] = min(dp[i], 1 + max(dp[x], pre[i - x]));
}
}
pre.swap(dp);
}
return pre.back();
}
};
Single pointer
As i increases, xRight will only increase or become larger. The time complexity of each j, xRight is O(n), and the total time complexity is O(kn).
Test cases
template
void Assert(const T & t1, const T & t2)
{
assert(t1 == t2);
}
template
void Assert(const vector & amp; v1, const vector & amp; v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i + + )
{
Assert(v1[i], v2[i]);
}
}
int main()
{
int res = 0;
{
res = Solution().superEggDrop(2, 6);
Assert(3, res);
}
{
res = Solution().superEggDrop(3, 14);
Assert(4, res);
}
{
res = Solution().superEggDrop(10, 100);
Assert(7, res);
}
{
res = Solution().superEggDrop(9, 89);
Assert(7, res);
}
{
res = Solution().superEggDrop(100, 10000);
Assert(14, res);
}
//CConsole::Out(res);
}
Edition January 7, 2023
class Solution {
public:
int superEggDrop(int k, int n) {
int iMaxStep = MaxStep(k,n);
vector preDp(iMaxStep + 1);
int iMinSetp = INT_MAX;
for (int i = 0; i <= iMaxStep; i + + )
{
preDp[i] = i + 1;
if (i + 1 -1 >= n)
{
iMinSetp = i;
}
}
while (–k)
{
vector dp(iMaxStep + 1);
dp[0] = 1;
for (int i = 1; i <= iMaxStep; i + + )
{
const int tmp = dp[i – 1] + preDp[i – 1];
dp[i] = tmp;
if (tmp > n)
{
iMinSetp = i;
break;
}
}
preDp.swap(dp);
}
return iMinSetp;
}
int MaxStep(int k, int n)const
{
int iOpeNum = 0;
int iCan = 1;//iOpeNum round can determine the Hu floor
for (int i = 2; i < 10000; i + + )
{
for (int j = 0; j < k; j + + )
{
if (iCan > n)
{
return iOpeNum;
}
iCan /= (i – 1);
iCan *= i;
iOpeNum + + ;
}
}
return 100;
}
};
Edition January 8, 2023
Enumerating each round, how many possibilities can be judged.
class Solution{
public:
int superEggDrop(int k, int n) {
//dp[j] represents the iStep round, the possibility that j eggs can represent
vector pre(k + 1,2);
pre[0] = 1;
if (2 > n)
{
return 1;
}
for (int iStep = 2; iStep < 20000; iStep + + )
{
vector dp(k + 1, 1);
for (int j = 1; j <= k; j + + )
{
dp[j] = pre[j] + pre[j – 1];
if (dp[j] > n)
{
return iStep;
}
}
pre.swap(dp);
}
return -1;
}
};
Extended reading
Video course
Effective learning: clear goals, timely feedback, stretching zone (appropriate difficulty), you can learn simple courses first, please go to CSDN Academy and listen to the explanation of Baiyin Lecturer (that is, I).
https://edu.csdn.net/course/detail/38771
how fast do you want
A battle has quickly formed. To share the worries of your boss, please learn C# onboarding training, C++ onboarding training and other courses.
https://edu.csdn.net/lecturer/6176
Related downloads
If you want to know the superior learning algorithm, please download the doc version of “Algorithm Book When You Hear the Defects”
https://download.csdn.net/download/he_zhidan/88348653
| What the Sa family wants to say to everyone |
|---|
| It is a good wish to be happy when you hear the flaws. Discover problems and correct them early to save your boss money. |
| The origin of the Mohist name: everything is recorded in Mohism. |
| If the program is a one-stop process, then the algorithm is its key point |
Test environment
Operating system: win7 Development environment: VS2019 C++ 17
Or operating system: win10 development environment:
VS2022 C++ 17
