前言

今天学了点Django，补题补晚了点，最近在做有关dfs的题目，y总的思路真的是太清晰了。

题目

leetcode 93 恢复IP地址

题目

恢复IP地址

思路

就是暴力递归求解就好了，不过现在暴力递归求解都写不太好。这种题都是设计从左向右依次尝试的做法，我们需要注意的函数体内部的一些判断方法。

代码

class Solution {
public:
    vector<string> res;
    vector<string> restoreIpAddresses(string s) {
        dfs(s, 0, 0, "");
        return res;
    }
    void dfs(string& s, int index, int k, string ans){
        if(index == s.size()){
            if(k == 4){
                ans.pop_back();
                res.emplace_back(ans);
                return;
            }
        }
        if(k == 4) return;
        int temp = 0;
        for(int i = index; i < s.size(); ++ i){
            //判断有无前导0
            if(i > index && s[index] == '0') break;
            temp = temp * 10 + s[i] - '0';
            if(temp <= 255) 
                dfs(s, i + 1, k + 1, ans + to_string(temp) + ".");
            else break;
        }
    }
};

leetcode 22 括号生成

题目

括号生成

思路

关于有效括号类的题目：
1.每一个括号的前面左括号的数大于等于右括号的数；
2.左括号的数等于右括号的数
然后就避免使用了栈进行判断。

代码

class Solution {
public:
    vector<string> res;
    vector<string> generateParenthesis(int n) {
        dfs(n, 0, 0, 0, "");
        return res;
    }
    void dfs(int &n, int index, int l, int r, string ans){
        if(index == 2 * n) {
            res.emplace_back(ans);
            return;
        }
        if(l < n) dfs(n, index + 1, l + 1, r, ans + "(");
        if(l > r) dfs(n, index + 1, l, r + 1, ans + ")");
    }
};