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

2023-11-11 07:44

本文主要是介绍一题三解(暴力、二分查找算法、单指针):鸡蛋掉落,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

涉及知识点

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

题目

给你 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,则xRight
xLeft+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只会增加或变大。每个j,xRight的时间复杂度是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

这篇关于一题三解(暴力、二分查找算法、单指针):鸡蛋掉落的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/388569

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

hdu2289(简单二分)

虽说是简单二分,但是我还是wa死了  题意:已知圆台的体积,求高度 首先要知道圆台体积怎么求:设上下底的半径分别为r1,r2,高为h,V = PI*(r1*r1+r1*r2+r2*r2)*h/3 然后以h进行二分 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#includ

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费

dp算法练习题【8】

不同二叉搜索树 96. 不同的二叉搜索树 给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。 示例 1: 输入:n = 3输出:5 示例 2: 输入:n = 1输出:1 class Solution {public int numTrees(int n) {int[] dp = new int