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

目录

一、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.mfbz.cn/a/886551.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【C++】类与对象基础概念解析

【C++】类与对象基础概念解析

恭喜你学习完C语言与数据结构的有关内容&#xff0c;现在让我们开始进行对C的学习吧~ &#x1f49d;&#x1f49d;&#x1f49d;如果你对C语言或数据结构还存在疑惑&#xff0c;欢迎观看我之前的作品 &#x1f449;【数据结构】 &#x1f449;【C语言】 目录 一、引言 二、类…
阅读更多...
MapBox Android版开发 6 关于Logo

MapBox Android版开发 6 关于Logo

MapBox Android版开发 6 关于Logo Logo的显示查看源码及思路&#xff08;Logo&#xff09;第一步第二步 隐藏Logo示例查看源码及思路&#xff08;Info&#xff09;第一步第二步 隐藏Logo和Info示例 看到有网友留言问如何移除Logo&#xff0c;今天看了下V9源码&#xff0c;发现M…
阅读更多...
CORE MVC 过滤器 （筛选器）《2》 TypeFilter、ServiceFilter

CORE MVC 过滤器 （筛选器）《2》 TypeFilter、ServiceFilter

TypeFilter、ServiceFilter ServiceFilter vs TypeFilter ServiceFilter和TypeFilter都实现了IFilterFactory ServiceFilter需要对自定义的Filter进行注册&#xff0c;TypeFilter不需要 ServiceFilter的Filter生命周期源自于您如何注册&#xff08;全局、区域&#xff09;&…
阅读更多...
Ps：打开与置入

Ps：打开与置入

在 Adobe Photoshop 中&#xff0c;理解不同的“打开”和“置入”命令及其用途&#xff0c;可以根据不同的需求选择最佳方式来管理和编辑图像文件。 ◆ ◆ ◆ 打开 1、Ps菜单&#xff1a;文件/打开 File/Open 快捷键&#xff1a;Ctrl O 用于直接打开现有的图像文件。 打开的…
阅读更多...
【HDP】zookeeper未授权漏洞修复

【HDP】zookeeper未授权漏洞修复

目录 一、禁用四字命令 二、ZK-Client增加kerberos 一、禁用四字命令 Zookeeper四字命令的使用方式非常简单&#xff0c;通常有两种方式。第一种是通过Telnet方式&#xff0c;使用Telnet客户端登录ZooKeeper的对外服务端口&#xff0c;然后直接使用四字命令即可&#xff1b;第…
阅读更多...
计算机网络-系分（5）

计算机网络-系分（5）

目录 计算机网络 DNS解析 DHCP动态主机配置协议 网络规划与设计 层次化网络设计 网络冗余设计 综合布线系统 1. 双栈技术 2. 隧道技术 3. 协议转换技术 其他网络技术 DAS&#xff08;Direct Attached Storage&#xff0c;直连存储&#xff09; NAS&#xff08;Net…
阅读更多...
centos环境安装JDK详细教程

centos环境安装JDK详细教程

centos环境安装JDK详细教程 一、前期准备二、JDK安装2.1 rpm方式安装JDK2.2 zip方式安装JDK2.3 yum方式安装JDK 本文主要说明CentOS下JDK的安装过程。JDK的安装有三种方式&#xff0c;用户可根据实际情况选择&#xff1a; 一、前期准备 查看服务器操作系统型号&#xff0c;执…
阅读更多...
【Android 14源码分析】Activity启动流程-3

【Android 14源码分析】Activity启动流程-3

忽然有一天&#xff0c;我想要做一件事&#xff1a;去代码中去验证那些曾经被“灌输”的理论。                                                                                  – 服装…
阅读更多...
鸿蒙harmonyos next纯flutter开发环境搭建

鸿蒙harmonyos next纯flutter开发环境搭建

公司app是用纯flutter开发的&#xff0c;目前支持android和iOS&#xff0c;后续估计也会支持鸿蒙harmonyos。目前谷歌flutter并没有支持咱们国产手机操作系统鸿蒙harmonyos&#xff0c;于是乎国内有个叫OpenHarmony-SIG的组织&#xff0c;去做了鸿蒙harmonyos适配flutter开发的…
阅读更多...
安卓主板_MTK4G/5G音视频记录仪整机及方案定制

安卓主板_MTK4G/5G音视频记录仪整机及方案定制

音视频记录仪方案&#xff0c;采用联发科MT6877平台八核2* A78 6* A55主频高达2.4GHz, 具有高能低耗特性&#xff0c;搭载Android 12.0智能操作系统&#xff0c;可选4GB32GB/6GB128GB内存&#xff0c;运行流畅。主板集成NFC、双摄像头、防抖以及多种无线数据连接&#xff0c;支…
阅读更多...
【web安全】——sql注入

