阿秀的学习笔记

这是六则或许对你有些许帮助的信息:

1、阿秀在工作之余开发了一个编程资源网站，目前已经收集了很多不错的学习资源和黑科技（附带下载地址），如你有意欢迎体验以及推荐自己认为不错的资源，众人拾柴火焰高，我为人人，人人为我🔥！

2、👉23年5月份我从字节跳动离职跳槽到某外企期间，为方便自己找工作，增加上岸几率，我自己从0开发了一个互联网中大厂面试真题解析网站，包括两个前端和一个后端。能够定向查看某些公司的某些岗位面试真题，比如我想查一下行业为互联网，公司为字节跳动，考察岗位为后端，考察时间为最近一年之类的面试题有哪些？

网站地址：InterviewGuide大厂面试真题解析网站。点此可以查看该网站的视频介绍：B站视频讲解 如果可以的话求个B站三连，感谢！

3、😊 分享一个学弟发给我的20T网盘资源合集，点此白嫖，主要是各类高清影视、电视剧、音乐、副业、纪录片、英语四六级考试、考研考公等资源。

4、😍免费分享阿秀个人学习计算机以来收集到的免费学习资源，点此白嫖；也记录一下自己以前买过的不错的计算机书籍、网络专栏和垃圾付费专栏；也记录一下自己以前买过的不错的计算机书籍、网络专栏和垃圾付费专栏

5、🚀如果你想在校招中顺利拿到更好的offer，阿秀建议你多看看前人踩过的坑和留下的经验，事实上你现在遇到的大多数问题你的学长学姐师兄师姐基本都已经遇到过了。

6、🔥 欢迎准备计算机校招的小伙伴加入我的学习圈子，一个人踽踽独行不如一群人报团取暖，圈子里沉淀了很多过去21/22/23届学长学姐的经验和总结，好好跟着走下去的，最后基本都可以拿到不错的offer！此外，每周都会进行精华总结和分享！如果你需要《阿秀的学习笔记》网站中📚︎校招八股文相关知识点的PDF版本的话，可以点此下载 。

# 887. 鸡蛋掉落 谷歌微软经典题目

力扣原题链接（点我直达） (opens new window)

你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N 共有 N 层楼的建筑。

每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。

你知道存在楼层 F ，满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。

每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。

你的目标是确切地知道 F 的值是多少。

无论 F 的初始值如何，你确定 F 的值的最小移动次数是多少？

示例 1：

输入：K = 1, N = 2
输出：2
解释：
鸡蛋从 1 楼掉落。如果它碎了，我们肯定知道 F = 0 。
否则，鸡蛋从 2 楼掉落。如果它碎了，我们肯定知道 F = 1 。
如果它没碎，那么我们肯定知道 F = 2 。
因此，在最坏的情况下我们需要移动 2 次以确定 F 是多少。
1
2
3
4
5
6
7

示例 2：

输入：K = 2, N = 6
输出：3
1
2

示例 3：

输入：K = 3, N = 14
输出：4
1
2

提示：

  1. 1 <= K <= 100
  2. 1 <= N <= 10000

# 第0版 最好懂，可是会超时

