1.BFS

bfs主要包括一下应用，flood fill（洪水灌溉）把所有的值进行填充man，最小步数模型，就是最先到达的形态，使用的最小方法。然后就是多源bfs，这个思路就是吧所有的起点全部放入到queue里面。之后就是双向bfs，这个是节约搜索时间（使用两个queue来进行）

397. 整数替换

返回最小的次数，可以用递归，或者最小步数

思路也是没有发现了这个值，就放入st和queue

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
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
    int integerReplacement(int n) {
//        if (n==1)return 0;
//
//        if(n%2){
//            return min(integerReplacement(n-1), integerReplacement(n+1))+1;
//
//        }
//        return 1+ integerReplacement(n/2);
        queue<long> q;
        q.push(n);
        int step=0;
        set<long> st;
        while (q.size()){
            int n=q.size();
            for (int i = 0; i < n; ++i) {
                auto n1=q.front();
                q.pop();
                if(n1==1)return step;
                if(n1%2){
                    if(st.count(n1-1)==0){
                        st.insert(n1-1);
                        q.push(n1-1);
                    }

                    if (st.count(n1+1)==0){
                        q.push(n1+1);
                        st.insert(n1+1);
                    }


                }else{
                    if(st.count(n1/2)==0){
                        q.push(n1/2);
                        st.insert(n1/2);
                    }
                }
            }
            step++;
        }
        return -1;
    }
};


403. 青蛙过河

f[i][j】表示表示到达i这个点，下一步是j步数。

计算方法就是当前i可能是由j，j-1，j+1构成的，f【rec[num[i]-j]][j]可以由他来构成，所以我们要查看当前值有没有。最后一个我们只要看f【n-1】【0.。。n-1】有没有一个成功的

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
35
36
37
38
39
class Solution {
public:
    //直接使用dp，f【i】【j】是bool，表示到达i，下一步是j，是不是可能的
//    地推方程f[?][j-1],f[?][j],f[?][j+1]来构成
//一共到达n，有f[n][1],f[n][2],f[n][n]中方法，一个是true，就返回

    bool canCross(vector<int>& stones) {
        unordered_map<int,int> rec;

        int n=stones.size();
        for (int i = 0; i < stones.size(); ++i) {
            rec[stones[i]]=i;
        }
        int end=stones[stones.size()-1];
        vector<vector<bool>> f(n,vector<bool>(n, false));
        f[0][1]=true;
        //开门表示，0开始一步跳是可以的
        for (int i = 1; i < n; ++i) {
            for (int j = 1; j < n; ++j) {
                if(i==0&&j==1)continue;
                int x=stones[i];
                if(rec.count(x-j)){
                    f[i][j]=f[i][j]||f[rec[x-j]][j];
                }
                if(rec.count(x-j-1)&&j+1<n){
                    f[i][j]=f[i][j]||f[rec[x-j-1]][j+1];
                }if(rec.count(x-j+1)&&j-1>=0){
                    f[i][j]=f[i][j]||f[rec[x-j+1]][j-1];
                }
            }
        }
        for (int i = 1; i < n; ++i) {
            if(f[n-1][i])return true;
        }
        return false;
    }

};

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
35
36
37
class Solution {
public:
    bool canCross(vector<int>& stones) {
         int len = stones.size();

        //dp[i][j] 表示 第 i 个石头是否可以跳 j 步
        // boolean[][] dp = new boolean[len][len + 1];
                vector<vector<bool>> dp(len,vector<bool>(len+1, false));

        //初始条件：第 0 个石头可以跳 1 步
        dp[0][1] = true;

        for(int i = 1; i < len; i++){
            bool flag = false;
            //因为 石头 i 最大只能跳 i + 1 步，因此 前面的石头 j 到达 石头 i 的距离必须 <= i
            for(int j = i - 1; j >= 0; j--){
                int diff = stones[i] - stones[j];
                if(diff > i){
                    break;
                }
                //对于 石头 j ，它需要跳 diff 步
                if(dp[j][diff]){
                    dp[i][diff - 1] = true;
                    dp[i][diff] = true;
                    dp[i][diff + 1] = true;
                    flag = true;
                }
            }
            //当到达了终点 而 flag ，表示无法从前面的任意石头跳到终点，返回 false
            if(i == len - 1 && !flag){
                return false;
            }
        }
        return true;
    }
};

