Day31 46全排列 47全排列II 回溯去重tips 51N皇后 37解数独

46 全排列

给定一个 没有重复 数字的序列,返回其所有可能的全排列。

示例:

  • 输入: [1,2,3]
  • 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

 排列问题与组合问题的不同之处就在于,没有startIndex,同时需要设置一个used数组,遍历过的就设置成true,下次遇到时跳过。

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里已经收录的元素,直接跳过
            used[i] = true;
            path.push_back(nums[i]);
            backtracking(nums, used);
            path.pop_back();
            used[i] = false;
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        result.clear();
        path.clear();
        vector<bool> used(nums.size(), false);
        backtracking(nums, used);
        return result;
    }
};

 47 全排列II

给定一个可包含重复数字的序列 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]]

提示:

  • 1 <= nums.length <= 8
  • -10 <= nums[i] <= 10

        本题与上一题的不同之处就在于本题利用了树层去重的逻辑,其余一模一样,但是本题的去重逻辑中,如果used【i-1】==true时,也能提交成功,但是效率会低:

false:

true: 

         大家应该很清晰的看到,树层上对前一位去重非常彻底,效率很高,树枝上对前一位去重虽然最后可以得到答案,但是做了很多无用搜索。

class Solution {
private:
    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++) {
            // used[i - 1] == true,说明同一树枝nums[i - 1]使用过
            // used[i - 1] == false,说明同一树层nums[i - 1]使用过
            // 如果同一树层nums[i - 1]使用过则直接跳过
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                continue;
            }
            if (used[i] == false) {
                used[i] = true;
                path.push_back(nums[i]);
                backtracking(nums, used);
                path.pop_back();
                used[i] = false;
            }
        }
    }
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        result.clear();
        path.clear();
        sort(nums.begin(), nums.end()); // 排序
        vector<bool> used(nums.size(), false);
        backtracking(nums, used);
        return result;
    }
};

// 时间复杂度: 最差情况所有元素都是唯一的。复杂度和全排列1都是 O(n! * n) 对于 n 个元素一共有 n! 中排列方案。而对于每一个答案,我们需要 O(n) 去复制最终放到 result 数组
// 空间复杂度: O(n) 回溯树的深度取决于我们有多少个元素

 tips:回溯算法去重的另一种写法

        要注意以下几点:

        1. 一定要记得用sort先对nums排序,否则大概率会错误的

        2. 如果使用uset去重,则insert以后不要erase,因为这样遍历的就是整棵树包括树枝了,同时,也不要每次进入单层的时候用uset的clear,uset已经是全局变量,本层的uset记录了一个元素,然后进入下一层之后这个uset就被清空了,也就是说,层与层之间的uset是同一个了,会相互影响

        需要注意,用set去重比used数组效率低很多。

51 N皇后

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 {
private:
vector<vector<string>> result;
// n 为输入的棋盘大小
// row 是当前递归到棋盘的第几行了
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;
        }
    }
    // 检查 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;
}
public:
    vector<vector<string>> solveNQueens(int n) {
        result.clear();
        std::vector<std::string> chessboard(n, std::string(n, '.'));
        backtracking(n, 0, chessboard);
        return result;
    }
};

 37 解数独

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

一个数独的解法需遵循如下规则: 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。 空白格用 '.' 表示。

解数独

一个数独。

解数独

答案被标成红色。

提示:

  • 给定的数独序列只包含数字 1-9 和字符 '.' 。
  • 你可以假设给定的数独只有唯一解。
  • 给定数独永远是 9x9 形式的。
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] == '.') {
                for (char k = '1'; k <= '9'; k++) {     // (i, j) 这个位置放k是否合适
                    if (isValid(i, j, k, board)) {
                        board[i][j] = k;                // 放置k
                        if (backtracking(board)) return true; // 如果找到合适一组立刻返回
                        board[i][j] = '.';              // 回溯,撤销k
                    }
                }
                return false;  // 9个数都试完了,都不行,那么就返回false
            }
        }
    }
    return true; // 遍历完没有返回false,说明找到了合适棋盘位置了
}
bool isValid(int row, int col, char val, vector<vector<char>>& board) {
    for (int i = 0; i < 9; i++) { // 判断行里是否重复
        if (board[row][i] == val) {
            return false;
        }
    }
    for (int j = 0; j < 9; j++) { // 判断列里是否重复
        if (board[j][col] == val) {
            return false;
        }
    }
    int startRow = (row / 3) * 3;
    int startCol = (col / 3) * 3;
    for (int i = startRow; i < startRow + 3; i++) { // 判断9方格里是否重复
        for (int j = startCol; j < startCol + 3; j++) {
            if (board[i][j] == val ) {
                return false;
            }
        }
    }
    return true;
}
public:
    void solveSudoku(vector<vector<char>>& board) {
        backtracking(board);
    }
};

 本题主要利用了二维递归,其实都差不多,只不过有两个for循环,同时注意找到一条合适的就返回,所以用bool类型。至此,回溯章节到此结束

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/331273.html

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

