一题三解(暴力、二分查找算法、单指针):鸡蛋掉落-CSDN博客

涉及知识点

暴力、二分查找算法、单指针

题目

给你 k 枚相同的鸡蛋并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。
已知存在楼层 f 满足 0 <= f <= n 任何从 高于 f 的楼层落下的鸡蛋都会碎从 f 楼层或比它低的楼层落下的鸡蛋都不会破。
每次操作你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下满足 1 <= x <= n。如果鸡蛋碎了你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎则可以在之后的操作中 重复使用 这枚鸡蛋。
请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少
示例 1
输入k = 1, n = 2
输出2
解释
鸡蛋从 1 楼掉落。如果它碎了肯定能得出 f = 0 。
否则鸡蛋从 2 楼掉落。如果它碎了肯定能得出 f = 1 。
如果它没碎那么肯定能得出 f = 2 。
因此在最坏的情况下我们需要移动 2 次以确定 f 是多少。
示例 2
输入k = 2, n = 6
输出3
示例 3
输入k = 3, n = 14
输出4
提示
1 <= k <= 100
1 <= n <= 104

暴力解法

分析

f 取[0,n]共n+1可能 pre[i]表示i种可能 (j-1)个鸡蛋需要多少回合排除
dp[i]表示i种可能j个鸡蛋 需要多少回合排除
只有一个鸡蛋则测试最低的的楼层如果破了就得到答案没破就排除一种可能。当只一种可能时不需要尝试故j为0时dp[i]=i-1;
假设有j(j>2)个鸡蛋假设在某层楼扔下如果没破有x种可能破了有i-x种可能。
则dp[i] = 1 + max(dp[x],pre[x-1])x取值[1,i-1]
笨办法枚举x。

时间复杂度

时间复杂度O(knn),超时。

代码

class Solution {
public:
int superEggDrop(int k, int n) {
vector pre(n + 2);//f 取[0,n)共n+1可能 pre[i]表示i种可能 j个鸡蛋需要多少回合排除
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();
}
};

二分

分析

重点考虑max(dp[x], pre[i - x]));
情况一dp[x] <= pre[i-x]
x1和x2是合法x且x1<x2如则x1被淘汰
证明因为pre和dp都是单调增加或不变 。 x1<x2 > i-x1 > i-x2 =>pre[i-x1]>=pre[i-x2]
情况二dp[x] > pre[i-x]
同理只需要考虑最小的x
情况一最大的x是xLeft,情况二最小的x是xRight则xRightxLeft+1
故只需求xRight注意:xRight可能不存在
情况二符合条件多个符合条件返回第一个用左开右闭空间二分。

时间复杂度

O(nklogn)。枚举鸡蛋数时间复杂度O(k)枚举可能数时间复杂度O(n)计算xRight时间复杂度O(logn)。

代码

class Solution {
public:
	int superEggDrop(int k, int n) {
		vector<int> pre(n + 2);//f 取[0,n)共n+1可能 pre[i]表示i种可能 j个鸡蛋需要多少回合排除
		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();
	}
};

单指针

随着i的增加xRight只会增加或变大。每个jxRight的时间复杂度是O(n)总时间复杂度是O(kn)。

测试用例

template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}

template
void Assert(const vector& v1, const vector& 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);

}

2023年1月7号版

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回合可以判定胡楼层
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;
}
};

2023年1月8号版

枚举各回合能判断多少种可能。
class Solution{
public:
int superEggDrop(int k, int n) {
//dp[j] 表示iStep回合j个鸡蛋能表示的可能
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;
}

};

扩展阅读

视频课程

有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了为老板分忧请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法请下载《闻缺陷则喜算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

洒家想对大家说的话
闻缺陷则喜是一个美好的愿望早发现问题早修改问题给老板节约钱。
墨家名称的来源有所得以墨记之。
如果程序是一条龙那算法就是他的是睛

测试环境

操作系统win7 开发环境 VS2019 C++17
或者 操作系统win10 开发环境

VS2022 C++17