429. N 叉树的层序遍历

模板题目

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

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> ans;
        if (!root)return ans;
        queue<Node*> q;
        q.push(root);
        while(q.size()){
            int n=q.size();
            vector<int> path;
            for (int i = 0; i < n; ++i) {
                auto cur=q.front();
                q.pop();
                path.push_back(cur->val);
                for (int j = 0; j < cur->children.size(); ++j) {
                    if(cur->children[j]){
                        q.push(cur->children[j]);
                    }
                }
            }
            ans.push_back(path);
        }
        return ans;
    }
};

513. 找树左下角的值

dfs，直接加入depth，然后第一次出现的就进行设置，从做开始到右边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int max=0,ans=0;
    int findBottomLeftValue(TreeNode* root) {
        dfs(root,1);
        return ans;
    }
    void dfs(TreeNode* root,int depth){
        if(!root)return;
        if(depth>max){
            max=depth;
            ans=root->val;
        }
        dfs(root->left,depth+1);
        dfs(root->right,depth+1);
    }
};

或者直接每一层的用vector存着，然后放出第一个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Deque<TreeNode> d = new ArrayDeque<>();
        d.addLast(root);
        int ans = 0;
        while (!d.isEmpty()) {
            int sz = d.size();
            ans = d.peek().val;
            while (sz-- > 0) {
                TreeNode poll = d.pollFirst();
                if (poll.left != null) d.addLast(poll.left);
                if (poll.right != null) d.addLast(poll.right);
            }
        }
        return ans;
    }
}

515. 在每个树行中找最大值

标准的层序，然后当前的进行比较，放进去，或者是使用dfs来对每一个进行大小比较

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
class Solution {
public:
    unordered_map<int,int> rec;
    int max1;
    vector<int> largestValues(TreeNode* root) {
        if(!root)return {};
        dfs(root,0);
        rec[0]=root->val;
        vector<int>ans;
        for (int i = 0; i <=max1; ++i) {
            ans.push_back(rec[i]);
        }
        return ans;
    }
    void dfs(TreeNode* root,int depth){
        if(!root)return;
        if(depth>max1){
            max1=depth;
            rec[depth]=root->val;
        }else{
            rec[depth]=max(rec[depth],root->val);

        }
        dfs(root->left,depth+1);
        dfs(root->right,depth+1);
    }
};

559. N 叉树的最大深度

简单模板

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
class Solution {
public:
    unordered_map<int,int> rec;
    int maxdepth=0;
    int maxDepth(Node* root) {
        if(!root)return 0;
        int ans=0;
//        rec[0]=1;
        dfs(root,0);
        for (int i = 0; i <=maxdepth ; ++i) {
            ans=max(rec[i],ans);
        }
        return maxdepth+1;
    }
    void dfs(Node* root,int depth){
        if(!root)return;
        if(depth> maxdepth){
            maxdepth=depth;
            rec[maxdepth]=1;
        } else{
            rec[depth]++;
        }
        for (int i = 0; i < root->children.size(); ++i) {
            dfs(root->children[i],depth+1);
        }
    }
};

623. 在二叉树中增加一行

最开始就是在0层直接加，其它层就是找到深度-1的时候加入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    TreeNode* addOneRow(TreeNode* root, int val, int depth) {
        if(depth == 1)return new TreeNode(val,root, nullptr);
        dfs(root,val,depth,1);
        return root;
    }
    void dfs(TreeNode* root, int val, int depth,int height){
        if(height == depth - 1){
            root->left = new TreeNode(val,root->left, nullptr);
            root->right = new TreeNode(val,nullptr,root->right);
            return;
        }
        if(root->left)
        dfs(root->left,val,depth,height+1);
        if (root->right)
        dfs(root->right,val,depth,height+1);

    }
};

