首页 > 其他 > 详细

Leetcode 题解记录

时间:2021-09-06 05:20:00      阅读:38      评论:0      收藏:0      [点我收藏+]

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];
    }

  

 

Leetcode 题解记录

原文:https://www.cnblogs.com/xinwang-coding/p/15226331.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!