相关文章

剩余电流继电器装在哪里?电工必备知识

可实时监测和显示TN-S、TT系统配电线路的剩余电流&#xff1b; 每只剩余电流监测仪最多可监测16个回路的剩余电流&#xff0c;剩余电流监测范围为1mA-30A&#xff1b; 每路剩余电流监测均可设置报警值&#xff0c;报警值的设置范围为5mA-30A。每路剩余电流监测可设置为超值…

Docker(一)简介和基本概念

一、简介 本章将带领你进入 Docker 的世界。 什么是 Docker&#xff1f; 用它会带来什么样的好处&#xff1f; 好吧&#xff0c;让我们带着问题开始这神奇之旅。 1.什么是 Docker Docker 最初是 dotCloud 公司创始人 Solomon Hykes 在法国期间发起的一个公司内部项目&…

Joern环境的安装(Windows版)

Joern环境的安装(Windows版) 网上很少有关于Windows下安装Joern的教程&#xff0c;而我最初使用也是装在Ubuntu虚拟机中&#xff0c;这样使用很占内存&#xff0c;影响体验感。在Windows下使用源码安装Joern也是非常简单的过程&#xff1a; 提前需要的本地环境&#xff1a; …

基于YOLOv8深度学习的智能肺炎诊断系统【python源码+Pyqt5界面+数据集+训练代码】深度学习实战

《博主简介》 小伙伴们好&#xff0c;我是阿旭。专注于人工智能、AIGC、python、计算机视觉相关分享研究。 ✌更多学习资源&#xff0c;可关注公-仲-hao:【阿旭算法与机器学习】&#xff0c;共同学习交流~ &#x1f44d;感谢小伙伴们点赞、关注&#xff01; 《------往期经典推…

图像处理中,采用极线约束准则来约束特征点匹配搜索空间,理论上在极线上进行搜索。这里的极线是什么线,怎么定义的?基本矩阵F和本质矩阵E有什么区别?

问题描述&#xff1a;图像处理中&#xff0c;采用极线约束准则来约束特征点匹配搜索空间&#xff0c;理论上在极线上进行搜索。这里的极线是什么线&#xff0c;怎么定义的&#xff1f;基本矩阵F和本质矩阵E有什么区别&#xff1f; 问题1解答&#xff1a; 极线是通过极线几何学…

多特征变量序列预测-模型代码全家桶

包括代码、文献、文件解读&#xff01;&#xff01;&#xff01; 包括多特征变量序列预处理的代码&#xff0c; 预测效果好&#xff01;&#xff01;&#xff01;性能优越 包括 完整的风速数据集&#xff0c; 以及已经生成制作好的数据集、标签&#xff0c;对应代码均可以运行…

冻结Prompt微调LM: T5 PET (a)

T5 paper: 2019.10 Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer Task: Everything Prompt: 前缀式人工prompt Model: Encoder-Decoder Take Away: 加入前缀Prompt&#xff0c;所有NLP任务都可以转化为文本生成任务 T5论文的初衷如…

力扣刷MySQL-第四弹(详细讲解)

&#x1f389;欢迎您来到我的MySQL基础复习专栏 ☆* o(≧▽≦)o *☆哈喽~我是小小恶斯法克&#x1f379; ✨博客主页&#xff1a;小小恶斯法克的博客 &#x1f388;该系列文章专栏&#xff1a;力扣刷题讲解-MySQL &#x1f379;文章作者技术和水平很有限&#xff0c;如果文中出…

GPT应用程序的上线流程

将GPT应用程序上线涉及多个步骤&#xff0c;包括开发、测试、部署和发布。以下是一般的上线流程&#xff0c;希望对大家有所帮助。北京木奇移动技术有限公司&#xff0c;专业的软件外包开发公司&#xff0c;欢迎交流合作。 开发和测试&#xff1a; 在开发阶段&#xff0c;确保您…

Spring MVC的原理