669. 修剪二叉搜索树

好题目，主要是想多了，如果当前值小，就返回右边的值（因为是bst，右边一定大），如果大，就返回左边的，如果符合返回root

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if(!root)return nullptr;
        if(root->val<low){
            //当前的国小,返回右边的
            return trimBST(root->right,low,high);
        }
        else if(root->val>high){
            return trimBST(root->left,low,high);
        }
        root->left=trimBST(root->left,low,high);
        root->right=trimBST(root->right,low,high);
        return root;

    }

127. 单词接龙

这个是求最短的变换方式，就是最小步数模型。我们通过检索每一个位置，然后进行a-z的变形，而且在指点里面就进行加入

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
unordered_set<string> S;
      unordered_map<string, int> dist;
      queue<string> q;
      dist[beginWord] = 1;
      q.push(beginWord);
      for (auto word: wordList) S.insert(word);

      while (q.size()) {
          auto t = q.front();
          q.pop();
          string r = t;
          for (int i = 0; i < t.size(); i ++ ) {
              t = r;
              for (char j = 'a'; j <= 'z'; j ++ )
                  if (r[i] != j) {
                      t[i] = j;
                      if (S.count(t) && dist.count(t) == 0) {
                          dist[t] = dist[r] + 1;
                          if (t == endWord) return dist[t];
                          q.push(t);
                      }
                  }
          }
      }

      return 0;


417. 太平洋大西洋水流问题

都可以流的，那我们只需要2次遍历，一次太平洋，一次大西洋，然后都可以的，两次遍历，取公共

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
static const int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

class Solution {
public:
    vector<vector<int>> heights;

    void bfs(int row, int col, vector<vector<bool>> & ocean) {
        if (ocean[row][col]) {
            return;
        }
        int m = heights.size();
        int n = heights[0].size();
        ocean[row][col] = true;
        queue<pair<int, int>> qu;
        qu.emplace(row, col);
        while (!qu.empty()) {
            auto [row, col] = qu.front();
            qu.pop();
            for (int i = 0; i < 4; i++) {
                int newRow = row + dirs[i][0], newCol = col + dirs[i][1];
                if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && heights[newRow][newCol] >= heights[row][col] && !ocean[newRow][newCol]) {
                    ocean[newRow][newCol] = true;
                    qu.emplace(newRow, newCol);
                }
            }
        }
    }

    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        this->heights = heights;
        int m = heights.size();
        int n = heights[0].size();
        vector<vector<bool>> pacific(m, vector<bool>(n, false));
        vector<vector<bool>> atlantic(m, vector<bool>(n, false));

        for (int i = 0; i < m; i++) {
            bfs(i, 0, pacific);
        }
        for (int j = 1; j < n; j++) {
            bfs(0, j, pacific);
        }
        for (int i = 0; i < m; i++) {
            bfs(i, n - 1, atlantic);
        }
        for (int j = 0; j < n - 1; j++) {
            bfs(m - 1, j, atlantic);
        }
        vector<vector<int>> result;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pacific[i][j] && atlantic[i][j]) {
                    vector<int> cell;
                    cell.emplace_back(i);
                    cell.emplace_back(j);
                    result.emplace_back(cell);
                }
            }
        }
        return result;
    }
};


433. 最小基因变化

简单的最小步数模型，和前两题一样

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
public:
    int minMutation(string startGene, string endGene, vector<string>& bank) {
        queue<string> q;
        q.push(startGene);
        int step=0;
        int t=0;
        set<string> st;
        for (int i = 0; i < bank.size(); ++i) {
            if (bank[i]==endGene){
                t=1;
            }
            st.insert(bank[i]);
        }
        set<string > rec;
        if(t==0)return -1;
        rec.insert(startGene);
        char dic[4]={'A','T','C','G'};
        while (q.size()){
            int n=q.size();
            for (int i = 0; i < n; ++i) {
                auto  cur=q.front();
//                cout<<cur<<endl;
                q.pop();
                if(cur==endGene)return step;
                for (int j = 0; j < cur.size(); ++j) {
                    for (int k = 0; k < 4; ++k) {
                        string b=cur;

                        b[j]=dic[k];
//                        cout<<cur<<endl;

                        if(st.count(b)){
                            if(!rec.count(b)){
                                q.push(b);
                                rec.insert(b);
                            }
                        }

                    }
                }
            }
            step++;
        }
        return -1;
    }
};


