【算法篇】回溯算法类（2）（笔记）

news/2024/12/22 1:07:28/

目录

一、LeetCode 题目

1. 子集II

2. 递增子序列

3. 全排列

4. 全排列 II

5. 重新安排行程

6. N皇后

7. 解数独

二、题目思路整理

一、LeetCode 题目

1. 子集II

https://leetcode.cn/problems/subsets-ii/description/icon-default.png?t=O83Ahttps://leetcode.cn/problems/subsets-ii/description/

        给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例 1：
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]示例 2：
输入：nums = [0]
输出：[[],[0]]

// 方法一：
class Solution {
public:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& nums, int startIndex) {result.push_back(path);for (int i = startIndex; i < nums.size(); i++) {if (i > startIndex && nums[i] == nums[i - 1]) {continue;}path.push_back(nums[i]);backtracking(nums, i + 1);path.pop_back();}return;}vector<vector<int>> subsetsWithDup(vector<int>& nums) {sort(nums.begin(), nums.end());backtracking(nums, 0);return result;}
};// 方法二：（unordered_set 的使用）
class Solution {
public:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& nums, int startIndex) {result.push_back(path);unordered_set<int> uset;for (int i = startIndex; i < nums.size(); i++) {if (uset.find(nums[i]) != uset.end()) {continue;}uset.insert(nums[i]);path.push_back(nums[i]);backtracking(nums, i + 1);path.pop_back();}return;}vector<vector<int>> subsetsWithDup(vector<int>& nums) {sort(nums.begin(), nums.end());backtracking(nums, 0);return result;}
};

2. 递增子序列

https://leetcode.cn/problems/non-decreasing-subsequences/description/icon-default.png?t=O83Ahttps://leetcode.cn/problems/non-decreasing-subsequences/description/

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

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

示例 1：
输入：nums = [4,6,7,7]
输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]示例 2：
输入：nums = [4,4,3,2,1]
输出：[[4,4]]

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);}unordered_set<int> uset; // 使用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]); // 记录这个元素在本层用过了，本层后面不能再用了path.push_back(nums[i]);backtracking(nums, i + 1);path.pop_back();}}
public:vector<vector<int>> findSubsequences(vector<int>& nums) {backtracking(nums, 0);return result;}
};

3. 全排列

https://leetcode.cn/problems/permutations/description/icon-default.png?t=O83Ahttps://leetcode.cn/problems/permutations/description/

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

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

class Solution {
public:vector<vector<int>> result;vector<int> path;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;}path.push_back(nums[i]);used[i] = true;backtracking(nums, used);path.pop_back();used[i] = false;}return;}vector<vector<int>> permute(vector<int>& nums) {vector<bool> used(nums.size(), false);backtracking(nums, used);return result;}
};

4. 全排列 II

https://leetcode.cn/problems/permutations-ii/description/icon-default.png?t=O83Ahttps://leetcode.cn/problems/permutations-ii/description/

        给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],[1,2,1],[2,1,1]]示例 2：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
class Solution {
public:vector<vector<int>> result;vector<int> path;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 (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {  // 如果上一个数还没用，那么选择第i个和上一个没什么区别continue;}if (used[i] == false) {path.push_back(nums[i]);used[i] = true;backtracking(nums, used);path.pop_back();used[i] = false;}}return;}vector<vector<int>> permuteUnique(vector<int>& nums) {vector<bool> used(nums.size(), false);sort(nums.begin(), nums.end());backtracking(nums, used);return result;}
};

        树层上去重(used[ i - 1 ] == false)，的树形结构如下：

        树枝上去重（used[ i - 1 ] == true）的树型结构如下：

5. 重新安排行程

https://leetcode.cn/problems/reconstruct-itinerary/description/icon-default.png?t=O83Ahttps://leetcode.cn/problems/reconstruct-itinerary/description/

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

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

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

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

示例 1：
输入：tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
输出：["JFK","MUC","LHR","SFO","SJC"]

示例 2：
输入：tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
输出：["JFK","ATL","JFK","SFO","ATL","SFO"]
解释：另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"] ，但是它字典排序更大更靠后。
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 ) { // 记录到达机场是否飞过了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;}
};

6. N皇后

https://leetcode.cn/problems/n-queens/description/icon-default.png?t=O83Ahttps://leetcode.cn/problems/n-queens/description/

        按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

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

示例 1：
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。示例 2：
输入：n = 1
输出：[["Q"]]

class Solution {
public: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] = '.';}}return;}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;}// 比较45度for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {if (chessboard[i][j] == 'Q') return false;}// 比较135度for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {if (chessboard[i][j] == 'Q') return false;}return true;}vector<vector<string>> solveNQueens(int n) {vector<string> chessboard(n, string(n, '.'));backtracking(n, 0, chessboard);return result;}
};

7. 解数独

https://leetcode.cn/problems/sudoku-solver/description/icon-default.png?t=O83Ahttps://leetcode.cn/problems/sudoku-solver/description/

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

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

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

        数独部分空格内已填入了数字，空白格用 '.' 表示。

示例 1：
输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

思路：

        一个 for 循环遍历棋盘的行，一个for循环遍历棋盘的列，一行一列确定下来之后，递归遍历这个位置放9个数字的可能性

