Algorithm
lc678_有效的括号字符串
思路
直接递归，把左括号看做+1，然后有括号看做减一，*就遍历[1, 0, -1]中的一个值,如果有负数直接
返回false
写了一波贪心递归，但是超时了，主要和题解的差距在于，自己对于中间sum 大于 0的情况一直递归处理，导致超时
而题解直接容忍下大于0的状态，只处理最终的minCount == 0即可,妙啊
题解不止上面的贪心解法，还有动态规划和堆栈操作
代码
我的代码
79 / 83 个通过测试用例
TLE，超时了
"**************************************************))))))))))))))))))))))))))))))))))))))))))))))))))"
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
|
class Solution {
private:
bool m_string_valid;
void _checkValidString(int sum, int index, string& s) {
// 递归边界
if (sum < 0) {
return ;
}
if (index == s.size() - 1) {
if (s[index] == ')') {
m_string_valid = m_string_valid || sum == 1;
} else if (s[index] == '*') {
m_string_valid = m_string_valid || sum == 1 || sum == 0;
}
return ;
}
// 递归
if (s[index] == '(') {
_checkValidString(sum + 1, index + 1, s);
} else if (s[index] == ')') {
_checkValidString(sum - 1, index + 1, s);
} else if (s[index] == '*') {
_checkValidString(sum + 1, index + 1, s);
_checkValidString(sum, index + 1, s);
_checkValidString(sum - 1, index + 1, s);
}
}
public:
bool checkValidString(string s) {
m_string_valid = false;
_checkValidString(0, 0, s);
return m_string_valid;
}
};
|
题解代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
class Solution {
public:
bool checkValidString(string s) {
int minCount = 0, maxCount = 0;
int n = s.size();
for (int i = 0; i < n; i++) {
char c = s[i];
if (c == '(') {
minCount++;
maxCount++;
} else if (c == ')') {
minCount = max(minCount - 1, 0);
maxCount--;
if (maxCount < 0) {
return false;
}
} else {
minCount = max(minCount - 1, 0);
maxCount++;
}
}
return minCount == 0;
}
};
|
Review
【TED演讲】贫穷不是你的问题
缺乏某项资源的时候，将会无法更好获取这些资源
正如马太效应，富人有足够的本金进行投资变得更富有，而穷人只能不断努力生存，并且不断地被资本家剥削
而且视频中的研究表明，贫穷的时候的智商会比富有的时候降低14点，所以说
在资源受限的计算机上没法做大数据计算
因此，保障性收入应该成为一种权力，让大家都能吃得饱，穿的暖，有学上，能做自己喜欢做的事情
那样的世界才是美好的世界，是我们应该实现的世界
Tips
Git Stash如何帮助您处理多个分支
Share
MobaXterm下载注册使用
要点
- 下载便携版本
- 下载在线生成的注册码文件
- 注册码文件放到便携版本的exe下
- 注册码文件的命名不要修改，或者用的时候修改回生成时的名字
Custom.mxtpro