当前位置: 首页 > news >正文

五、回溯(trackback)

文章目录

  • 一、算法定义
  • 二、经典例题
    • (一)排列
      • 1.[46.全排列](https://leetcode.cn/problems/permutations/description/)
        • (1)思路
        • (2)代码
        • (3)复杂度分析
      • 2.[LCR 083. 全排列](https://leetcode.cn/problems/VvJkup/description/)
        • (1)思路
        • (2)代码
        • (3)复杂度分析
    • (二)组合
    • (三)子集
    • (四)N皇后问题、岛屿问题
      • 1.[51.N皇后](https://leetcode.cn/problems/n-queens/)
      • (1)思路
      • (2)代码
      • (3)复杂度分析

一、算法定义

抽象地说,解决一个回溯问题,实际上就是遍历一棵决策树的过程,树的每个叶子节点存放着一个合法答案。你把整棵树遍历一遍,把叶子节点上的答案都收集起来,就能得到所有的合法答案。
站在回溯树的一个节点上,你只需要思考 3 个问题:
1、路径:也就是已经做出的选择。
2、选择列表:也就是你当前可以做的选择。
3、结束条件:也就是到达决策树底层,无法再做选择的条件。
在这里插入图片描述

二、经典例题

(一)排列

1.46.全排列

(1)思路

在这里插入图片描述

(2)代码
class Solution {
public:
vector<vector<int>> res;void dfs(vector<int>& nums) {vector<int> path;vector<bool> used(nums.size(),false);trackback(nums,path,used);}void trackback(vector<int>& nums,vector<int>&path,vector<bool>&used) {if (path.size() == nums.size()) {res.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;trackback(nums, path, used);used[i] = false;path.pop_back();}}vector<vector<int>> permute(vector<int>& nums) {if (nums.size() == 0) return res;dfs(nums);return res;}
};
(3)复杂度分析

时间复杂度:O(n x n!)
空间复杂度:O(n),其中n为序列的长度。除答案数组以外,递归函数在递归过程中需要为每一层递归函数分配栈空间,所以这里需要额外的空间且该空间取决于递归的深度,这里可知递归调用深度为 O(n)。

2.LCR 083. 全排列

(1)思路
(2)代码
class Solution {
public:
vector<vector<int>> res;void process(vector<int>& nums) {vector<int> path;vector<bool> used(nums.size(),false);dfs(used,path,nums);}void dfs(vector<bool>& used,vector<int> &path,vector<int>& nums) {if (path.size() == nums.size()){res.push_back(path);return;}for (int i = 0; i < nums.size(); i++) {if (used[i]) continue;path.push_back(nums[i]);used[i] = true;dfs(used,path,nums);used[i] = false;path.pop_back();}}vector<vector<int>> permute(vector<int>& nums) {if (nums.size() == 0) return res;sort(nums.begin(),nums.end());process(nums);return res;}
};
(3)复杂度分析

时间复杂度:O(n x n!)
空间复杂度:O(n)

(二)组合

(三)子集

(四)N皇后问题、岛屿问题

1.51.N皇后

(1)思路

(2)代码

class Solution {
public:
vector<vector<string>> res;vector<vector<string>> solveNQueens(int n) {vector<string> board (n,string(n,'.'));backtrack(board,0);return res;}void backtrack(vector<string>& board, int row) {if (row == board.size()) {res.push_back(board);return;}int n = board[row].size();for (int col = 0; col < n; col++) {if (!isvaild(board,row,col)) {continue;}board[row][col] = 'Q';backtrack(board, row + 1);// 撤销选择board[row][col] = '.';}}bool isvaild(vector<string>& board, int row, int col) {int n = board.size();for (int i = 0; i <= row; i++) {if (board[i][col] == 'Q')return false;}for (int i = row - 1,j = col + 1; i >= 0 && j < n;i --,j ++) { // 左上if (board[i][j] == 'Q')return false;}for (int i = row - 1, j = col - 1;i >= 0 && j >= 0; i--, j--) {  // 右上if (board[i][j] == 'Q')return false;}return true;}
};

(3)复杂度分析

相关文章:

五、回溯(trackback)

文章目录 一、算法定义二、经典例题&#xff08;一&#xff09;排列1.[46.全排列](https://leetcode.cn/problems/permutations/description/)&#xff08;1&#xff09;思路&#xff08;2&#xff09;代码&#xff08;3&#xff09;复杂度分析 2.[LCR 083. 全排列](https://le…...

什么是分布式锁?他解决了什么样的问题?

相信对于朋友们来说&#xff0c;锁这个东西已经非常熟悉了&#xff0c;在说分布式锁之前&#xff0c;我们来聊聊单体应用时候的本地锁&#xff0c;这个锁很多小伙伴都会用 ✔本地锁 我们在开发单体应用的时候&#xff0c;为了保证多个线程并发访问公共资源的时候&#xff0c;…...

Ubuntu 12.04增加右键命令:在终端中打开增加打开文件

Ubuntu 12.04增加右键命令&#xff1a;在终端中打开 软件中心&#xff1a;搜索nautilus-open-terminal安装 用快捷键CtrlT打开命令行输入&#xff1a; sudo apt-get install nautilus-open-terminal 重新加载文件管理器 nautilus -q 或注销再登录即要使用...

Centos 7 访问局域网windows共享文件夹

Refer: centos7 访问windows系统的共享文件夹_centos访问windows共享_三希的博客-CSDN博客 一、在CentOS中配置CIFS网络存储服务 CIFS&#xff08;Common Internet File System&#xff09;是一种在网络上共享文件的协议&#xff0c;也称为SMB&#xff08;Server Message Blo…...

GDB的TUI模式(文本界面)

2023年9月22日&#xff0c;周五晚上 今晚在看GDB的官方文档时&#xff0c;发现GDB居然有文本界面模式 TUI (Debugging with GDB) (sourceware.org) GDB开启TUI的条件 GDB的文本界面的开启条件是&#xff1a;操作系统有适当版本的curses库 The TUI mode is supported only on…...

深入了解Python和OpenCV:图像的卡通风格化

前言 当今数字时代&#xff0c;图像处理和美化已经变得非常普遍。从社交媒体到个人博客&#xff0c;人们都渴望分享独特且引人注目的图片。本文将介绍如何使用Python编程语言和OpenCV库创建令人印象深刻的卡通风格图像。卡通风格的图像具有艺术性和创意&#xff0c;它们可以用…...

【算法挨揍日记】day06——1004. 最大连续1的个数 III、1658. 将 x 减到 0 的最小操作数

1004. 最大连续1的个数 III 1004. 最大连续1的个数 III 题目描述&#xff1a; 给定一个二进制数组 nums 和一个整数 k&#xff0c;如果可以翻转最多 k 个 0 &#xff0c;则返回 数组中连续 1 的最大个数 。 解题思路&#xff1a; 首先题目要我们求出的最多翻转k个0后&#x…...

华为云HECS安装docker

1、运行安装指令 yum install docker都选择y&#xff0c;直到安装成功 2、查看是否安装成功 运行版本查看指令&#xff0c;显示docker版本&#xff0c;证明安装成功 docker --version 或者 docker -v 3、启用并运行docker 3.1启用docker 指令 systemctl enable docker …...

力扣669 补9.16

最近大三上四天有早八&#xff0c;真的是受不了了啊&#xff0c;欧嗨呦&#xff0c;早上困如狗&#xff0c;然后&#xff0c;下午困如狗&#xff0c;然后晚上困如狗&#xff0c;尤其我最近在晚上7点到10点这个时间段看力扣&#xff0c;看得我昏昏欲睡&#xff0c;不自觉就睡了1…...

2023-9-22 没有上司的舞会

题目链接&#xff1a;没有上司的舞会 #include <cstring> #include <iostream> #include <algorithm>using namespace std;const int N 6010;int n; int happy[N]; int h[N], e[N], ne[N], idx; bool has_father[N];// 两个状态&#xff0c;选该节点或不选该…...

【HDFS】cachingStrategy的设置

org.apache.hadoop.hdfs.client.impl.BlockReaderFactory#getRemoteBlockReader: private BlockReader getRemoteBlockReader(Peer peer) throws IOException {int networkDistance = clientContext.getNetworkDistance(datanode);return BlockReaderRemote...

性能测试 —— 性能测试常见的测试指标 !

一、什么是性能测试 先看下百度百科对它的定义&#xff0c;性能测试是通过自动化的测试工具模拟多种正常、峰值以及异常负载条件来对系统的各项性能指标进行测试。 我们可以认为性能测试是&#xff1a;通过在测试环境下对系统或构件的性能进行探测&#xff0c;用以验证在生产环…...

【学习草稿】背包问题

一、01背包问题 图解详细解析 &#xff08;转载&#xff09; https://blog.csdn.net/qq_37767455/article/details/99086678 &#xff1a;Vi表示第 i 个物品的价值&#xff0c;Wi表示第 i 个物品的体积&#xff0c;定义V(i,j)&#xff1a;当前背包容量 j&#xff0c;前 i 个物…...

doxygen c++ 语法

c基本语法模板 以 /*! 开头, */ 结尾 /*!\关键字1\关键字2 */1 文件头部信息 /*! \file ClassA.h* \brief 文件说明 定义了类fatherA* \details This class is used to demonstrate a number of section commands.* \author John Doe* \author Jan Doe* \v…...

ChatGLM微调基于P-Tuning/LoRA/Full parameter(上)

1. 准备环境 首先必须有7个G的显存以上,torch >= 1.10 需要根据你的cuda版本 1.1 模型下载 $ git lfs install $ git clone https://huggingface.co/THUDM/chatglm-6b1.2 docker环境搭建 环境搭建 $ sudo docker pull slpcat/chatglm-6b:latest $ sudo docker run -it …...

BLE Mesh蓝牙mesh传输大数据包传输文件照片等大数据量通讯

1、BLE Mesh数据传输现状 BLE Mesh网络技术是低功耗蓝牙的一个进阶版&#xff0c;Mesh扩大了蓝牙在应用中的规模和范围&#xff0c;因为它同时支持超过三万个网络节点&#xff0c;可以跨越大型建筑物&#xff0c;不仅可以使得医疗健康应用更加方便快捷&#xff0c;还能监测像学…...

9.18 QT作业

mainwindow.h QT_BEGIN_NAMESPACE namespace Ui { class MainWindow; } QT_END_NAMESPACEclass MainWindow : public QMainWindow {Q_OBJECTpublic:MainWindow(QWidget *parent nullptr);~MainWindow();signals:void jump(); //自定义跳转信号函数private slots:vo…...

【100天精通Python】Day67:Python可视化_Matplotlib 绘动画,2D、3D 动画 示例+代码

1 绘制2D动画&#xff08;animation&#xff09; Matplotlib是一个Python绘图库&#xff0c;它提供了丰富的绘图功能&#xff0c;包括绘制动画。要绘制动画&#xff0c;Matplotlib提供了FuncAnimation类&#xff0c;允许您创建基于函数的动画。下面是一个详细的Matplotlib动画示…...

Linux内核源码分析 (B.x)Linux页表的映射

Linux内核源码分析 (B.x)Linux页表的映射 文章目录 Linux内核源码分析 (B.x)Linux页表的映射一、ARM32页表1、页表术语2、虚拟地址到物理地址转换3、一级页表项4、二级页表项 二、ARM64页表1、ARMv8-A架构2、4KB大小页4级映射 三、Linux内核中关于页表的函数和宏1、查询页表2、…...

机器学习(15)---代价函数、损失函数和目标函数详解

文章目录 一、各自定义二、各自详解三、代价函数和损失函数区别四、例题理解 一、各自定义 1. 代价函数&#xff1a;代价函数&#xff08;Cost Function&#xff09;是定义在整个训练集上的&#xff0c;是所有样本误差的平均&#xff0c;也就是损失函数的平均。它用于衡量模型在…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

基于大模型的 UI 自动化系统

基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...

Flask RESTful 示例

目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题&#xff1a; 下面创建一个简单的Flask RESTful API示例。首先&#xff0c;我们需要创建环境&#xff0c;安装必要的依赖&#xff0c;然后…...

Linux链表操作全解析

Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表&#xff1f;1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

系统设计 --- MongoDB亿级数据查询优化策略

系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log&#xff0c;共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题&#xff0c;不能使用ELK只能使用…...

定时器任务——若依源码分析

分析util包下面的工具类schedule utils&#xff1a; ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类&#xff0c;封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz&#xff0c;先构建任务的 JobD…...

Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理

引言 Bitmap&#xff08;位图&#xff09;是Android应用内存占用的“头号杀手”。一张1080P&#xff08;1920x1080&#xff09;的图片以ARGB_8888格式加载时&#xff0c;内存占用高达8MB&#xff08;192010804字节&#xff09;。据统计&#xff0c;超过60%的应用OOM崩溃与Bitm…...

分布式增量爬虫实现方案

之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面&#xff0c;避免重复抓取&#xff0c;以节省资源和时间。 在分布式环境下&#xff0c;增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路&#xff1a;将增量判…...

使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度

文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...