Skip to content

Commit e4394dd

Browse files
author
lucifer
committed
docs: 更新 README
1 parent 95e9dad commit e4394dd

File tree

2 files changed

+69
-47
lines changed

2 files changed

+69
-47
lines changed

README.md

Lines changed: 22 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -31,6 +31,23 @@
3131

3232
![](https://tva1.sinaimg.cn/large/007S8ZIlly1gdvenxvjlsj30z90dtdhw.jpg)
3333

34+
## 非科学人士看过来
35+
36+
如果是国内的非科学用户,可以使用 https://lucifer.ren/leetcode ,整站做了静态化,速度贼快!但是阅读体验可能一般,大家也可以访问[力扣加加](http://leetcode-solution.cn/)(暂时没有静态化)获得更好的阅读体验。
37+
38+
## 怎么刷 LeetCode?
39+
40+
- [我是如何刷 LeetCode 的](https://www.zhihu.com/question/280279208/answer/824585814)
41+
- [算法小白如何高效、快速刷 leetcode?](https://www.zhihu.com/question/321738058/answer/1279464192)
42+
43+
## 刷题插件(开发中)
44+
45+
- [刷题效率低?或许你就差这么一个插件](https://lucifer.ren/blog/2020/06/06/algo-chrome-extension/)
46+
47+
## 91 天学算法
48+
49+
- [91 天,遇见不一样的自己](https://lucifer.ren/blog/2020/05/23/91-algo/)
50+
3451
## 介绍
3552

3653
leetcode 题解,记录自己的 leetcode 解题之路。
@@ -311,12 +328,13 @@ leetcode 题解,记录自己的 leetcode 解题之路。
311328
- [《贪婪策略》专题](./thinkings/greedy.md)
312329
- [《深度优先遍历》专题](./thinkings/DFS.md)
313330
- [滑动窗口(思路 + 模板)](./thinkings/slide-window.md)
314-
- [位运算](./thinkings/bit.md) 🆕
331+
- [位运算](./thinkings/bit.md)
315332
- [设计题](./thinkings/design.md) 🆕
316-
- [小岛问题](./thinkings/island.md) 🆕
333+
- [小岛问题](./thinkings/island.md)
317334
- [最大公约数](./thinkings/GCD.md) 🆕
318335
- [并查集](./thinkings/union-find.md) 🆕
319336
- [前缀和](./thinkings/prefix.md) 🆕
337+
- [字典序列删除](https://lucifer.ren/blog/2020/06/13/%E5%88%A0%E9%99%A4%E9%97%AE%E9%A2%98/)🆕
320338

321339
### anki 卡片
322340

@@ -368,6 +386,8 @@ anki - 文件 - 导入 - 下拉格式选择“打包的 anki 集合”,然后
368386

369387
- 单调栈
370388

389+
- BFS & DFS
390+
371391
## 关注我
372392

373393
点关注,不迷路。如果再给 ➕ 个星标就更棒啦!

problems/887.super-egg-drop.md

Lines changed: 47 additions & 45 deletions
Original file line numberDiff line numberDiff line change
@@ -1,29 +1,29 @@
1-
21
## 题目地址
2+
33
https://leetcode.com/problems/super-egg-drop/description/
44

55
## 题目描述
66

77
```
8-
You are given K eggs, and you have access to a building with N floors from 1 to N.
8+
You are given K eggs, and you have access to a building with N floors from 1 to N.
99
1010
Each egg is identical in function, and if an egg breaks, you cannot drop it again.
1111
1212
You know that there exists a floor F with 0 <= F <= N such that any egg dropped at a floor higher than F will break, and any egg dropped at or below floor F will not break.
1313
14-
Each move, you may take an egg (if you have an unbroken one) and drop it from any floor X (with 1 <= X <= N).
14+
Each move, you may take an egg (if you have an unbroken one) and drop it from any floor X (with 1 <= X <= N).
1515
1616
Your goal is to know with certainty what the value of F is.
1717
1818
What is the minimum number of moves that you need to know with certainty what F is, regardless of the initial value of F?
1919
20-
20+
2121
2222
Example 1:
2323
2424
Input: K = 1, N = 2
2525
Output: 2
26-
Explanation:
26+
Explanation:
2727
Drop the egg from floor 1. If it breaks, we know with certainty that F = 0.
2828
Otherwise, drop the egg from floor 2. If it breaks, we know with certainty that F = 1.
2929
If it didn't break, then we know with certainty F = 2.
@@ -36,7 +36,7 @@ Example 3:
3636
3737
Input: K = 3, N = 14
3838
Output: 4
39-
39+
4040
4141
Note:
4242
@@ -52,82 +52,84 @@ Note:
5252

5353
## 思路
5454

55+
> 本题已经重制,重制版更清晰 [《丢鸡蛋问题》重制版来袭~](https://lucifer.ren/blog/2020/06/08/887.super-egg-drop/)
56+
5557
这是一道典型的动态规划题目,但是又和一般的动态规划不一样。
5658

5759
拿题目给的例子为例,两个鸡蛋,六层楼,我们最少扔几次?
5860

5961
![887.super-egg-drop-1](../assets/problems/887.super-egg-drop-1.png)
6062

61-
一个符合直觉的做法是,建立dp[i][j], 代表i个鸡蛋,j层楼最少扔几次,然后我们取dp[K][N]即可。
63+
一个符合直觉的做法是,建立 dp[i][j], 代表 i 个鸡蛋,j 层楼最少扔几次,然后我们取 dp[K][n]即可。
6264

6365
代码大概这样的:
6466

6567
```js
66-
const dp = Array(K + 1);
67-
dp[0] = Array(N + 1).fill(0);
68-
for (let i = 1; i < K + 1; i++) {
69-
dp[i] = [0];
70-
for (let j = 1; j < N + 1; j++) {
71-
// 只有一个鸡蛋
72-
if (i === 1) {
73-
dp[i][j] = j;
74-
continue;
75-
}
76-
// 只有一层楼
77-
if (j === 1) {
78-
dp[i][j] = 1;
79-
continue;
80-
}
81-
82-
// 每一层我们都模拟一遍
83-
const all = [];
84-
for (let k = 1; k < j + 1; k++) {
85-
const brokenCount = dp[i - 1][k - 1]; // 如果碎了
86-
const notBrokenCount = dp[i][j - k]; // 如果没碎
87-
all.push(Math.max(brokenCount, notBrokenCount)); // 最坏的可能
88-
}
89-
dp[i][j] = Math.min(...all) + 1; // 最坏的集合中我们取最好的情况
90-
}
68+
const dp = Array(K + 1);
69+
dp[0] = Array(N + 1).fill(0);
70+
for (let i = 1; i < K + 1; i++) {
71+
dp[i] = [0];
72+
for (let j = 1; j < N + 1; j++) {
73+
// 只有一个鸡蛋
74+
if (i === 1) {
75+
dp[i][j] = j;
76+
continue;
77+
}
78+
// 只有一层楼
79+
if (j === 1) {
80+
dp[i][j] = 1;
81+
continue;
9182
}
9283

93-
return dp[K][N];
84+
// 每一层我们都模拟一遍
85+
const all = [];
86+
for (let k = 1; k < j + 1; k++) {
87+
const brokenCount = dp[i - 1][k - 1]; // 如果碎了
88+
const notBrokenCount = dp[i][j - k]; // 如果没碎
89+
all.push(Math.max(brokenCount, notBrokenCount)); // 最坏的可能
90+
}
91+
dp[i][j] = Math.min(...all) + 1; // 最坏的集合中我们取最好的情况
92+
}
93+
}
94+
95+
return dp[K][N];
9496
```
9597

9698
果不其然,当我提交的时候,超时了。 这个的时复杂度是很高的,可以看到,我们内层暴力的求解所有可能,然后
97-
取最好的,这个过程非常耗时,大概是O(N^2 * K).
99+
取最好的,这个过程非常耗时,大概是 O(N^2 \* K).
98100

99-
然后我看了一位leetcode[网友](https://leetcode.com/lee215/)的回答,
101+
然后我看了一位 leetcode[网友](https://leetcode.com/lee215/)的回答,
100102
他的想法是`dp[M][K]means that, given K eggs and M moves,what is the maximum number of floor that we can check.`
101103

102104
我们按照他的思路重新建模:
103105

104106
![887.super-egg-drop-2](../assets/problems/887.super-egg-drop-2.png)
105107

106108
可以看到右下角的部分根本就不需要计算,从而节省很多时间
107-
## 关键点解析
108109

109-
- dp建模思路要发生变化, 即
110-
`dp[M][K]means that, given K eggs and M moves,what is the maximum number of floor that we can check.`
110+
## 关键点解析
111111

112+
- dp 建模思路要发生变化, 即
113+
`dp[M][K]means that, given K eggs and M moves,what is the maximum number of floor that we can check.`
112114

113115
## 代码
114116

115-
116117
```js
117118
/**
118119
* @param {number} K
119120
* @param {number} N
120121
* @return {number}
121122
*/
122-
var superEggDrop = function(K, N) {
123+
var superEggDrop = function (K, N) {
123124
// 不选择dp[K][M]的原因是dp[M][K]可以简化操作
124-
const dp = Array(N + 1).fill(0).map(_ => Array(K + 1).fill(0))
125-
125+
const dp = Array(N + 1)
126+
.fill(0)
127+
.map((_) => Array(K + 1).fill(0));
128+
126129
let m = 0;
127130
while (dp[m][K] < N) {
128-
m++;
129-
for (let k = 1; k <= K; ++k)
130-
dp[m][k] = dp[m - 1][k - 1] + 1 + dp[m - 1][k];
131+
m++;
132+
for (let k = 1; k <= K; ++k) dp[m][k] = dp[m - 1][k - 1] + 1 + dp[m - 1][k];
131133
}
132134
return m;
133135
};

0 commit comments

Comments
 (0)