lc2182_构造限制重复的字符串 TED_关注自己心理健康 用微信读书读英文电子书 荐书_悉达多
Algorithm
lc2182_构造限制重复的字符串
思路:
先遍历获取cnt字符数组，然后从尾到头构造，每次到最大重复次数的时候吃一个下一个字符。
没有字符cnt的时候，就直接进行下一个字符的输出。
这个示例2是一个难点，一定要想清楚怎么处理结尾终止，否则很容易导致反复修改导致无法30分钟内写完。
汗，我就一开始没想清楚，导致中等简单题写了50分钟
通过每次遍历一遍 cnt 数组，数组中如果有字符大于 repeatLimit, 说明后续还得再进入 for 来判定。
非连续的部分直接一直遍历即可，不用计数。
再次进入时判断吃一个的逻辑和是否不用再重复的逻辑。
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
|
class Solution {
public:
string repeatLimitedString(string s, int repeatLimit) {
vector<int> cnt(27, 0);
for (auto c : s) {
cnt[c - 'a']++;
}
bool bigerLeft = true;
string ans;
while (bigerLeft) {
// assum bigerLeft false firstly
bigerLeft = false;
for (int i = 26; i >= 0; i--) {
if (!cnt[i]) {
continue;
}
// follow logic will eat char ok, so again `for`
// need to check back char is same or not.
if (!ans.empty() && ans.back() == 'a' + i) {
break;
}
if (bigerLeft) {
ans += 'a' + i;
cnt[i]--;
break;
}
if (cnt[i] > repeatLimit) {
// 这里大于的话，说明后续还要进入一次for循环
// 但是当前for需要继续下去 **1个字符**
ans += string(repeatLimit, 'a' + i);
cnt[i] -= repeatLimit;
bigerLeft = true;
} else {
ans += string(cnt[i], 'a' + i);
cnt[i] = 0;
}
}
}
return ans;
}
};
|
题解的双指针方式其实和我的思路差不多，我相当于是用循环代替了双指针，题解更具有通用性，建议学一下。
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
|
const int N = 26;
class Solution {
public:
string repeatLimitedString(string s, int repeatLimit) {
vector<int> count(N);
for (char c : s) {
count[c - 'a']++;
}
string ret;
int m = 0;
for (int i = N - 1, j = N - 2; i >= 0 && j >= 0;) {
if (count[i] == 0) { // 当前字符已经填完，填入后面的字符，重置 m
m = 0;
i--;
} else if (m < repeatLimit) { // 当前字符未超过限制
count[i]--;
ret.push_back('a' + i);
m++;
} else if (j >= i || count[j] == 0) { // 当前字符已经超过限制，查找可填入的其他字符
j--;
} else { // 当前字符已经超过限制，填入其他字符，并且重置 m
count[j]--;
ret.push_back('a' + j);
m = 0;
}
}
return ret;
}
};
|
Review
TED: 关注自己心理健康
- 像关注身体健康一样得关注心理健康
- 向前看，当经历心理痛苦的时候，去接纳并不再需要，向前看，千万不要回想"打翻的牛奶"，否则会让你抑郁，而是做专注其他事情
- 积极的心理暗示，相信自己一定能变得更好，而不是更加糟糕。相信自己很好。
Tips
用微信读书读英文电子书。
自己英文水平一般，直接读全英文的话，还是有些吃力的，然后最近把英文电子书导入微信读书阅读。
发现有自动的翻译，每一段都会翻译，这样就能先读英文，实在读不懂就能直接看翻译，不用每次都
复制粘贴到翻译工具，然后重新再理解一整个流程拖慢阅读速度了。
Share
推荐书本: 悉达多
