福州仿站定制模板建站,wordpress login 插件,wordpress报名收费,wordpress连不上mysql8涉及知识点
暴力、二分查找算法、单指针
题目
给你 k 枚相同的鸡蛋#xff0c;并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。 已知存在楼层 f #xff0c;满足 0 f n #xff0c;任何从 高于 f 的楼层落下的鸡蛋都会碎#xff0c;从 f 楼层或比它低的…涉及知识点
暴力、二分查找算法、单指针
题目
给你 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]共n1可能 pre[i]表示i种可能 (j-1)个鸡蛋需要多少回合排除 dp[i]表示i种可能j个鸡蛋 需要多少回合排除 只有一个鸡蛋则测试最低的的楼层如果破了就得到答案没破就排除一种可能。当只一种可能时不需要尝试故j为0时dp[i]i-1; 假设有j(j2)个鸡蛋假设在某层楼扔下如果没破有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)共n1可能 pre[i]表示i种可能 j个鸡蛋需要多少回合排除 for (int i 0; i n1; 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 n1; 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且x1x2如则x1被淘汰 证明因为pre和dp都是单调增加或不变 。 x1x2 i-x1 i-x2 pre[i-x1]pre[i-x2] 情况二dp[x] pre[i-x] 同理只需要考虑最小的x 情况一最大的x是xLeft,情况二最小的x是xRight则xRightxLeft1 故只需求xRight注意:xRight可能不存在 情况二符合条件多个符合条件返回第一个用左开右闭空间二分。
时间复杂度
O(nklogn)。枚举鸡蛋数时间复杂度O(k)枚举可能数时间复杂度O(n)计算xRight时间复杂度O(logn)。
代码
class Solution {
public:int superEggDrop(int k, int n) {vectorint pre(n 2);//f 取[0,n)共n1可能 pre[i]表示i种可能 j个鸡蛋需要多少回合排除for (int i 0; i n 1; i){pre[i] i - 1;}for (int j 1; j k; j){vectorint 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] i1; 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 C17 或者 操作系统win10 开发环境
VS2022 C17
