Cpp五条

这个屌丝很懒，什么也没留下！

热门标签

回溯和递归 - 归档_递归返回上一层

作者：Cpp五条 | 2024-05-18 23:50:03

踩

递归返回上一层

LeetCode - 回溯和递归

概述

方式	性质
递归	自顶向下，对于有重叠子问题的递归，可以使用记忆化搜索。
回溯	回溯是属于递归的，是递归返回上一层的过程，暴力解法的主要实现手段。与之对应的是多重循环（每层遍历数量固定的话）。另外回溯可以通过剪枝来优化，不用到达所有的叶子节点。
深度优先	floodfill算法

树形递归

17. Letter Combinations of a Phone Number

417. Pacific Atlantic Water Flow

17. Letter Combinations of a Phone Number

处理数字的个数代表递归的深度，比如第一层处理第一个数字2 -> “abc”, 第二层处理第二个数字 3 ->“def”，每一层都需要把当前数字代表的字符串取出来遍历字符，然后累加到下一层中去。
参数combine在传递的时候，可以直接在参数里面加上当前遍历的字符c，这样避免回退到上一层的时候还需要从combine里面把c去除的操作。

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> res;
        string combine;
        if(digits.empty()){
            return res;
        }
        letterCombination(digits, 0, combine, res);
        return res;
    }
    void letterCombination(string& digits, int i, string combine, vector<string>& res){
        if(i >= digits.size()){
            res.push_back(combine);
            combine.clear();
            return;
        }
        string chars = getChars(digits[i]);
        for(auto& c: chars){
            //combine += c;
            //letterCombination(digits, i + 1, combine, res);
            //combine.pop_back();
            letterCombination(digits, i + 1, combine + c, res);
        }
    }
    string getChars(char& digit){
        string chars;
        switch(digit){
            case '2':
            chars = "abc";
            break;
            case '3':
            chars = "def";
            break;
            case '4':
            chars = "ghi";
            break;
            case '5':
            chars = "jkl";
            break;
            case '6':
            chars = "mno";
            break;
            case '7':
            chars = "pqrs";
            break;
            case '8':
            chars = "tuv";
            break;
            case '9':
            chars = "wxyz";
            break;
        }
        return chars;
    }
};
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

93. Restore IP Addresses

Input: “25525511135”
Output: [“255.255.11.135”, “255.255.111.35”]
在这里插入图片描述

class Solution {
public:
    //回溯，穷举三个逗号放置到头尾之间的任何位置的情况，判断每一段的数字是否符合ip要求，
    //符合的话就push到返回值里面.
    //处理到的逗号的个数代表递归的深度，逗号分隔的长度是1~3.
    //一共四段数据，input不能够剩，也不能够超.
    vector<string> restoreIpAddresses(string s) {
        vector<string> ret;
        helper(s, 0, 0, "", ret);
        return ret;
    }
private:
    void helper(string& s, int index, int part, string combine, vector<string>& ret){
        if(part == 4){//part表示当前combine包含了几部分数据，4就已经包含满了一个IP的四段
            if(index == s.size()){//还需要满足当前已经取完了所有的input
                ret.push_back(combine);//combine就是递归到底组成的IP字符串结果
            }
            return;
        }
        for(int len = 1; len <= 3 && (index + len - 1 < s.size()); len++){
            string cur = s.substr(index, len);
            //cout << "partNumber: " << part << " partLen: " << len << " partStr: " << cur << " partCombine: " << combine + cur << endl;
            //这一part的数据需要满足IP值范围
            if(atoi(cur.c_str()) > 255 || (len != 1 && cur[0] == '0'))
                return;
            //如果在最后一part，就不需要再往后面添加.了
            else if(part != 3)
                cur += ".";
            //cout << "index= " << index + len << endl;
            helper(s, index + len, part + 1, combine + cur, ret);
        }
            return;
    }
};
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

131. Palindrome Partitioning

在这里插入图片描述

class Solution {
public:
    //最开始想到用dp方式，最后遍历选出dp[i][j]中为回文的串，但是发现返回要求的是二维数组，
    //每个子数组对应的是s拆分为多个回文子串的结果，这满足一次回溯构建的结果。
    //helper(s,istart): [istart, s.end()]部分可以分隔成的回文串数组。
    //使用dp先把dp数组填满，就可以在接下来用O(1)时间判断当前substr是否为回文。
    vector<vector<string>> partition(string s) {
        vector<vector<string>> ret;
        vector<string> combine;
        if(s.empty())
            return ret;
        helper(s, 0, combine, ret);
        return ret;
    }
private:
    void helper(string& s, int istart, vector<string>& combine, vector<vector<string>>& ret){
        if(istart >= s.length()){
            ret.push_back(combine);
            return;
        }
        for(int i = istart; i < s.length(); i++){
            if(check(s, istart, i)){
                combine.push_back(s.substr(istart, i - istart + 1));
                helper(s, i + 1, combine, ret);
                combine.pop_back();
            }
        }
        
    }
    bool check(const string&s, int i, int j) {
        while (i <= j && s[i] == s[j]){
            i++;
            j--;
        }
        return (j < i);
    }
};
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

