dfs与回溯

发表于 | 更新于 | 评论数： | 阅读次数： | 阅读次数：

17. Letter Combinations of a Phone Number

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    
    string chars[8] = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};//备选字符
    
    vector<string> letterCombinations(string digits) {
        if(digits.empty()) return vector<string>();    //这里注意返回一个空的vector
        vector<string> state (1, "");                  //这里初始话了一个有一个 空元素 的vector （不是空的vector了）
        for(auto digit : digits) {
            vector<string> now;
            for (auto c : chars[digit - '2']) {
                for (auto s : state) {
                    now.push_back(s + c);
                }
            }
            state = now;
        }
        return state;
    }
};

关于string 的默认初始化

79. Word Search

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:
    bool exist(vector<vector<char>>& board, string word) {
        if (board.empty() || board[0].empty()) return false; //判断数组是否为空
         
        for (int i = 0; i < board.size(); i++)
            for (int j = 0; j < board[0].size(); j++)
                if (dfs(board, word, 0, i, j))  // dfs返回值是bool，放在if里
                    return true;
        return false;
    }
    bool dfs (vector<vector<char>>& board, string& word, int u, int x, int y) { //参数这里用&
        if(board[x][y] != word[u]) return false;
        if (u == word.size() - 1) return true;    //如果当前是word的最后一个字符，说明已经找到答案了。
        board[x][y] = '*'; //这里不需要再设一个temp了，因为程序运行到这里说明 word[u]==board[x][y]... 回溯时用word[u]即可
                            
        int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1}; //下， 右， 上， 左
        for (int i = 0; i < 4; i++) {
            int a = x + dx[i], b = y + dy[i];//移动到下一个位置, 这里注意由于最后要回溯，所以不要更新x, y，这里要设置新的遍历
            if (a >= 0 && a < board.size() && b >= 0 && b < board[0].size()) 
                if (dfs(board, word, u + 1, a, b))  //dfs返回值是bool的dfs函数 放if里判断
                    return true;
            
        }


        board[x][y] = word[u]; //回溯
        return false;          //运行到回溯这里就说明当前的状态不匹配，所以return false
    }
};

如果状态是整个棋盘，那么一定要恢复现场
如果状态是棋盘中的某一个格子，就不需要恢复现场

46. Permutations

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
class Solution { //方法一： 枚举每个位置可以放哪些数字
public:
    int n ;
    vector<vector<int>> ans;
    vector<int> path;
    vector<bool> st;
    
    vector<vector<int>> permute(vector<int>& nums) {
        n = nums.size();
        st = vector<bool>(n, false);
        dfs(nums, 0);

        return ans;
    }
    void dfs(vector<int>& nums, int u) {
        if (u == n) {
            ans.push_back(path);
            return;
        }
        for(int i = 0; i < n; i++) {
            if (!st[i]) { //如果这个数没有被用过
                path.push_back(nums[i]); //那么就把这个数加到当前方案中
                st[i] = true; //标记一下nums[i]已经用过了
                dfs(nums, u + 1); //进入下一个格子
                //回溯
                st[i] = false;
                path.pop_back();
            }
        }
    }       
    
};

47. Permutations II

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
class Solution { //方法二： 枚举每个数可以放到哪个位置上
public:
    vector<vector<int>> ans;
    vector<int> path;
    vector<bool> st;
    int n;
       
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        n = nums.size();
        path = vector<int>(n);
        st = vector<bool>(n, false);
        
        sort(nums.begin(), nums.end());
        dfs(nums, 0, 0);
        return ans;
    }
    
    void dfs (vector<int>& nums, int u, int start) {
        if (u == n) {
            ans.push_back(path);
            return;
        }
        for (int i = start; i < n; i++) {
            if(!st[i]) {   //如果当前位置上可以放置数字...
                path[i] = nums[u];
                st[i] = true;
                if(u + 1 < n && nums[u + 1] == nums[u])  //如果下一个数字与当前数字相等
                    dfs(nums, u + 1, i + 1);             //那么它只能放置在当前数字后面的格子上
                else
                    dfs(nums, u + 1, 0);      //下一个数字与当前数字不相等，那么它可以放置在任意格子上，即格子可以从0开始遍历
                //回溯， 这里没有弹出path[i],是因为下次循环时 path[i]会被覆盖
                st[i] = false;
                
            }
                     
        }
         
    }
        
};