Spring MVC中的MVC即模型-视图-控制器&#xff0c;该框架围绕一个DispatcherServlet设计而成&#xff0c;DispatcherServlet会把请求分发给各个处理器&#xff0c;并支持可配置的处理器映射和视图渲染等功能。Spring MVC的具体工作流程如下&#xff1a; &#xff08;1&#xff…

深度解析 Compose 的 Modifier 原理 -- Modifier.layout()、LayoutModifier

" Jetpack Compose - - Modifier 原理系列文章 " &#x1f4d1; 《 深入解析 Compose 的 Modifier 原理 - - Modifier、CombinedModifier 》 &#x1f4d1; 《 深度解析 Compose 的 Modifier 原理 - - Modifier.composed()、ComposedModifier 》 &#x1f4d1; 《 深…

redis安装-Linux为例

可以下载一个Shell或者MobaXterm工具&#xff0c;便于操作 在redis官网下载压缩包 开始安装 安装依赖 yum install -y gcc tcl切换目录 切换目录后直接把redis安装包拖到/user/local/src/下 cd /user/local/src/解压然后安装 #解压 tar -zxvf redis-7.2.4.tar.gz #安装 …

C语言——小细节和小知识12

一、倒置句子 将句子中的单词位置倒置&#xff0c;标点不用倒置&#xff0c;例如i love you.倒置结果是&#xff1a;you. love i。 1、两步翻转法 采用两步翻转法来实现单词位置的倒置。首先&#xff0c;它整体翻转整个字符串&#xff0c;然后再逐个翻转每个单词内的字符。 …

环形链表问题

环形链表 给你一个链表的头节点 head &#xff0c;判断链表中是否有环。 如果链表中有某个节点&#xff0c;可以通过连续跟踪 next 指针再次到达&#xff0c;则链表中存在环。 为了表示给定链表中的环&#xff0c;评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置&a…

如何录制屏幕视频?让视频制作更简单!

随着数字化时代的来临&#xff0c;录制屏幕视频成为一种常见的传播和教学方式。无论是制作演示文稿、教学视频&#xff0c;还是记录游戏操作&#xff0c;屏幕录制为用户提供了强大而灵活的工具。可是您知道如何录制屏幕视频吗&#xff1f;本文将深入介绍两种常见的屏幕录制方法…

vue el-select自定义搜索选择案例

开发中常见的有选择框并且输入关键词可以快速检索功能&#xff0c;刚好这次项目需求&#xff0c;就开始吧 需求&#xff1a;1、生成1000到100000的数可选择&#xff0c;递增1000 2、这些数必须三位数用逗号隔开&#xff0c;比如1,000.00这样的形式显示 3、输入关键词比如10&am…

zabbix监控平台(agent端)

引言&#xff1a;明人不说暗话&#xff0c;上一篇文章我们讲了zabbix的serrver端部署和配置&#xff0c;今天详细讲解一下agent端服务器&#xff08;客户端&#xff09;的配置和关联 1.进入官网 Zabbix&#xff1a;企业级开源监控解决方案 2.进入下载页面选择需要下载的版本信…

【JVM】JVM概述

JVM概述 基本介绍 JVM&#xff1a;全称 Java Virtual Machine&#xff0c;即 Java 虚拟机&#xff0c;一种规范&#xff0c;本身是一个虚拟计算机&#xff0c;直接和操作系统进行交互&#xff0c;与硬件不直接交互&#xff0c;而操作系统可以帮我们完成和硬件进行交互的工作特…

【网络安全】2024年一个漏洞4w+,网安副业挖SRC漏洞,躺着把钱挣了!

一个漏洞奖励2w&#xff0c;这是真实的嘛&#xff01; 作为资深白帽&#xff0c;入行网安这些年也一直在接私活&#xff0c;副业赚的钱几乎是我工资的三倍&#xff01;看到最近副业挖漏洞的内容非常火爆&#xff0c;我便决定将自己的经验分享出来&#xff0c;带我的粉丝们一起…

Vue3在点击菜单切换路由时,将ElementPlus UI库中el-main组件的内容滚动恢复到顶部

功能&#xff1a;Vue3在点击菜单切换路由时&#xff0c;将页面el-main的内容滚动到顶部&#xff0c;布局如下&#xff0c;使用UI组件库为ElementPlus 在网上搜很多都是在route.js中的router.beforeEach中使用window.scrollTop(0,0) 或 window.scrollTo(0,0) 滚动&#xff0c;但…