vivo提前批(6.7)
1.种花
现有一块长方形的地种植花草，因受到阳光水分等因素的影响，相邻的区域不能种植，假如用一个数列表示土地上的种植情况，0表示未种植，1表示种植，问不影响原有花草的情况下，最多可以种花草的数量是多少? LeetCode605
输入： 第一行一个数字，表示土地的长度n。第二行n个0 1组成的数列。
输出：最大可种植的数量
思路：如果当前位置未种植且前一个位置未种植且后一个位置未种植，则当前位置可以种植。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
while (cin >> n) {
vector<int> nums(n);
for (int i = 0; i < n; i++) cin >> nums[i];
int idx = 0, cnt = 0;
while (idx < nums.size()) {
// 判断当前位置是否可以种植
if (nums[idx] == 0 && (idx == 0 || nums[idx - 1] == 0) &&
(idx == nums.size() - 1 || nums[idx + 1] == 0)) {
nums[idx] = 1;
cnt++;
}
idx++;
}
cout << cnt << endl;
}
return 0;
}
2.高楼扔手机(高楼扔鸡蛋，高楼仍碗)
你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N 共有 N 层楼的建筑。每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。 你知道存在楼层 F ，满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。你的目标是确切地知道 F 的值是多少。无论 F 的初始值如何，你确定 F 的值的最小移动次数是多少？
思路：dp[k][m] 表示用 k 个鸡蛋移动 m 步可以“保证求解”的最大楼层数。所谓“求解”，意思就是给定楼层 N，我们能否找到临界楼层 F(F <= N)，使得鸡蛋从 F 层掉落刚好不会被摔碎。所谓“保证求解”，意思就是即使每次丢鸡蛋的结果都很差，最终仍能求解。比如，给定 1 个鸡蛋移动 1 步，那么可以求解的最大楼层数为 1，即从 1 楼丢下，如果鸡蛋碎了，求得 F=0，如果鸡蛋没碎，求得 F=1。在这种情况下，假如我们给出一个 2 层的楼，就无法保证求解了，因为无论从哪一层丢出鸡蛋，都没有十足的把握能够一次求得 F，换句话说，虽然我们仍有一定的机会能够求解，但无法“保证求解”。
下面回到正题：
假设我们有 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
基本的问题已经解决了，但是我们还遗留了一个问题：为什么要选择在 dp[k-1][t-1] + 1 层丢鸡蛋？
现在我们已经知道，如果我们每一步都在 dp[k-1][t-1] + 1 层丢鸡蛋，最终是一定能够求解的。但如果我们选择在更低的层或者更高的层丢鸡蛋会怎样呢？我们分两种情况讨论：
1. 在更低的楼层丢鸡蛋。同样能够“保证求解”，但最终得到的并不是“最大”楼层数，我们没有充分挖掘鸡蛋数和移动次数的潜力，最终求解时会剩余一定量的鸡蛋或移动次数。
2. 在更高的楼层丢鸡蛋。不妨假设高了一层，即在第 dp[k-1][t-1] + 2 层丢鸡蛋。如果鸡蛋碎掉了，我们仍然可以排除该层以上的所有楼层（不管这个楼有多高），但接下来就不好办了，因为我们剩下的 k-1 个鸡蛋在 t-1 步内只能“保证求解” dp[k-1][t-1] 的楼层，而现在剩余的楼层却是 dp[k-1][t-1] + 1，多了一层，因此无法“保证求解”！综上，我们用排除法证明了每一步都应该在第 dp[k-1][t-1] + 1 层丢鸡蛋。
输入：鸡蛋个数k，楼层n。
输出：最少多少次
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>
using namespace std;
int main() {
int k, n;
while (cin >> k >> n) {
vector<vector<int>> dp(k + 1, vector<int>(n + 1));
for (int i = 1; i <= n; i++) dp[1][i] = i; // base case
for (int i = 2; i <= k; i++) { // 枚举鸡蛋
for (int j = 1; j <= n; j++) { // 枚举楼层
int minV = INT_MAX;
for (int m = 1; m <= j; m++) { // 选择从哪个楼层扔
// 状态更新
minV = min(minV, max(dp[i - 1][m - 1], dp[i][j - m]) + 1);
}
dp[i][j] = minV;
}
}
cout << dp[k][n] << endl;
}
}
/**
* 时间复杂度:O(KN^2)
* 状态表示：dp[i][j]表示有i个鸡蛋，面对j层楼测出F的最少次数
* 状态计算：如果我在m层仍(1<m<j)，有两种情况，碎了，i-1即鸡蛋少一个，楼层区间变为1~m-1，如果没碎，i不变，楼层区间变为j-m
*/
int superEggDrop(int k, int n) {
vector<vector<int>> dp(k + 1, vector<int>(n + 1));
for (int i = 1; i <= n; i++) dp[1][i] = i; // base case
for (int i = 2; i <= k; i++) { // 枚举鸡蛋
for (int j = 1; j <= n; j++) { // 枚举楼层
int minV = INT_MAX;
for (int m = 1; m <= j; m++) { // 选择从哪个楼层扔
// 状态更新
minV = min(minV, max(dp[i - 1][m - 1], dp[i][j - m]) + 1);
}
dp[i][j] = minV;
}
}
return dp[k][n];
}
/**
* 时间复杂度：O(KN)
* 空间复杂度：O(KN)
* 状态表示：dp[i][j]表示用i个鸡蛋和允许j次移动可以“保证求解”的最大楼层。
* 状态计算：参考解析思路
*/
int superEggDrop(int k, int n) {
vector<vector<int>> dp(k + 1, vector<int>(n + 1));
for (int i = 1; i <= n; i++) {
dp[0][i] = 0;
for (int j = 1; j <= k; j++) {
dp[j][i] = dp[j][i - 1] + dp[j - 1][i - 1] + 1;
if (dp[j][i] >= n) return i;
}
}
return n;
// 空间优化
vector<int> dp(k + 1, 1);
int m = 2;
dp[0] = 0;
while (dp[k] < n) {
for (int i = k; i >= 1; i--) {
dp[i] = dp[i] + dp[i - 1] + 1;
}
m++;
}
return m - 1;
}
3.合并k个有序链表
合并k个有序链表。LeetCode23
输入：第一行输入n，表示n个链表，接下来n行，每一行都是一个链表。
输出：合并后的链表
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
vector<int> split(string s) {
s += ' ';
vector<int> res;
int pos = s.find(' ');
while (pos != s.npos) {
res.push_back(stoi(s.substr(0, pos)));
s = s.substr(pos + 1);
pos = s.find(' ');
}
return res;
}
ListNode* mergeLists(vector<ListNode*>& lists) {
auto dummy = new ListNode(-1);
auto p = dummy;
while (true) {
int minV = INT_MAX;
bool flag = true;
int idx = 0;
for (int i = 0; i < lists.size(); i++) {
if (lists[i] && lists[i]->val < minV) {
minV = lists[i]->val;
idx = i;
flag = false;
}
}
if (flag) break;
p->next = lists[idx];
lists[idx] = lists[idx]->next;
p = p->next;
}
return dummy->next;
}
int main() {
int n;
cin >> n;
cin.ignore();
vector<ListNode*> lists;
for (int i = 0; i < n; i++) {
auto dummy = new ListNode(-1);
auto p = dummy;
int t;
while (cin >> t) {
p->next = new ListNode(t);
p = p->next;
if (cin.get() == '\n') break; // 注意这儿的读取结束的条件
}
// string s;
// getline(cin, s);
// vector<int> tmp = split(s);
// for (auto t : tmp) {
// p->next = new ListNode(t);
// p = p->next;
// }
lists.push_back(dummy->next);
}
auto res = mergeLists(lists);
while (res) {
cout << res->val << ' ';
res = res->next;
}
cout << endl;
return 0;
}
