0%

ARST打卡第123周[123/521]

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下载注册使用

要点

  1. 下载便携版本
  2. 下载在线生成的注册码文件
  3. 注册码文件放到便携版本的exe下
  4. 注册码文件的命名不要修改,或者用的时候修改回生成时的名字Custom.mxtpro