22. 括号生成
题解: dfs.
1. dfs(string str, int i): str表示 前 i-1 个 括号组成的合法括号, i 表示 现在要插入第 i 个小括号 "()", 这里不需要 考虑插入的小括号里面还有小括号,因为这样的操作会在 i+1, i+2, ... 中去尝试.
2. 对于一个合法的括号组合,我们可以在字符串头部, 以及每个左括号的后面添加一个小括号 "()".
3. 结果可能会有重复, 需要去重.
vector<string> generateParenthesis(int n) {
set<string> _set;
function<void(string, int)> dfs = [&](string brackets, int level){
if(!level){
_set.insert(brackets);
return;
}
dfs("()" + brackets, level - 1);
for(int i=0; i<brackets.size(); ++i){
if(brackets[i] == ‘(‘)
dfs(brackets.substr(0,i+1)+"()"+brackets.substr(i+1), level-1);
}
};
dfs("", n);
vector<string> ans;
for(auto str : _set)
ans.emplace_back(str);
return ans;
}
剑指 Offer 10- I. 斐波那契数列
题解: 斐波那契数列公式 : f[i] = f[i-1] + f[i-2]
1. 注意点: 数论知识 (a + b) mod n == ( a mod n + b mod n ) mod n
int fib(int n) {
long long a[3] = {0, 1, 1};
if(n <= 2)
return a[n] % mod;
for(int i=3; i<=n; ++i){
a[0] = a[1], a[1] = a[2];
a[2] = (a[1] + a[0]) % mod; // 注意点: 取余不影响结果
}
return a[2];
}