字数统计: 1.8k字   |   阅读时长: 8分

回溯 (2)

491. 递增子序列 - 力扣（LeetCode） (leetcode-cn.com)

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

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 {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int> &nums, int startIndex)
    {
        if(path.size() > 1)
        {
        result.push_back(path);
        //return;不能加入return，否则只能返回包含两个元素的数组集合
        }
        unordered_set <int> uset; //unordered_set进行去重
        for(int i = startIndex; i < nums.size(); i++)
        {
            if((!path.empty() && nums[i] < path.back()) ||(uset.find(nums[i]) != uset.end()))//前面的判断条件要求序列递增，后面的判断要求
            continue;
            uset.insert(nums[i]); //nums[i] 在本层用过了，本次循环的后面元素就不能为nums[i]了
            path.push_back(nums[i]);
            backtracking(nums, i + 1);
            path.pop_back();
        }
    }
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        result.clear();
        path.clear();
        backtracking(nums, 0);
        return result;
    }
};

46. 全排列 - 力扣（LeetCode） (leetcode-cn.com)

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

1
2
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

这个问题是组合问题，首先排列是有序的，也就是说 [1,2] 和 [2,1] 是两个集合，这和之前分析的子集以及组合所不同的地方。

可以看出元素1在[1,2]中已经使用过了，但是在[2,1]中还要在使用一次1，所以处理排列问题就不用使用startIndex了。

但排列问题需要一个used数组，标记已经选择的元素

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 {
private:
    vector<int> path;
    vector<vector<int>> result;
    void backtracking(vector<int> &nums, vector <bool> used)
    {
        if(path.size() == nums.size())
        {
            result.push_back(path);
            return;
        }
        for(int i = 0; i < nums.size(); i++)
        {
            if(used[i] == true) continue;
            used[i] = true;
            path.push_back(nums[i]);
            backtracking(nums, used);
            path.pop_back();
            used[i] = false;
        }
    }
public:
    vector<vector<int>> permute(vector<int>& nums) {
        path.clear();
        result.clear();
        vector <bool> used(nums.size(), false);
        backtracking(nums, used);
        return result; 
    }
};

332. 重新安排行程 - 力扣（LeetCode） (leetcode-cn.com)

给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。

所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。

  • 例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。

假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。

1
2
输入：tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
输出：["JFK","MUC","LHR","SFO","SJC"]
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 {
private:
    // unordered_map<出发机场, map<到达机场, 航班次数>> targets
    unordered_map<string, map<string, int>> targets;
    bool backtracking(int ticketNum, vector <string> &result)
    {
        if(result.size() == ticketNum + 1)
        {
            return true;
        }
        for(pair<const string, int> &target : targets[result[result.size() - 1]])   //每个出发机场对应的到达机场和航班次数
        {
            if(target.second > 0) //如果对应的航班次数不为0，说明这个目的地址是可以从上一个地址直接到的
            {
                result.push_back(target.first);
                target.second--;
                if(backtracking(ticketNum, result))
                return true;
                result.pop_back();
                target.second++;
            }
        }
        return false;
    }
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        targets.clear();
        vector<string> result;
        for(const vector<string> &vec : tickets)
        {
            targets[vec[0]][vec[1]]++; //记录下原车站到目的车站，对应的航班次数有几次
        }
        result.push_back("JFK");
        backtracking(tickets.size(), result);
        return result;
    }
};

51. N 皇后 - 力扣（LeetCode） (leetcode-cn.com)

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

1
2
3
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，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
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
private:
    vector<vector<string>> result;
    void backtracking(int n, int row, vector <string> &chessboard)
    {
        if(row == n)
        {
        result.push_back(chessboard);
        return;
        }
        for(int col = 0; col < n; col++)
        {
            if(isValid(row, col, chessboard, n))
            {
                chessboard[row][col] = 'Q';
                backtracking(n, row + 1, chessboard);
                chessboard[row][col] = '.';
            }
        }
    }
    bool isValid(int row, int col, vector <string> &chessboard, int n)
    {
        for(int i = 0; i < row; i++)
        {
            if(chessboard[i][col] == 'Q')
            return false;
        }
        //判断左上方有无皇后
        for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
        {
            if(chessboard[i][j] == 'Q')
            return false;
        }
        //判断右上方有无皇后
        for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++)
        {
            if(chessboard[i][j] == 'Q')
            return false;
        }
        return true;
    }
public:
    vector<vector<string>> solveNQueens(int n) {
        result.clear();
        vector <string> chessboard(n, string(n, '.'));
        backtracking(n, 0, chessboard);
        return result;
    } 
};

37. 解数独 - 力扣（LeetCode） (leetcode-cn.com)

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 '.' 表示。

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 {
private:
    bool backtracking(vector <vector<char>> &board)
    {
        for(int i = 0; i < board.size(); i++)   //遍历行
        {
            for(int j = 0; j < board[0].size(); j++)
            {
                if(board[i][j] != '.') continue;
                for(char k = '1'; k <= '9'; k++)
                {
                    if(isValid(i, j, k, board))
                    {
                        board[i][j] = k;
                        if(backtracking(board)) return true;
                        board[i][j] = '.';
                    }
                }
                return false;
            }
        }
        return true;
    }
    bool isValid(int row,int col,char k, vector<vector<char>> &board)
    {
        for(int i = 0; i < 9; i++)
        {
            if(board[i][col] == k)	//判断行不能重复
            return false;	//判断列不能重复
        }
        for(int j = 0; j < 9; j++)
        {
            if(board[row][j] == k)
            return false;
        }
        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;
        for(int i = startRow; i < startRow + 3; i++)
        {
            for(int j = startCol; j < startCol + 3; j++)	//判断九宫格内数字不能重复
            {
                if(board[i][j] == k)
                return false;
            }
        }
        return true;
    }
public:
    void solveSudoku(vector<vector<char>>& board) {
        backtracking(board);
    }
};

扫一扫，分享到微信

微信分享二维码
本站总访问量次 |

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

这一定是一个<br><br>很长很长的一生啊