752. 打开转盘锁

最小步数模型，就是这样的模板，修改，如果为9，就变0或者8

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        //状态转移,使用最小步数模型,使用bfs
        queue<string> q;
        q.push("0000");
        unordered_map<string,int> rec;
        for (int i = 0; i < deadends.size(); ++i) {
            rec[deadends[i]]=1;
        }
        if (rec.find("0000")!=rec.end())return -1;

        rec["0000"]=1;

        int ans=0;
        while(q.size()){
            int n=q.size();

            for (int i = 0; i < n; ++i) {
                auto cur=q.front();
                q.pop();
//                cout<<cur<<" ";

                if (cur==target)return ans;
                for (int j = 0; j < 4; ++j) {
                    auto a= up(cur,j);
                    auto b= down(cur,j);

                    if(rec.find(a)==rec.end()){
                        q.push(a);
                        rec[a]=1;
                    }
                    if(rec.find(b)==rec.end()){
                        q.push(b);
                        rec[b]=1;
                    }


                }
            }
            //每一次++
            ans++;
        }
        return -1;
    }
    string up(string s,int i){
        if(s[i]=='9'){
            s[i]='0';
        }else{
            s[i]=s[i]+1;
        }
        return s;
    }
    string down(string s,int i){
        if(s[i]=='0'){
            s[i]='9';
        }else{
            s[i]=s[i]-1;
        }
        return s;
    }

};

2.DFS

dfs一般就是爆搜，进行排列组合，组合数，一般就是直接sort，排列数，就是使用st数组，然后continue条件就是排列是0，组合是u

17. 电话号码的字母组合

这个是组合数，u=，直接push进去。正常的回溯教程

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
class Solution {
public:
    vector<string> ans;
    string strs[10] = {
            "", "", "abc", "def",
            "ghi", "jkl", "mno",
            "pqrs", "tuv", "wxyz",
    };
    string path;
    vector<string> letterCombinations(string digits) {
        if (digits.empty())return ans;
        dfs(digits,0);
        return ans;

    }
    void dfs(string digits,int u){
        if(u==digits.size()){
            ans.push_back(path);
            return;
        }
        if(u>digits.size())return;
        int n=digits[u]-'0';
        for (int i = 0; i < strs[n].size(); ++i) {
            path.push_back(strs[n][i]);
            dfs(digits,u+1);
            path.pop_back();
        }
    }
};

22. 括号生成

这个条件就是左括号大于右括号，左右括号的值相等

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 {
public:
    vector<string> ans;
    string path;
    unordered_map<char,int> rec;
    vector<string> generateParenthesis(int n) {

        dfs(n,0);
        return ans;

    }
    void dfs(int n,int u){
        if(u==2*n){
            ans.push_back(path);
            return;
        }
//        cout<<path<<" ";
        if(rec.find('(')==rec.end()||rec['(']<n){
            path+='(';
            rec['(']++;
            dfs(n,u+1);
            path.pop_back();
            rec['(']--;
        }
        if (rec.find(')')==rec.end()||rec[')']<rec['(']){
            path+=')';
            rec[')']++;
            dfs(n,u+1);
            path.pop_back();
            rec[')']--;
        }

    }
};

37. 解数独