int superEggDrop(int K, int N)
{
	if (N == 0 || N == 1 || K == 1) {
		return N;
	}

	int minNum = N;
	for (int i = 1; i <= N; i++) {
		int tMin = max(superEggDrop(K - 1, i - 1), superEggDrop(K, N - i));
		minNum = min(minNum, 1 + tMin);
	}
	return minNum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

# 第一版，公众号解析

https://mp.weixin.qq.com/s/7PEBnUfIpiuw26lVeihlhA

# 第二版，换个思路解题

执行用时 :8 ms, 在所有 cpp 提交中击败了68.65%的用户

内存消耗 :8.3 MB, 在所有 cpp 提交中击败了93.34%的用户

从多少楼层多少个蛋最少要扔几次，转变为有多少个蛋扔几次可以测试出多少楼层。

执行用时 :8 ms, 在所有 cpp 提交中击败了68.65%的用户

内存消耗 :8.1 MB, 在所有 cpp 提交中击败了97.84%的用户

int help(int i, int K) {
	return (i == 1 || K == 1) ? i : help(i - 1, K - 1) + help(i - 1, K) + 1;
}


int superEggDrop(int K, int N) {
	int count = 1;
	while (help(count, K) < N) {
		count++;
	}
	return count;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

# 第二版的第二种解释

上面的方法的思路，都还是顺着题目的思路的进行的，其实我们可以换一个思路来想：“求k个鸡蛋在m步内可以测出多少层”。我们令dp [k] [m]表示k个鸡蛋在m步内可以测出的最多的层数，那么当我们在第X层扔鸡蛋的时候，就有两种情况：

鸡蛋碎了，我们少了一颗鸡蛋，也用掉了一步，此时测出N - X + dp [k-1] [m-1]层，X和它上面的N-X层已经通过这次扔鸡蛋确定大于F； 鸡蛋没碎，鸡蛋的数量没有变，但是用掉了一步，剩余X + dp [k] [m-1]，X层及其以下已经通过这次扔鸡蛋确定不会大于F； 也就是说，我们每一次扔鸡蛋，不仅仅确定了下一次扔鸡蛋的楼层的方向，也确定了另一半楼层与F的大小关系，所以在下面的关键代码中，使用的不再是max，而是加法（这里是重点）。评论里有人问到为什么是相加，其实这里有一个惯性思维的误区，上面的诸多解法中，往往求max的思路是“两种方式中较大的那一个结果”，其实这里的相加，不是鸡蛋碎了和没碎两种情况的相加，而是“本次扔之后可能测出来的层数 + 本次扔之前已经测出来的层数”。

假设我们有 k 个鸡蛋可以移动 m 步，考虑某一步 t 应该在哪一层丢鸡蛋？一个正确的选择是在 dp [k-1] [t-1] + 1 层丢鸡蛋，结果分两种情况：

  1. 如果鸡蛋碎了，我们首先排除了该层以上的所有楼层（不管这个楼有多高），而对于剩下的 dp [k-1] [t-1] 层楼，我们一定能用 k-1 个鸡蛋在 t-1 步内求解。因此这种情况下，我们总共可以求解无限高的楼层。可见，这是一种非常好的情况，但并不总是发生。
  2. 如果鸡蛋没碎，我们首先排除了该层以下的 dp [k-1] [t-1] 层楼，此时我们还有 k 个蛋和 t-1 步，那么我们去该层以上的楼层继续测得 dp [k] [t-1] 层楼。因此这种情况下，我们总共可以求解 dp [k-1] [t-1] + dp [k] [t-1] + 1 层楼。

容易想象，在所有 m 步中只要有一次出现了第一种情况，那么我们就可以求解无限高的楼层。但“保证求解”的定义要求我们排除一切运气成分，因此我们只得认为每次移动都遇到第二种情况。于是得到递推公式：

dp [k ] [t] = dp [k-1] [t-1] + dp [k] [t-1] + 1

执行用时 :8 ms, 在所有 cpp 提交中击败了68.65%的用户

内存消耗 :31.8 MB, 在所有 cpp 提交中击败了25.89%的用户

int superEggDrop(int K, int N)
{
	vector<vector<int>>  dp(K + 1,vector<int>(N + 1,0));
	//当N=0时，K等于多少都是0，或者当K=1时，只能有K种解法了
	//dp[0][m] = 0; // zero egg
	for (int n = 1; n <= N; n++) {
		for (int k = 1; k <= K; k++) {
			dp[k][n] = dp[k][n - 1] + dp[k - 1][n - 1] + 1;
			if (dp[k][n] >= N) {
				return n;
			}
		}
	}
	return N;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1

← 目录 →