【web安全】——sql注入

1.MySQL基础 1.1information_schema数据库详解 简介&#xff1a; 在mysql5版本以后&#xff0c;为了方便管理&#xff0c;默认定义了information_schema数据库&#xff0c;用来存储数据库元数据信息。schemata(数据库名)、tables(表名tableschema)、columns(列名或字段名)。…
阅读更多...
java设计模式介绍

java设计模式介绍

常见的设计模式有哪些呢&#xff1f; 单例模式&#xff08;Singleton Pattern&#xff09;&#xff1a; 就像是武林中的“独孤求败”&#xff0c;一个类只有一个实例&#xff0c;并提供一个全局访问点。 常用于需要控制资源访问的场景&#xff0c;比如数据库连接池。 工厂模式…
阅读更多...
828华为云征文｜部署音乐流媒体服务器 mStream

828华为云征文｜部署音乐流媒体服务器 mStream

828华为云征文&#xff5c;部署音乐流媒体服务器 mStream 一、Flexus云服务器X实例介绍二、Flexus云服务器X实例配置2.1 重置密码2.2 服务器连接2.3 安全组配置2.4 Docker 环境搭建 三、Flexus云服务器X实例部署 mStream3.1 mStream 介绍3.2 mStream 部署3.3 mStream 使用 四、…
阅读更多...
51c自动驾驶~合集1

51c自动驾驶~合集1

我自己的原文哦~ https://blog.51cto.com/whaosoft/11466109 #HTCL 超过所有视觉方案&#xff01;HTCL&#xff1a;分层时间上下文问鼎OCC 本文是对ECCV2024接受的文章 HTCL: 的介绍&#xff0c;HTCL在SemanticKITTI基准测试中超过了所有基于相机的方法&#xff0c;甚至在和…
阅读更多...
java中创建不可变集合

java中创建不可变集合

一.应用场景 二.创建不可变集合的书写格式&#xff08;List&#xff0c;Set&#xff0c;Map) List集合 package com.njau.d9_immutable;import java.util.Iterator; import java.util.List;/*** 创建不可变集合:List.of()方法* "张三","李四","王五…
阅读更多...
每日OJ题_牛客_游游的水果大礼包_枚举_C++_Java

每日OJ题_牛客_游游的水果大礼包_枚举_C++_Java

目录 牛客_游游的水果大礼包 题目解析 C代码 Java代码 牛客_游游的水果大礼包 游游的水果大礼包 (nowcoder.com) 描述&#xff1a; 游游有n个苹果&#xff0c;m个桃子。她可以把2个苹果和1个桃子组成价值a元的一号水果大礼包&#xff0c;也可以把1个苹果和2个桃子…
阅读更多...
拆解维修飞科剃须刀

拆解维修飞科剃须刀

原因 用了好几年的剃须刀&#xff0c;经过一次更换电池。后来上面的盖帽松动&#xff0c;无法合盖&#xff0c;经过把弹片矫正后修复。最近一次”大力出奇迹“的操作直接断送了这个老伤员最后的可能性。最终只能花了将近十块大洋买了一套盖着和中间座。简单更换了一下。 记录…
阅读更多...
Unity NetCode 客户端连接不上服务器，局域网模式 Failed to connect to server.

Unity NetCode 客户端连接不上服务器，局域网模式 Failed to connect to server.

报错代码: Failed to connect to server. 报错截图&#xff1a; 解决办法: 服务端:绑定127.0.0.1和端口 客户端:写好对应服务端ip和端口 如何查看服务端所在局域网IP&#xff0c;192.xxx.xxx.xx,就不用教了吧。 注意这个钩&#xff0c;得点下&#xff0c;默认不勾选。 意…
阅读更多...
【注册/登录安全分析报告：孔夫子旧书网】

【注册/登录安全分析报告：孔夫子旧书网】

前言 由于网站注册入口容易被黑客攻击&#xff0c;存在如下安全问题&#xff1a; 暴力破解密码&#xff0c;造成用户信息泄露短信盗刷的安全问题&#xff0c;影响业务及导致用户投诉带来经济损失&#xff0c;尤其是后付费客户&#xff0c;风险巨大&#xff0c;造成亏损无底洞…
阅读更多...
docker运行arm64架构的镜像、不同平台镜像构建

docker运行arm64架构的镜像、不同平台镜像构建

背景 Docker 允许开发者将应用及其依赖打包成一个轻量级、可移植的容器&#xff0c;实现“一次构建&#xff0c;到处运行”的目标。然而&#xff0c;不同的操作系统和硬件架构对容器镜像有不同的要求。例如&#xff0c;Linux 和 Windows 系统有不同的文件系统和系统调用&#…
阅读更多...
最新文章

Copyright @ 2022~2023