数独解法就是回溯，然后还是使用多个数组来进行，初始化每一个有的点

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
public:
    bool row[9][9],col[9][9],block[3][3][9];

    void solveSudoku(vector<vector<char>>& board) {
        memset(row,false,sizeof row);
        memset(col,false,sizeof col);
        memset(block,false,sizeof block);
        //初始化所有的点
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                if(board[i][j]!='.'){
                    int t=board[i][j]-'1';
                    row[i][t]=true;
                    col[j][t]=true;
                    block[i/3][j/3][t]=true;
                }
            }
        }
        dfs(board,0,0);
    }
    bool dfs(vector<vector<char>>& board,int x,int y){
        if (y==9){
            //进入下一轮
            x++;
            y=0;
        }
        if(x==9){
            return true;
        }
        //判断当前点是不是.可以填入
        if (board[x][y]!='.'){
            return dfs(board,x,y+1);
        }else{
            for (int i = 0; i <9; ++i) {
                if (row[x][i]||col[y][i]||block[x/3][y/3][i])continue;
                row[x][i]=col[y][i]=block[x/3][y/3][i]=true;
                board[x][y]='0'+i+1;
                if(dfs(board,x,y+1))return true;
                board[x][y]='.';
                row[x][i]=col[y][i]=block[x/3][y/3][i]=false;


                

            }
            return false;
        }
    }
};


39. 组合总和

因为是组合，所以所以使用sort，还有continue，从u开始

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
class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        dfs(candidates,target,0);
        return ans;
    }
    void dfs(vector<int> &nums,int u,int index){
        if (u==0){
            ans.push_back(path);
            return;
        }
        if (index==nums.size())return;
        if(u<0)return;
        for (int i = index; i < nums.size(); ++i) {
            path.push_back(nums[i]);
            dfs(nums,u-nums[i],i);
            path.pop_back();
        }

    }
};

40. 组合总和 II

这个就是药continue

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
class Solution {
public:
    vector<int> path;
    vector<vector<int>> ans;

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {

        sort(candidates.begin(),candidates.end());
        dfs(candidates,target,0);
        return ans;
    }
    void dfs(vector<int> &nums,int target,int u){
        if(target==0){
            ans.push_back(path);
            return;
        }
        if(u>=nums.size())return;
//
//        cout<<target<<"  ";
        for (int i = u; i < nums.size(); ++i) {
            if(nums[i]>target)return;
            if (i>u&&nums[i]==nums[i-1])continue;
            path.push_back(nums[i]);
            dfs(nums,target-nums[i],i+1);
            path.pop_back();
//            rec[nums[i]]=1;
        }
    }
};

93. 复原 IP 地址

他这个前导0，需要用进行替换，用u+1代替s。szie

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
35
36
37
38
39
40
41
42
43
44
45
class Solution {
public:
    int start;
    int end;
    vector<string> ans;
    string path;
    vector<string> restoreIpAddresses(string s) {
        start=0,end=255;
        dfs(s,4,0);
        return ans;
    }
    void dfs(string s,int times,int u){
        //不出现011
        //只有3个小数点可以进行加入
        if (!times&&u==s.size()){
            path.pop_back();
            ans.push_back(path);
            return;
        }
        if (times<0)return;
        if(u>=s.size())return;
        int n=u+1;
        if(s[u]!='0')n=s.size();
        // if(s[u]=='0'){
        //     path+="0.";
        //     dfs(s,times-1,u+1);
        //     return ;
        // }else{
            for (int i = u; i < n; ++i) {
                if (i-u+1>3)return;
                auto x=s.substr(u,i-u+1);

                auto t= stoi(x);
                if(t<=255){
                    auto back=path;
                    path+=x+".";
                    dfs(s,times-1,i+1);
                    path=back;
                }
            }
        // }


    }
};

95. 不同的二叉搜索树 II

找出不同的bst，我们设置根节点为0到n-1，没次遍历，然后左右两边设置为左右树，同事也对每一个左右节点来作为root的左右

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 {
public:
    vector<TreeNode*> generateTrees(int n) {
        // 进行建树，从1-n开始，可以改成1-l-1，l，和l+1到n
        vector<TreeNode*> ans=dfs(1,n);
        return ans;
    }
    vector<TreeNode*> dfs(int l,int r){
        vector<TreeNode*> res;
        if(l>r){
             res.push_back(NULL);
            return res;
            }
        
        for(int i=l;i<=r;i++){
        vector<TreeNode*> left=dfs(l,i-1);
        vector<TreeNode*> right=dfs(i+1,r);
        
        // 接着就是左右节点的选择
        for(auto &L:left){
            for(auto &R:right){
                TreeNode *root = new TreeNode(i);
                    root->left = L;
                    root->right = R;
                    res.push_back(root);
            }
        }

        }
        return res;

    }
};

