20200419

Plan

leetcode 每日一题 20~22

Notes

最近一周工作比较忙，每天没什么时间刷题，趁着周日多刷几道。 今天刷了三道20，21，22.前两道都比较简单，不在记录。记录一下22题，有一个思维误区，导致一开始就想错了。 题目： 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例：

输入：n = 3 输出：[ "((()))", "(()())", "(())()", "()(())", "()()()" ]

刚开始看到这道题想到了是用回溯法，但是思路是这样的：设长度为n的字符串集合为a，长度为n-1的字符串集合为b，则a是由以下三种情况生成的： 1."("+b+")" 2."()"+b 3.b+"()" b的所有字符串加这三种情况，去重后就是a。 看上去没什么问题，验证了n=1,2,3的时候都是符合要求的，但是其实n=4的时候已经会出现遗漏。比如下面这种情况： (())(()),它不由任意一个n=3的字符串加上面三种情况生成。 正确解法： 对每一个位置，插入"("或者")"。如果插入左括号，只要左括号没有插入完，就可以插入；如果插入右括号，当前剩余右括号的数量必须大于左括号，否则就不是有效的括号组合。用这种思路，传入两个变量Left，right分别记录当前左右括号的剩余，以及初始化传入一个空字符串，还有记录最终结果的字符串数组即可。

More

今天学到了两点： 1.一定要多思考当前思路是否正确，否则会浪费很多时间。 2.go中数组/切片传入函数时是形参，如果想要改变数组/切片的值，需要传入指针；map传入函数时是实参，在函数中对map修改会直接修改原始的map。