ARST打卡第123周[123/521]

发表于 分类于 阅读次数：
lc678_有效的括号字符串 【TED演讲】贫穷不是你的问题 Git Stash如何帮助您处理多个分支 MobaXterm下载注册使用

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