310. 最小高度树

建图也tle，使用树形dp，下次在写

386. 字典序排数

这个的思路还是首先dfs，如果大于了，就返回，然后直接push

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
class Solution {
public:
    vector<int> ans;
    vector<int> lexicalOrder(int n) {
        string path;

        dfs(to_string(n),0,path);
        return ans;
    }
    void dfs(string s ,int u,string path){

        if(u>s.size())return;
        if(u>0&&stoi(s)< stoi(path)){
//            ans.push_back(stoi(path));
            return;
        }else if(u){
            ans.push_back(stoi(path));
        }
        int start=0;
        if(u==0)start=1;
        for (int i = start; i <=9; ++i) {
            auto b=path;
            path+= to_string(i);
            dfs(s,u+1,path);
            path=b;
        }
    }
};

首先对u来进行判断，u=0，只能从1开始，其他都是

437. 路径总和 III

双重dfs，这个题目，首先第一次是遍历，第二次就是进行对以他为root，来查找路径

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
class Solution {
public:
//两个dfs，第一个遍历点，第二几个计算

    int ans;
int x;
    int pathSum(TreeNode* root, int targetSum) {
        if (!root)return 0;
        x=targetSum;
        dfs1(root);
        return ans;
    }
    void dfs1(TreeNode* root){
        if(!root)return;
        dfs2(root,x-root->val);
//        cout<<"-----------"<<endl;
        dfs1(root->left);
        dfs1(root->right);
    }
    void dfs2(TreeNode* root, long targetSum){
        if(targetSum==0){
            ans++;
//            return;
        }
        if(!root->left&&!root->right)return;
//       cout<<targetSum<<" ";
        if(root->left)dfs2(root->left,targetSum-root->left->val);
        if(root->right)dfs2(root->right,targetSum-root->right->val);
    }
};

473. 火柴拼正方形

这个就是和之前的分组都是一样的，可以看成k=4，求解4个相等的

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
35
36
class Solution {
public:
    vector<bool> st;
    int x;
    bool makesquare(vector<int>& matchsticks) {
        int sum= accumulate(matchsticks.begin(),matchsticks.end(),0);
        if(sum%4)return false;
        int k=sum/4;
        sort(matchsticks.begin(),matchsticks.end());
        if(matchsticks.back()>k)return false;
        st=vector<bool>(matchsticks.size(),false);
        x=k;
        return dfs(matchsticks,x,0,0);
    }
    bool  dfs(vector<int> &nums,int target,int index,int u){
        if(u==4)return true;
//        cout<<u;
        if(target==0)return dfs(nums,x,0,u+1);
//        if(target<0)return false;
        for (int i = index; i < nums.size(); ++i) {
            if(!st[i]&&target-nums[i]>=0){
                st[i]=true;
//                path.push_back(nums[i]);
                if(dfs(nums,target-nums[i],i+1,u)){
                    return true;
                }
                st[i]=false;
//                path.pop_back();
                //排好序了的,如果当前都没办法减少到0,后面就不可能
                if (target==x)return false;
            }
        }
        return false;
    }

};

然后还是使用index开始，最后的一个剪纸条件就是，无论如何这个target都不在改变，那就是失败了。我们可以把target看成某一成的值，但是他在这一层不变，说明以后的层也不变

494. 目标和

dfs两次操作就是+，-

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int ans;
    int findTargetSumWays(vector<int>& nums, int target) {
        dfs(nums,0,target);
        return ans;
    }
    void dfs(vector<int>& nums,int u,int target){
        if(u==nums.size()&&target==0){
            ans++;
            return;
        }
        if(u>=nums.size())return;
        dfs(nums,u+1,target-nums[u]);
        dfs(nums,u+1,target+nums[u]);
    }
};