46. Permutations

全排列
在这里插入图片描述

class Solution {
public:
    //helper(index, combine, added): 当前加入的是combine构建过程的第index个数字。
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ret;
        if(nums.empty())
            return ret;
        vector<int> combine;
        //记录在递归过程中，已经被加入combine的数字的索引，在下一层的递归调用中，要避免使用到已经使用到的数字
        vector<bool> added(nums.size(), false);
        helper(nums, 0, combine, ret, added);
        return ret;
    }
private:
    void helper(vector<int>& nums, int index, vector<int>& combine, vector<vector<int>>& ret, vector<bool>& added){
        if(index >= nums.size()){
            ret.push_back(combine);
            return;
        }
        for(int i = 0; i < nums.size(); i++){
            if(!added[i]){
                combine.push_back(nums[i]);
                added[i] = true;
                helper(nums, index+1, combine, ret, added);
                //回到当前层的调用中的时候，需要将刚才作为当前层加入的数字nums[i]去除，选择当前层另外可以选择的数字
                //并且将当前数字nums[i]的索引从added中去除，因为下一层调用可能会使用它。
                combine.pop_back();
                added[i] = 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

47. Permutations II

在46题的基础上，将输入的数组先排序，然后在函数里的迭代过程中，判断前后两次的数字是否相同，相同的话就剪枝。

class Solution {
public:
    //函数递深度增加combine的size, 当前递归函数的迭代（for）尝试当前构建第index个数字的不同选择。
    vector<vector<int>> permuteUnique(vector<int>& nums) {
    	...
        sort(nums.begin(), nums.end());
        ...
    }
private:
    void helper(vector<int>& nums, int index, vector<int>& combine, vector<vector<int>>& ret, vector<bool>& added){
    		......
    		...
            //用iprev剪枝，当前遍历的数字和上一次的相同，就不用再继续构建了。
            if(!added[i] && nums[i] != iprev){
                combine.push_back(nums[i]);
                added[i] = true;
                helper(nums, index+1, combine, ret, added);
                //迭代过程中，可能下一个数字和上一个数字相同，这里记录好上一次的数字，与下一次的比较。
                iprev = combine.back();
                combine.pop_back();
                added[i] = false;
				.....
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

77. Combinations

组合问题，与排列问题不同，排列中相同元素可以有不同的顺序，组合中没有。
在当前的迭代中，给到下一层的迭代范围必须除开当前层已经处理过元素以避免形成不同顺序但是相同元素的序列，因为迭代是从左往右遍历的，所以可以直接右移左边界：helper(n, k, i+1, combine, ret);
代码里遍历有一行所谓的剪枝优化已经被注释掉，个人觉得不像是剪枝。

在这里插入图片描述

class Solution {
public:
    //组合问题，区别于排列问题
    //helper(index, combine): 当前加入的是combine构建过程的第index个数字。
    //[1,2,3] == [2,1,3] 只能算是同一个组合
    //[1,2,3] == [1,3,2] 只能算是同一个组合
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> ret;
        if(n <= 0 || k <= 0 || n < k){
            return ret;
        }
        vector<int> combine;
        helper(n, k, 1, combine, ret);
        return ret;
    }
private:
    void helper(int n, int k, int index, vector<int>& combine, vector<vector<int>>& ret){
        if(k == combine.size()){
            ret.push_back(combine);
            return;
        }
        //这个算得上是剪枝？
        //for(int i = index; i <= n - k + combine.size() + 1; i++){
        for(int i = index; i <= n; i++){
            combine.push_back(i);
            //下一层的迭代范围从当前元素右边开始，不能包含当前已经遍历过的数字。
            helper(n, k, i+1, combine, ret);
            combine.pop_back();
        }
    }
};

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

39. Combination Sum

也是回溯方法求组合，组合方式细微差别。
加了打印看流程。

递归进入下一层的范围从当前索引开始

class Solution {
public:
    //helper(index, combination): 表示从index开始遍历，以及迭代index位置得到的combination
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> ret;
        vector<int> combination;
        if(candidates.empty())
            return ret;
        helper(candidates, 0, combination, 0, target, ret, 0);
        return ret;

    }
private:
    void helper(vector<int>& candidates, int index, vector<int>& combination, int sum, int target, vector<vector<int>>& ret, int deep){
        if(index >= candidates.size() || sum > target){
            trace_depth(deep);cout << "not meet, return" << endl;
            return;
        }
        else if(sum == target){
            ret.push_back(combination);
            trace_depth(deep);cout << "meet, return"<< endl;
            return;
        }
        for(int i = index; i < candidates.size(); i++){
            combination.push_back(candidates[i]);
            trace_depth(deep); cout << "pick candidates[" << i << "]" << " "; trace_combination(combination);
            helper(candidates, i, combination, sum + candidates[i], target, ret, deep+1);
            combination.pop_back();
            trace_depth(deep); cout << "pop  candidates[" << i << "]" << " "; trace_combination(combination);
        } 
        return;
    }
    void trace_combination(vector<int>& combination){
                    cout << "combination:";
            for(auto &x : combination)
                cout << x << " ";
            cout << endl;
    }
    void trace_depth(int deep){
        for(int i = 0; i < deep; i++){
            cout << "->";
        }
    }
};
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

40. Combination Sum II

参考47题，先排序，这样在每层迭代过程中就可以通过前后元素是否相同来进行剪枝。

        int prev = INT_MAX;
        for(int i = index; i < candidates.size(); i++){
            if(candidates[i] == prev)
                continue;
            combination.push_back(candidates[i]);
            helper(candidates, i+1, combination, sum + candidates[i], target, ret, deep+1);
            prev = combination.back();
            combination.pop_back();
        } 
        return;
1
2
3
4
5
6
7
8
9
10

216. Combination Sum III

if(sum = n && combination.size() = k)中，参数sum可以被减掉，直接对n/k进行自减判0即可（符合排列组合的暴力回溯只需要到叶子节点无需返回结果的特性）
helper(index, combination): 表示从index开始遍历，构建第combination.size()+1个数，直到叶子节点返回时combination构建完成。helper没有返回值，无法构成子问题解（此类问题也没有状态转移）

class Solution {
public:
    //helper(index, combination): 表示从index开始遍历，构建第combination.size()+1个数，直到叶子节点返回时combination构建完成。
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> ret;
        vector<int> combination;
        helper(n, 1, k, combination, ret, 0);
        return ret;
    }
private:
    void helper(int n, int index, int k, vector<int>& combination, vector<vector<int>>& ret, int deep){
        //if(sum == n && combination.size() == k){
        if(n == 0 && k == 0){
            ret.push_back(combination);
            return;
        }
        else if(index > 9 || n < 0 || k < 0){
            return;
        }
        for(int i = index; i <= 9; i++){
            combination.push_back(i);
            helper(n-i, i+1, k-1, combination, ret, deep+1);
            combination.pop_back();
        } 
        return;
    }
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

78. Subsets

Given a set of distinct integers, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Example:
Input: nums = [1,2,3]
Output:
[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]

在77题基础上套一个循环，求解不同长度的组合。
（优化）在77题基础上，修改递归函数，不管到了几层(不管当前combine在构建长度为几的数组)都push combine到返回值ret中去，形成不同长度的数组。

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums){
        vector<vector<int>> ret;
        vector<int> combine;
        helper(nums, nums.size(), 0, combine, ret);
        return ret;
    }
private:
    void helper(vector<int>& nums, int k, int index, vector<int>& combine, vector<vector<int>>& ret){
    	//这里直接就push当前长度的combine到ret中去。
        ret.push_back(combine);
        if(k == combine.size()){
            return;
        }
        for(int i = index; i < nums.size(); i++){
            combine.push_back(nums[i]);
            helper(nums, k, i+1, combine, ret);
            combine.pop_back();
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

90. Subsets II

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Example:
Input: [1,2,2]
Output:
[ [2], [1], [1,2,2], [2,2], [1,2], []]

回溯暴力求解 + 排序在求解combine数组中的第k个数（所有递归深度为k）的时候，这个数如果和之前的数（深度为k的函数中前一个迭代的数字）相等的话，那么就直接跳过这个数字。

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums){
        vector<vector<int>> ret;
        vector<int> combine;
        sort(nums.begin(), nums.end());
        helper(nums, nums.size(), 0, combine, ret);
        return ret;
    }
private:
    void helper(vector<int>& nums, int k, int index, vector<int>& combine, vector<vector<int>>& ret){
    	//这里直接就push当前长度的combine到ret中去。
        ret.push_back(combine);
        if(k == combine.size()){
            return;
        }
        int prev = INT_MAX;
        for(int i = index; i < nums.size(); i++){
            if(prev != nums[i]){
                prev = nums[i];
                combine.push_back(nums[i]);
                helper(nums, k, i+1, combine, ret);
                combine.pop_back();
            }
        }
    }
};
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

401. Binary Watch

Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent.
Example:
Input: n = 1
Return: [“1:00”, “2:00”, “4:00”, “8:00”, “0:01”, “0:02”, “0:04”, “0:08”, “0:16”, “0:32”]

class Solution {
public:
    //10个待选择的数字[0...9]代表表盘从上到下，从左到右的索引,选择num个索引，将索引到的灯点亮就是显示效果
    //ex: n=5, 用[2,3,4,5,9]作为索引来填充一个空的字，bitmap=0x0000(16bit)，bitmap | = 512 >> x
    //bitmap >> 6 & 0xF : bitmap & 0x6 从数字到字符转换就是 3:25
    vector<string> readBinaryWatch(int num) {
        vector<string> ret;
        vector<int> combine;
        int n = 9;
        if(num < 0){
            return ret;
        }
        helper(n, num, 0, combine, ret);
        return ret;
    }
private:
    void helper(int& n, int& num, int index, vector<int>& combine, vector<string>& ret){
        if(num == combine.size()){
            str = getTime(ret, combine);
            if(!str.empty()) ret.push_back(str);
            return;
        }
        for(int i = index; i <= n; i++){
            combine.push_back(i);
            helper(n, num, i+1, combine, ret);
            combine.pop_back();
        }
    }
    string getTime(vector<string>& ret, vector<int>& combine){
        int bitmap = 0;
        for(int i = 0; i < combine.size(); i++){
            bitmap |= (512 >> combine[i]);
        }
        if((((bitmap >> 6) & 0xF) >= 12) || (bitmap & 0x3F) >= 60)
            return "";
        str1 = to_string((bitmap >> 6) & 0xF);
        str2 = (bitmap & 0x3F) < 10 ? to_string(0) + to_string(bitmap & 0x3F) : to_string(bitmap & 0x3F);
        if(str2 == "0")
            str2 += "0";
        return str1 + ":" + str2;
    }
    string str;
    string str1;
    string str2;
};
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

79. Word Search

board =
[
[‘A’,‘B’,‘C’,‘E’],
[‘S’,‘F’,‘C’,‘S’],
[‘A’,‘D’,‘E’,‘E’]
]
Given word = “ABCCED”, return true.

相比线性的回溯，这里有一个扩展和一个约束

扩展是递归过程构建下一个元素有多个选择（二维平面的几个方向）
约束是构建的对象是word，递归路径过程中就进行了比较，不用搜索全部路径（200题的floodfill就是搜索全部路径）
注意需要判断x,y是否在区域内，以及是否被访问过。

class Solution {
public:
    //helper(b_x, b_y, w_idx): board的x,y位置是否和word的第i个字母相同，如果相同，继续基于x,y向周边元素扩散
    bool exist(vector<vector<char>>& board, string word) {
        vector<vector<bool>> acceed(board.size(), vector<bool>(board[0].size(), false));
        for(int i = 0; i < board.size(); i++){
            for(int j = 0; j < board[0].size(); j++){
                if(helper(board, word, i, j, 0, acceed))
                    return true;
            }
        }
        return false;
    }
private:
    bool helper(vector<vector<char>>& board, string& word, int& b_x, int& b_y, int w_idx, vector<vector<bool>>& acceed){
        if(w_idx == word.size() - 1)
            return word[w_idx] == board[b_x][b_y];

        //当前坐标与word的第w_idx个匹配，继续往后面走
        if(word[w_idx] == board[b_x][b_y]){
            acceed[b_x][b_y] = true;
            //朝上下左右各尝试一步
            for(int i = 0; i < 4; i++){
                int new_x = b_x + next[i][0];
                int new_y = b_y + next[i][1];
                if(new_x >= 0 && new_x < board.size() &&
                   new_y >= 0 && new_y < board[0].size() &&
                   !acceed[new_x][new_y] && helper(board, word, new_x, new_y, w_idx+1, acceed)){
                        return true;
                    }
                }
                //当前坐标不满足，移除
                acceed[b_x][b_y] = false;
        }
        return false;
    }
    int next[4][2] = {{0,1}, {0,-1},{-1, 0}, {1,0}};
};
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

200. Numer of Islands

DFS Floodfill algorithem
Input:
11000
11000
00100
00011
Output: 3

和79.Word Search基本相同，没有目标参数word, 深度优先搜索当前满足填充为1的区域，然后将遍历到的元素设置为已访问，同时返回值+1，遍历grid，对每个位置都做以上的操作。
递归没有返回值，因为不用因为只需要深度搜索过程中填充整个区域，不需要像79.Word Search一样要满足某个搜索条件。
没有显示的递归结束条件

class Solution {
public:
    //helper(g_x, g_y, w_idx): grid的x,y位置开始进行DFS,是否构成一个新的isLand.
    int numIslands(vector<vector<char>>& grid) {
        if(grid.empty())
            return 0;
        vector<vector<bool>> acceed(grid.size(), vector<bool>(grid[0].size(), false));
        int isLands = 0;
        for(int i = 0; i < grid.size(); i++){
            for(int j = 0; j < grid[0].size(); j++){
                if(grid[i][j] == '1' && !acceed[i][j]){
                    isLands++;
                    helper(grid, i, j, acceed);
                }
            }
        }
        return isLands;
    }
private:
    void helper(vector<vector<char>>& grid, int& g_y, int& g_x, vector<vector<bool>>& acceed){
        acceed[g_y][g_x] = true;
        //cout << g_x << " " << g_y << ": " << grid[g_y][g_x] << endl;
        //朝上下左右各尝试一步
        for(int i = 0; i < 4; i++){
            int new_y = g_y + next[i][1];
            int new_x = g_x + next[i][0];
            if(new_y >= 0 && new_y < grid.size() &&
               new_x >= 0 && new_x < grid[0].size() &&
               grid[new_y][new_x] == '1' && !acceed[new_y][new_x]){
                    helper(grid, new_y, new_x, acceed);
            }
        }
        return;
    }
    int next[4][2] = {{0,1}, {0,-1},{-1, 0}, {1,0}};
};
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

130. Surrounded Regions

Given a 2D board containing ‘X’ and ‘O’ (the letter O), capture all regions surrounded by ‘X’.
A region is captured by flipping all 'O’s into 'X’s in that surrounded region.

题解中很多把边缘连通的O替换成其他符号，对剩余的O进行X替换，最后将其他符号替换回原来的O。
下面代码暴力一些，直接将非连通边缘的O替换成X, 其实时间复杂度更高了。
另外这道题花了三天晚上，主要是在标记accessed O 与不标记的情况下，都有对应的case没过，最后得出：accessed标记还不够约束到accessed的是本次还是上次DFS过程中标记的accessd O, 如果是上次标记的，那么此次就不能够作为accessed的情况而应该直接返回false，需要额外加入excluded来区分。

与200.Number of Islands 对比，多了两个约束条件：

DFS过程中，不能采用像200题标记accessed一样，直接讲访问到的元素标记为X(因为本题对于是否形成O的“岛屿”是有条件的), 所以需要DFS顶层判true情况下，再对之前访问过的元素标记X，所以需要一个队列来保存DFS过程中访问过的元素。
边缘O，应该在DFS之后，连同与它连通的所有O标记为excluded，以便后续遍历过过程访问到后直接判为false。

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        if(board.empty())
            return;
        vector<vector<bool>> accessed(board.size(), vector<bool>(board[0].size(), false));
        vector<vector<bool>> excluded(board.size(), vector<bool>(board[0].size(), false));
        for(int i = 0; i < board.size(); i++){
            for(int j = 0; j < board[0].size(); j++){
                if(board[i][j] == 'O' && !accessed[i][j]){
                    if(helper(board, i, j, accessed, excluded)){
                        while(!v_x.empty() && !v_y.empty()){
                            board[v_y.back()][v_x.back()] = 'X';
                            v_y.pop_back();
                            v_x.pop_back();
                        }
                    }
                    else{
                        v_y.clear();
                        v_x.clear();
                    }
                }
            }
        }
        return;
    }
private:
    bool helper(vector<vector<char>>& board, int& g_y, int& g_x, vector<vector<bool>>& accessed, vector<vector<bool>>& excluded){
        accessed[g_y][g_x] = true;
        if(excluded[g_y][g_x])
            return false;
        //搜索到边缘的O,一定是联通到外面的，不满足条件
        if(g_y == 0 || g_y == board.size() - 1 || g_x == 0 || g_x == board[0].size() - 1){
            excluded[g_y][g_x] = true;
            return false;
        }
        //朝上下左右各尝试一步
        int ret = true;
        for(int i = 0; i < 4; i++){
            int new_y = g_y + next[i][0];
            int new_x = g_x + next[i][1];
            if(isArea(new_x, new_y, board)){
                if(board[new_y][new_x] == 'O'){
                    if(!accessed[new_y][new_x]){
                        if(!helper(board, new_y, new_x, accessed, excluded)){
                            ret = false;
                        }
                    }
                    else if(excluded[new_y][new_x]){
                        ret = false;
                    }
                }
            }
            else
                ret = false;
        }
        if(ret){
            v_y.push_back(g_y); v_x.push_back(g_x);
        }
        return ret;
    }
    bool isArea(int& x, int& y, vector<vector<char>>& board){
        return y >= 0 && y < board.size() && x >= 0 && x < board[0].size();
    }
    int next[4][2] = {{-1,0}, {1,0},{0, -1}, {0,1}};//上下左右
    vector<int> v_x;
    vector<int> v_y;
};
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
65
66
67
68

417. Pacific Atlantic Water Flow

Pacific ~ ~ ~ ~ ~

1 2 2 3 (5) *

3 2 3 (4) (4) *

2 4 (5) 3 1 *

(6) (7) 1 4 5 *

(5) 1 1 2 4 *

- - - - Atlantic

解法一：

与130题比较，这里应该是反过来，求与边缘连通的元素，约束条件：

必须是与上下边缘都连通的（DFS不需要返回值，遍历过程维护一个表示上下边缘是否被访问到的成员即可）
DFS的方向是有条件的，必须比当前元素小
优化，DFS过程可以访问到之前已经标记的元素，那么直接标记为连通的
加上了优化代码，还是超时，看了评论，只需要对四个边进行DFS,这样直接降低了复杂度到O(4n*DFS), n为边长。

class Solution {
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& matrix) {
        vector<vector<int>> ret;
        vector<int> point;

        if(matrix.empty())
            return ret;
  
        vector<vector<bool>> tmp(matrix.size(), vector<bool>(matrix[0].size(), false));
        vector<vector<bool>> accessd(matrix.size(), vector<bool>(matrix[0].size(), false));
        vector<vector<bool>> connected(matrix.size(), vector<bool>(matrix[0].size(), false));
        for(int i = 0; i < matrix.size(); i++){
            for(int j = 0; j < matrix[0].size(); j++){
                resValid[0] = false;
                resValid[1] = false;
                accessd = tmp;
                helper(matrix, i, j, accessd, connected);
                if(resValid[0] && resValid[1]){
                    connected[i][j] = true;
                    point.push_back(i);
                    point.push_back(j);
                    ret.push_back(point);
                    point.clear();
                }
            }
        }
        return ret;
    }
private:
    void helper(vector<vector<int>>& matrix, int& g_y, int& g_x, vector<vector<bool>>& accessd, vector<vector<bool>>& connected){
        accessd[g_y][g_x] = true;
        if(connected[g_y][g_x]){
            resValid[0] = true;
            resValid[1] = true;
            return;
        }
        //上边缘连通
        if(g_y == 0 || g_x == 0){
            resValid[0] = true;
        }
        //下边缘连通
        if(g_y == matrix.size() - 1 || g_x == matrix[0].size() - 1 ){
            resValid[1] = true;
        }
        if(resValid[0] && resValid[1])
            return;
        //朝上下左右各尝试一步
        for(int i = 0; i < 4; i++){
            int new_y = g_y + next[i][0];
            int new_x = g_x + next[i][1];
            if(isArea(new_x, new_y, matrix) && isFlow(g_x, g_y, new_x, new_y, matrix)){
                if(!accessd[new_y][new_x]){
                    helper(matrix, new_y, new_x, accessd, connected);
                }
            }
        }
    }
    bool isArea(int& x, int& y, vector<vector<int>>& matrix){
        return y >= 0 && y < matrix.size() && x >= 0 && x < matrix[0].size();
    }
    bool isFlow(int& x, int& y, int& new_x, int& new_y, vector<vector<int>>& matrix){
        return matrix[new_y][new_x] <= matrix[y][x];
    }
    int next[4][2] = {{-1,0}, {1,0},{0, -1}, {0,1}};//上下左右
    bool resValid[2] = {false, 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
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
65
66
67

解法二：

class Solution {
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& matrix) {
        vector<vector<int>> ret;
        vector<int> point;

        if(matrix.empty())
            return ret;
  
        vector<vector<bool>> Pacific(matrix.size(), vector<bool>(matrix[0].size(), false));
        vector<vector<bool>> Atlantic(matrix.size(), vector<bool>(matrix[0].size(), false));
        for(int i = 0; i < matrix.size(); i++){
            for(int j = 0; j < matrix[0].size(); j++){
                //Pacific 
                if((i == 0 || j == 0) && !Pacific[i][j]) {
                    helper(matrix, i, j, Pacific);
                }
                //Atlantic
                if((i == matrix.size() - 1 || j == matrix[0].size() - 1 ) && !Atlantic[i][j]){
                    helper(matrix, i, j, Atlantic);
                }
            }
        }
        for(int i = 0; i < matrix.size(); i++){
            for(int j = 0; j < matrix[0].size(); j++){
                if(Pacific[i][j] == true && Atlantic[i][j] == true){
                    //cout << i << " " << j << " " << Atlantic[i][j] << " " << Pacific[i][j] << " ";
                    point.push_back(i);
                    point.push_back(j);
                    ret.push_back(point);
                    point.clear();
                }
            }
            //cout << endl;
        }
        return ret;
    }
private:
    void helper(vector<vector<int>>& matrix, int& g_y, int& g_x, vector<vector<bool>>& ocean){
        //cout << g_y << " " << g_x << endl;
        ocean[g_y][g_x] = true;
        //逆向爬坡，DFS方向为比自己数字大的方向
        for(int i = 0; i < 4; i++){
            int new_y = g_y + next[i][0];
            int new_x = g_x + next[i][1];
            if(isArea(new_x, new_y, matrix) && isFlow(g_x, g_y, new_x, new_y, matrix)){
                if(!ocean[new_y][new_x]){
                    helper(matrix, new_y, new_x, ocean);
                }
            }
        }
    }
    bool isArea(int& x, int& y, vector<vector<int>>& matrix){
        return y >= 0 && y < matrix.size() && x >= 0 && x < matrix[0].size();
    }
    bool isFlow(int& x, int& y, int& new_x, int& new_y, vector<vector<int>>& matrix){
        return matrix[new_y][new_x] >= matrix[y][x];
    }
    int next[4][2] = {{-1,0}, {1,0},{0, -1}, {0,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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

51. N-Queens

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.Given an integer n, return all distinct solutions to the n-queens puzzle.
Input: 4
Output: [
[".Q…", // Solution 1
“…Q”,
“Q…”,
“…Q.”],

["…Q.", // Solution 2
“Q…”,
“…Q”,
“.Q…”]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

二维回溯的变形，row是递归深度，col是回溯后操作的对象。
在二维回溯的基础上增加了判断棋盘是否已经attacked的业务逻辑，其中判断的方法需要有一定设计技巧才能够得到较好的时间复杂度。
需要返回棋盘数组，为这道题增加了点难度。

class Solution {
public:
    //helper(n, 0, attacked), n*n的棋盘，从第0行开始递归，遍历其中的n列, n列都搜索不到，返回false。
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> ret;
        vector<string> board;
        //vector<vector<int>> attacked(n, vector<int>(n, 0));
        colUsed = vector<bool>(n, false);
        diag1Used = vector<bool>(2*n - 1, false);
        diag2Used = vector<bool>(2*n - 1, false);
        if(n <= 0) 
            return ret;
        //helper(n, 0, attacked, board, ret);
        helper(n, 0, board, ret);
        return ret;
    }
private:
    void helper(int& n, int row, vector<string>& board, vector<vector<string>>& ret){
        if(row == n){
            ret.push_back(board);
            return;
        }
        //在本行中选中一个列放置Q, 不能与其他Q冲突。
        for(int col = 0; col < n; col++){
            if(!colUsed[col] && !diag1Used[row + col] && !diag2Used[n - 1 + row - col]){
                string s(n, '.');
                s.replace(col, 1, string(1,'Q'));
                board.push_back(s);
                updateAttacked(n, row, col, colUsed, diag1Used, diag2Used, true);
                helper(n, row + 1, board, ret);
                board.pop_back();
                updateAttacked(n, row, col, colUsed, diag1Used, diag2Used, false);
            }
        }
        return;
    }
    //判断对角线和列是否被占用，时间复杂度需要优化
    /*
    void updateAttacked(vector<vector<int>>& attacked, int& row, int& col, int set){
        for(int i = 0; i < attacked.size(); i++){
            for(int j = 0; j < attacked[0].size(); j++){
                if(j == col || i + j == row + col || i - j == row - col){
                    attacked[i][j] += set; 
                }
            }
        }
    }*/
    //判断对角线和列是否被占用的优化
    void updateAttacked(int& n, int& row, int& col, vector<bool>& colUsed, vector<bool>& diag1Used, vector<bool>& diag2Used, bool set){
        colUsed[col] = set;
        diag1Used[row + col] = set;
        diag2Used[n - 1 + row - col] = set;
    }
    //求解对角线和列是否被占用
    vector<bool> colUsed;
    vector<bool> diag1Used;
    vector<bool> diag2Used;
};
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

52. N-Queens II

和51题完全一样，只需要返回放置得数量

class Solution {
public:
    int totalNQueens(int n) {
        int ret = 0;
        colUsed = vector<bool>(n, false);
        diag1Used = vector<bool>(2*n - 1, false);
        diag2Used = vector<bool>(2*n - 1, false);
        if(n <= 0) 
            return ret;
        helper(n, 0, ret);
        return ret;
    }
private:
    void helper(int& n, int row, int& ret){
        if(row == n){
            ret += 1;
            return;
        }
        //在本行中选中一个列放置Q, 不能与其他Q冲突。
        for(int col = 0; col < n; col++){
            if(!colUsed[col] && !diag1Used[row + col] && !diag2Used[n - 1 + row - col]){
                updateAttacked(n, row, col, colUsed, diag1Used, diag2Used, true);
                helper(n, row + 1, ret);
                updateAttacked(n, row, col, colUsed, diag1Used, diag2Used, false);
            }
        }
        return;
    }
    void updateAttacked(int& n, int& row, int& col, vector<bool>& colUsed, vector<bool>& diag1Used, vector<bool>& diag2Used, bool set){
        colUsed[col] = set;
        diag1Used[row + col] = set;
        diag2Used[n - 1 + row - col] = set;
    }
    //求解对角线和列是否被占用
    vector<bool> colUsed;
    vector<bool> diag1Used;
    vector<bool> diag2Used;
};
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

位运算？
DFS剪枝？

36. Valid Sudoku

乱入一个非递归题型，37题需要用到这道题的hashtable.

用vector<map<char, bool>>，只需要一次遍历，就可以将 [i, j] 元素记录在行、列、块索引上面的hashtable上。
其中块的索引公式为：box = (i / 3) * 3 + j / 3

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        vector<map<char, bool>> rowmap(board.size(), map<char, bool>());
        vector<map<char, bool>> colmap(board.size(), map<char, bool>());
        vector<map<char, bool>> boxmap(board.size(), map<char, bool>());    
        for(int i = 0; i < board.size(); i++){
            for(int j = 0; j < board[0].size(); j++){
                if(board[i][j] == '.')
                    continue;

                if(rowmap[i][board[i][j]])
                    return false;
                rowmap[i][board[i][j]] = true;

                if(colmap[j][board[i][j]])
                    return false;
                colmap[j][board[i][j]] = true;

                if(boxmap[(i / 3) * 3 + j / 3][board[i][j]])
                    return false;
                boxmap[(i / 3) * 3 + j / 3][board[i][j]] = true;
            }
        }
        return true;
    }
};
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

37. Sudoku Solver

仔细看参数列表有没有写错，以免发生错误的时候不符合逻辑，都不好定位哪里错了。
这里参数传递优化的时候用了原生的int[][]，需要注意下作为参数传递时候的写法：int (&boxmap)[9][9]
带点总结：递归向是二维数组遍历方向，每个格子迭代的’1‘ - ’9‘是回溯选择的对象。

class Solution {
public:
    //递归的方向是正常的二位数组遍历方向，每个格子数字取值就是回溯操作的对象。
    void solveSudoku(vector<vector<char>>& board) {
        int rowmap[9][9] = {0};
        int colmap[9][9] = {0};
        int boxmap[9][9] = {0};
        for(int i = 0; i < board.size(); i++){
            for(int j = 0; j < board[0].size(); j++){
                if(board[i][j] != '.'){
                    rowmap[i][board[i][j] - '1'] = 1;
                    colmap[j][board[i][j] - '1'] = 1;
                    boxmap[(i / 3) * 3 + j / 3][board[i][j] - '1'] = 1;
                }
            }
        }
         helper(board, 0, 0, rowmap, colmap, boxmap);
    }
    private:
    bool helper(vector<vector<char>>& board, int row, int col, int (&rowmap)[9][9] , int (&colmap)[9][9], int (&boxmap)[9][9]){
        while (row < board.size() && board[row][col] != '.') {
            row = row + (col + 1) / 9;
            col = (col + 1) % 9;
        }
        if (row == board.size()) {
            return true;
        }
        for(char c = '1'; c <= '9'; c++){
            if(!rowmap[row][c - '1'] && !colmap[col][c - '1'] && !boxmap[(row / 3) * 3 + col / 3][c - '1']){
                board[row][col] = c;
                rowmap[row][c - '1'] = true;
                colmap[col][c - '1'] = true;
                boxmap[(row / 3) * 3 + col / 3][c - '1'] = true;
                if(helper(board, row + (col + 1) / 9, (col + 1) % 9, rowmap, colmap, boxmap)){
                    return true;
                }
                rowmap[row][c - '1'] = false;
                colmap[col][c - '1'] = false;
                boxmap[(row / 3) * 3 + col / 3][c - '1'] = false;
                board[row][col] = '.';
            }
        }
        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
38
39
40
41
42
43
44
45

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Cpp五条/article/detail/590465

回溯和递归 - 归档_递归返回上一层

LeetCode - 回溯和递归

概述

树形递归

51. N-Queens (约束)

52. N-Queens II (约束)

36. Valid Sudoku (约束)

37. Sudoku Solver (约束)

17. Letter Combinations of a Phone Number

93. Restore IP Addresses

131. Palindrome Partitioning

46. Permutations

47. Permutations II

77. Combinations

39. Combination Sum

40. Combination Sum II

216. Combination Sum III

78. Subsets

90. Subsets II

401. Binary Watch

79. Word Search

200. Numer of Islands

130. Surrounded Regions

417. Pacific Atlantic Water Flow

51. N-Queens

52. N-Queens II

36. Valid Sudoku

37. Sudoku Solver