// 写法一：
class Solution {
public: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] == '.') {for (char k = '1'; k <= '9'; k++) { if (isValid(board, i, j, k)) {board[i][j] = k;if (backtracking(board)) return true; // 如果找到合适一组立刻返回board[i][j] = '.';}}return false;  // 9个数都试完了，都不行，返回false}}}return true; // 遍历完没有返回false，说明找到了合适棋盘位置了}bool isValid(vector<vector<char>>& board, int row, int col, char key) {// 检查行for (int i = 0; i < 9; i++) {if (board[row][i] == key) return false;}// 检查列for (int i = 0; i < 9; i++) {if (board[i][col] == key) return false;}// 检查四方格int rows = row / 3;int cols = col / 3;for (int i = 3 * rows; i < 3 * rows + 3; i++) {for (int j = 3 * cols; j < 3 * cols + 3; j++) {if (board[i][j] == key) return false;}}return true;}void solveSudoku(vector<vector<char>>& board) {backtracking(board);return;}
};// 写法二：
class Solution {
public: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] == '.') {   // 递归的上一层已经填上一个数字了，所以这里这里直接跳过了for (char k = '1'; k <= '9'; k++) { if (isValid(board, i, j, k)) {board[i][j] = k;if (backtracking(board)) return true; // 如果找到合适一组立刻返回board[i][j] = '.';}}return false;  // 9个数都试完了，都不行，返回false}}}return true; // 遍历完没有返回false，说明找到了合适棋盘位置了}bool isValid(vector<vector<char>>& board, int row, int col, char key) {// 检查行for (int i = 0; i < 9; i++) {if (board[row][i] == key) return false;}// 检查列for (int i = 0; i < 9; i++) {if (board[i][col] == key) return false;}// 检查四方格int rows = row / 3;int cols = col / 3;for (int i = 3 * rows; i < 3 * rows + 3; i++) {for (int j = 3 * cols; j < 3 * cols + 3; j++) {if (board[i][j] == key) return false;}}return true;}void solveSudoku(vector<vector<char>>& board) {backtracking(board);return;}
};

二、题目思路整理


http://www.ppmy.cn/news/1536432.html

相关文章

erlang学习:Linux命令学习9

erlang学习:Linux命令学习9

sed命令介绍 sed全称是&#xff1a;Stream EDitor&#xff08;流编辑器&#xff09; Linux sed 命令是利用脚本来处理文本文件&#xff0c;sed 可依照脚本的指令来处理、编辑文本文件。Sed 主要用来自动编辑一个或多个文件、简化对文件的反复操作、编写转换程序等 sed 的运行…
阅读更多...
Qt QWidget控件

Qt QWidget控件

目录 一、概述 二、Qwidget常用属性及函数介绍 2.1 enable 2.2 geometry 2.3 windowTitle 2.4 windowIcon 2.5 cursor 2.6 font 设置字体样式 2.7 toolTip 2.8 focusPolicy焦点策略 2.9 styleSheet 一、概述 widget翻译而来就是小控件&#xff0c;小部件。…
阅读更多...
linux文件编程_文件

linux文件编程_文件

1. 文件编程概述 之前在windows中对文件的操作是&#xff1a;打开文档—>编辑文档—>保存文档—>关闭文档 我们的Linux文件编程主要是利用代码对文件进行操作&#xff1a;文件创建、打开、编辑等自动化执行等 在Linux我们要使用编程调用api函数的方式进行文档的编辑…
阅读更多...
Python获取json返回的字符串获取方法大全

Python获取json返回的字符串获取方法大全

1、使用 json.loads() 解析JSON字符串 import jsonjson_string {"name": "Alice", "age": 25, "city": "Beijing"} data json.loads(json_string)# 获取字符串值 name data[name] print("Name:", name) # 输…
阅读更多...
✨机器学习笔记（六）—— ReLU、多分类问题、Softmax、Adam、反向传播

✨机器学习笔记（六）—— ReLU、多分类问题、Softmax、Adam、反向传播

Course2-Week2: https://github.com/kaieye/2022-Machine-Learning-Specialization/tree/main/Advanced%20Learning%20Algorithms/week2机器学习笔记&#xff08;六&#xff09; 1️⃣ReLU&#xff08;Rectified Linear Unit&#xff09;2️⃣多分类问题3️⃣Softmax4️⃣Adam5…
阅读更多...
如何实现 C/C++ 与 Python 的通信？

如何实现 C/C++ 与 Python 的通信？

在现代编程中&#xff0c;C/C与Python的通信已经成为一种趋势&#xff0c;尤其是在需要高性能和灵活性的场景中。本文将深入探讨如何实现这两者之间的互通&#xff0c;包括基础和高级方法&#xff0c;帮助大家在混合编程中游刃有余。 C/C 调用 Python&#xff08;基础篇&#…
阅读更多...
JAVA就业笔记3——第一阶段（3）

JAVA就业笔记3——第一阶段（3）

课程须知 A类知识&#xff1a;工作和面试常用&#xff0c;代码必须要手敲&#xff0c;需要掌握。 B类知识&#xff1a;面试会问道&#xff0c;工作不常用&#xff0c;代码不需要手敲&#xff0c;理解能正确表达即可。 C类知识&#xff1a;工作和面试不常用&#xff0c;代码不…
阅读更多...
【多重循环在Java中的应用】

【多重循环在Java中的应用】

多重循环在Java中的应用 介绍 多重循环是将一个循环嵌套在另一个循环体内的编程结构。Java中的 for、while 和 do...while 循环均可作为外层循环和内层循环。建议使用两层嵌套&#xff0c;最多不超过三层&#xff0c;以保持代码的可读性。 在多重循环中&#xff0c;外层循环执…
阅读更多...
最新文章

Copyright @ 2022~2023