枚举每个数放到哪个位置上
将相同的数放在一起 sort

78. Subsets

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        for (int i = 0; i < 1 << nums.size(); i++) {  // 枚举每种组合结果,假设nums.size()为3，那么这里 i的范围是 0 ~  7, 表示8种可能的集合组成
            vector<int> now;
            for(int j = 0; j < nums.size(); j++)  //枚举每个数字
                if (i >> j & 1)                  
                    now.push_back(nums[j]);
            res.push_back(now);
        }
        return res;
    }
};

判断 i的二进制表示的第j位是否为1

i >> j & 1 j从0开始计数，即 二进制数最右边是第0位

位运算是o(1)的

90. Subsets II

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<vector<int>> ans;
    vector<int> path;
    int n;
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        n = nums.size();
        sort(nums.begin(), nums.end());
        dfs(nums, 0);
        return ans;
    }
    void dfs (vector<int>& nums, int u) {
        if (u == n) {
            ans.push_back(path);
            return;
        }
        int k = 0;
        while(u + k < n && nums[u] == nums[u + k]) k++;
        
        for (int i = 0; i <= k; i++) {
            dfs(nums, u + k);
            path.push_back(nums[u]);
           
        }
        //path.erase(path.end() - k - 1, path.end());  //回溯（两种语法可以实现）
        for (int i = 0; i <= k; i++) path.pop_back(); 
    }
};

举个例子：

  1. [1, 2, 3, 4, 5]

1 : 0 , 1 元素1可以选择不放 或者 放
2 : 0 , 1
3 : 0 , 1
4 : 0 , 1
5 : 0 , 1

  1. [1, 1, 2, 2, 2]

1 : 0, 1, 2 元素1可以选择不放， 放一个， 放两个…
2 : 0, 1, 2, 3

216. Combination Sum III

1
2


依次枚举每个数从哪个位置上选
举个例子：

从1 2 3 4中选三个数，

第一个数可以从
1 1
2 3
4 这几个位置上选
第二个数就要从剩下的数里选了

  1. 2， 3， 4
  2. 1， 3， 4
    …

dfs(当前枚举到了第几个数字， 开始枚举的位置， 当前选择的所有数的和)

52. N-Queens II

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
class Solution {
public:
    
    int ans = 0, n;
    vector<bool> col, d, ud;
        
    int totalNQueens(int _n) {
        n = _n;                //把_n存到全局变量里， 这样可以少传一些参数
        col = vector<bool>(n);
        d = ud = vector<bool> (n * 2); //对角线为什么开 2 * n 呢？
        dfs (0); //从前往后枚举每一行
        
        return ans;
       
    }
    
    void dfs (int u) {
        if (u == n) {
            ans++;
            return;
        }
        
        for (int i = 0; i < n; i++) {  //当前坐标是(u, i)
            if (!col[i] && !d[u + i] && !ud[u - i + n]) {
                col[i] = d[u + i] = ud[u - i + n] = true;
                dfs(u + 1);
                col[i] = d[u + i] = ud[u - i + n] = false; //回溯
            }
        }
    
    }
   
};

依次枚举每一行皇后的位置（每一行只有一个皇后）

  1. 每一列只能有一个皇后 col[N]
  2. 每条斜线上只能有一个皇后 d[2 * N - 1], ud[2 * N - 1]

需要判断每一个坐标(x, y)在哪一条斜线上

x + y
x - y + n //因为ud[]索引非负，而x - y 可能为负， 所以这里要加上一个 n （当x = 0, y = n - 1， x - y + n = 1）

0%