Candy
按照规则给每个小孩发糖果
- 每个小孩的糖果数至少为 1
- 每个小孩获得的糖果数比他临近的, 并且权重比他小的小孩获得的要多
my solution(12ms, 100.00%)
虽然做出来了, 但是并不高兴 = =, 因为代码太过复杂
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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
| const static int _ = [] () {
ios::sync_with_stdio(false);
cin.tie(nullptr);
return 0;
} ();
class Solution {
public:
int candy(vector<int>& ratings) {
size_t size = ratings.size();
if (!size) return 0;
if (size == 1) return 1;
vector<int> candys(size, 0);
if (ratings[0] <= ratings[1])
candys[0] = 1;
if (ratings[size - 1] <= ratings[size - 2])
candys[size - 1] = 1;
for (int i = 1; i + 1 < size; ++i) {
int minn = min(ratings[i], ratings[i - 1]);
minn = min(minn, ratings[i + 1]);
if (ratings[i] == minn)
candys[i] = 1;
}
if (ratings[0] > ratings[1] && candys[1])
candys[0] = candys[1] + 1;
if (ratings[size - 1] > ratings[size - 2] && candys[size - 2])
candys[size - 1] = candys[size - 2] + 1;
for (int i = 1; i + 1 < size; ++i) {
if (candys[i] == 0) {
int minn, maxn;
if (ratings[i + 1] == ratings[i - 1]) {
if (candys[i + 1] && candys[i - 1])
candys[i] = max(candys[i + 1], candys[i - 1]) + 1;
continue;
}
else if (ratings[i + 1] > ratings[i - 1]) {
minn = i - 1;
maxn = i + 1;
}
else {
minn = i + 1;
maxn = i - 1;
}
if (ratings[i] <= ratings[maxn] && candys[minn])
candys[i] = candys[minn] + 1;
if (ratings[i] > ratings[maxn] && candys[maxn] && candys[minn])
candys[i] = max(candys[maxn], candys[minn]) + 1;
}
}
for (int i = size - 2; i >= 1; --i) {
if (candys[i] == 0) {
int minn, maxn;
if (ratings[i + 1] == ratings[i - 1]) {
if (candys[i + 1] && candys[i - 1])
candys[i] = max(candys[i + 1], candys[i - 1]) + 1;
continue;
}
else if (ratings[i + 1] > ratings[i - 1]) {
minn = i - 1;
maxn = i + 1;
}
else {
minn = i + 1;
maxn = i - 1;
}
if (ratings[i] <= ratings[maxn] && candys[minn])
candys[i] = candys[minn] + 1;
if (ratings[i] > ratings[maxn] && candys[maxn] && candys[minn])
candys[i] = max(candys[maxn], candys[minn]) + 1;
}
}
if (ratings[0] > ratings[1] && candys[1])
candys[0] = candys[1] + 1;
if (ratings[size - 1] > ratings[size - 2] && candys[size - 2])
candys[size - 1] = candys[size - 2] + 1;
int ret = 0;
for (int i = 0; i < size; ++i)
ret += candys[i];
return ret;
}
private:
};
|
整体代码会有 3 次遍历, 但是代码太多, 太复杂了…
如果没有看到最好算法的简洁程度, 我可能还能再高兴一下…
best solution
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
| class Solution {
public:
int candy(vector<int>& ratings) {
vector<int> num(ratings.size(), 1);
for (int i = 1; i < ratings.size(); ++i) {
if (ratings[i] > ratings[i-1]) {
num[i] = num[i-1] + 1;
}
}
for (int i = ratings.size() - 2; i >= 0; --i) {
if (ratings[i] > ratings[i+1] && num[i] <= num[i+1]) {
num[i] = num[i+1] + 1;
}
}
int sum = 0;
for (int i = 0; i < num.size(); ++i) {
sum += num[i];
}
return sum;
}
};
static int x = []() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
return 0;
}();
|
(做完题的喜悦被冲刷得干干净净…, 啊… 真的是羞愧难当啊…)
(我为什么总是把问题复杂化了呢…)
逻辑上大致相同, 只不过他只需要一次 反向遍历, 一次 正向遍历
其中每次遍历所需要判断的条件都十分简单并且清晰