蓝桥杯试题:DFS回溯
一、题目要求
输入一个数组n,输出1到n的全排列
二、代码展示
import java.util.*;public class ikun {static List<List<Integer>> list = new ArrayList<>();public static void main(String[] args) { Scanner sc = new Scanner(System.in);int n = sc.nextInt();int[] v = new int[n + 1];List<Integer> res = new ArrayList<>();dfs(n,v,res);for (List<Integer> x:list){for (int y:x){System.out.print(y + " ");}System.out.println();}}public static void dfs(int n, int[] v, List<Integer> res) {// 终止条件:当当前排列长度等于n时if (res.size() == n) {// 深拷贝当前排列结果到结果集list.add(new ArrayList<>(res));return; // 结束当前递归分支}// 遍历所有数字1~nfor (int i = 1; i <= n; i++) {// 跳过已使用的数字(剪枝操作)if (v[i] == 1) continue;// 选择阶段:将数字i加入当前排列res.add(i); // 操作路径v[i] = 1; // 更新状态标记// 递归深入:探索下一层决策树dfs(n, v, res); // 进入新的递归层级// 回溯阶段:撤销当前选择res.remove(res.size() - 1); // 移除最后一个元素(i)v[i] = 0; // 重置状态标记}}}
核心逻辑
主方法(main):
创建标记数组
v(索引1到n标记数字是否被使用)。调用DFS函数生成排列。
遍历结果列表
list,输出所有排列。DFS方法(dfs):
终止条件:当临时结果
res的大小等于n时,将当前排列存入list。递归过程:
遍历数字1到n。
若当前数字未被使用(
v[i] == 0):
将数字加入
res,并标记为已使用。递归调用DFS,继续生成剩余位置的排列。
回溯:递归返回后,移除
res末尾元素,并重置标记,以便尝试其他数字。关键点分析
标记数组
v:用于避免重复使用数字。v[i] = 1表示数字i已被使用。回溯机制:在递归返回后,撤销当前选择(移除
res末尾元素,重置标记),确保后续分支的正确性。结果存储:每次找到完整排列时,复制
res到list(避免后续修改影响已存结果)。
三、DFS算法
1、DFS算法核心思想
深度优先搜索(DFS) 是一种"先探到底再回溯"的算法,其核心特征是:
-
优先沿着一条路径深入探索到底
-
遇到终点或无法继续时回溯到最近的分支点
-
通过递归或栈结构实现路径记录和状态回退
基础语法:
public static void dfs(){if (当前状态 == 目标状态){//逻辑处理return;}for (寻找新状态){if (状态合法){dfs(新状态);}}}
回溯
public static void dfs(){if (当前状态 == 目标状态){//逻辑处理return;}for (查找新状态){if (状态合法){//标记当前状态已访问dfs(新状态);//撤销标记}}}
2、代码中的DFS实现解析
代码结构概览
static List<List<Integer>> list = new ArrayList<>(); // 存储所有排列结果public static void dfs(int n, int[] v, List<Integer> res) {// 终止条件if (res.size() == n) {list.add(new ArrayList<>(res)); // 保存当前排列return;}// 遍历所有可能选择for (int i = 1; i <= n; i++) {if (v[i] == 1) continue; // 跳过已使用的数字// 做选择res.add(i);v[i] = 1;// 递归深入dfs(n, v, res);// 撤销选择(回溯)res.remove(res.size() - 1);v[i] = 0;}
}
3、代码与DFS原理的对应关系
| DFS阶段 | 代码实现 | 说明 |
|---|---|---|
| 1. 路径选择 | res.add(i) | 将当前数字加入排列路径 |
| 2. 状态标记 | v[i] = 1 | 标记该数字已被使用 |
| 3. 递归深入 | dfs(n, v, res) | 进入下一层决策树 |
| 4. 回溯恢复 | res.remove(...); v[i] = 0 | 返回上层时撤销选择 |
| 5. 终止条件 | if (res.size() == n) | 当路径长度等于n时记录结果 |
4、执行流程演示(n=2)
初始调用:dfs(2, [0,0,0], [])↓ i=1被选中:res=[1], v=[0,1,0]→ 递归调用 dfs(2, [0,1,0], [1])↓i=2被选中:res=[1,2], v=[0,1,1]→ 记录结果 [1,2]← 回溯:res变为[1], v[2]=0← 返回上层← 回溯:res变为[], v[1]=0i=2被选中:res=[2], v=[0,0,1]→ 递归调用 dfs(2, [0,0,1], [2])↓i=1被选中:res=[2,1], v=[0,1,1]→ 记录结果 [2,1]← 回溯:res变为[2], v[1]=0← 返回上层← 回溯:res变为[], v[2]=0
5、算法特性分析
| 特性 | 本代码中的体现 |
|---|---|
| 时间复杂度 | O(n!) - 需要生成n!种排列 |
| 空间复杂度 | O(n) - 递归栈深度为n |
| 回溯机制 | 通过remove和v[i]=0显式实现状态回退 |
| 剪枝优化 | 使用v数组避免重复选择 |
| 结果存储 | 使用new ArrayList<>(res)深度拷贝当前状态 |
6、DFS的典型应用场景
-
全排列/组合问题(如本代码所示)
-
迷宫路径搜索
-
树/图的遍历
-
棋盘类游戏解法(八皇后、数独等)
-
连通分量检测
通过这种递归+回溯的实现方式,DFS算法能系统性地遍历所有可能的解空间,特别适合需要穷举所有可能性的场景。代码中通过标记数组和列表操作,清晰地展现了DFS的核心思想。
相关文章:
蓝桥杯试题:DFS回溯
一、题目要求 输入一个数组n,输出1到n的全排列 二、代码展示 import java.util.*;public class ikun {static List<List<Integer>> list new ArrayList<>();public static void main(String[] args) { Scanner sc new Scanner(System.in);…...
Lua | 每日一练 (4)
💢欢迎来到张胤尘的技术站 💥技术如江河,汇聚众志成。代码似星辰,照亮行征程。开源精神长,传承永不忘。携手共前行,未来更辉煌💥 文章目录 Lua | 每日一练 (4)题目参考答案线程和协程调度方式上…...
每日一题——接雨水
接雨水问题详解 问题描述 给定一个非负整数数组 height,表示每个宽度为 1 的柱子的高度图。计算按此排列的柱子,下雨之后能接多少雨水。 示例 示例 1: 输入:height [0,1,0,2,1,0,1,3,2,1,2,1] 输出:6 解释&#…...
java常见面试01
为什么重写 equals 还要重写 hashcode 🌈 核心原因: 当两个对象通过equals()判断为相等时,它们的hashCode()必须返回相同的整数值!这是Java世界的交通规则哦~(交警曼波敬礼.jpg) 🧩 具体场景…...
算法-二叉树篇27-把二叉搜索树转换为累加树
把二叉搜索树转换为累加树 力扣题目链接 题目描述 给出二叉 搜索 树的根节点,该树的节点值各不相同,请你将其转换为累加树(Greater Sum Tree),使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。 提…...
C语言:51单片机 基础知识
一、单片机概述 单片机的组成及其特点 单片机是指在一块芯片上集成了CPU、ROM、RAM、定时器/计数器和多种I/O接口电路等,具有一定规模的微型计算机。 特点: 1、单片机的存储器以ROM、RAM严格分工。 2、采用面向控制的指令系统。 3、单片机的I/O口引脚通…...
olmOCR:使用VLM解析PDF
在PDF解析中,目前主流的开源工具包括Minuer、GOT OCR等。主要都是通过飞桨等OCR套件组装的一套pipeline,或者直接通过VLM解析图像。 #一、 olmOCR是使用VLM进行的端到端的PDF文档解析 二、document-anchoring 与上述的不同在于,olmOCR使用…...
数据结构(初阶)(七)----树和二叉树(堆,堆排序)
八,树与二叉树 树 概念与结构 树是⼀种⾮线性的数据结构,它是由 n(n>0) 个有限结点组成⼀个具有层次关系的集合。把它叫做树是因为它看起来像⼀棵倒挂的树,也就是说它是根朝上,⽽叶朝下的。 • 有⼀…...
图像分类项目1:基于卷积神经网络的动物图像分类
一、选题背景及动机 在现代社会中,图像分类是计算机视觉领域的一个重要任务。动物图像分类具有广泛的应用,例如生态学研究、动物保护、农业监测等。通过对动物图像进行自动分类,可以帮助人们更好地了解动物种类、数量和分布情况,…...
Kali Linux 2024.4版本全局代理(wide Proxy)配置,适用于浏览器、命令行
1. 网络拓扑介绍(不使用虚拟机直接跳到2) 虚拟机:VMware 17 Pro,为本机开启桥接模式。 我的究极套娃网络:手机V2rayNG代理端口为10808,开热点 -> 电脑连接wifi -> 虚拟机中运行kali 2. kali 配置…...
[Windows] 批量为视频或者音频生成字幕 video subtitle master 1.5.2
Video Subtitle Master 1.5.2 介绍 Video Subtitle Master 1.5.2 是一款功能强大的客户端工具,能够批量为视频或音频生成字幕,还支持批量将字幕翻译成其他语言。该工具具有跨平台性,无论是 mac 系统还是 windows 系统都能使用。 参考原文&a…...
不要升级,Flutter Debug 在 iOS 18.4 beta 无法运行,提示 mprotect failed: Permission denied
近期如果有开发者的 iOS 真机升级到 18.4 beta,大概率会发现在 debug 运行时会有 Permission denied 的相关错误提示,其实从 log 可以很直观看出来,就是 Dart VM 在初始化时,对内核文件「解释运行(JIT)」时…...
介绍 torch-mlir 从 pytorch 生态到 mlir 生态
一、引言 The Torch-MLIR project provides core infrastructure for bridging the PyTorch ecosystem and the MLIR ecosystem. For example, Torch-MLIR enables PyTorch models to be lowered to a few different MLIR dialects. Torch-MLIR does not attempt to provide a…...
upload
(上传一句话木马,用蚁剑链接验证是否成功/传有回显的:<?php phpinfo();?>) 学看代码 #function checkfile(){}:定义了一个名叫checkfile的函数 #var file方法.(获取名为‘upload_file’的元素)[获取哪些&…...
InterHand26M(handposeX-json 格式)数据集-release >> DataBall
DataBall 助力快速掌握数据集的信息和使用方式,会员享有 百种数据集,持续增加中。 需要更多数据资源和技术解决方案,知识星球: “DataBall - X 数据球(free)” 贵在坚持! ---------------------------------------…...
[Java基础] JVM常量池介绍(BeanUtils.copyProperties(source, target)中的属性值引用的是同一个对象吗)
文章目录 1. JVM内存模型2. 常量池中有什么类型?3. 常量池中真正存储的内容是什么4. 判断一个字符串(引用)是否在常量池中5. BeanUtils.copyProperties(source, target)中的属性值引用的是同一个对象吗?6. 获取堆内存使用情况、非堆内存使用情况 1. JVM内…...
`maturin`是什么:matu rus in python
maturin是什么 maturin 是一个用于构建和发布 Rust 编写的 Python 绑定库的工具。它简化了将 Rust 代码集成到 Python 项目中的过程,支持创建不同类型的 Python 包,如纯 Python 包、包含 **Rust (系统编程语言)**扩展模块的包等。以下为你详细介绍 maturin 的相关信息并举例…...
spring boot整合flyway实现数据的动态维护
1、简单介绍一下flyway Flyway 是一款开源的数据库版本控制工具,主要用于管理数据库结构的变更(如创建表、修改字段、插入数据等)。它通过跟踪和执行版本化的迁移脚本,帮助团队实现数据库变更的自动化。接下来简单介绍一下flyway…...
unity中使用spine详解
一.Spine概述 Spine 是一款针对游戏开发的 2D 骨骼动画编辑工具。 Spine 旨在提供更高效和简洁 的工作流程,以创建游戏所需的动画。 Spine原理:将一个模型,根据动画的需求分成一些骨骼,一个骨骼对应一张贴图,控制骨骼…...
14. LangChain项目实战1——基于公司制度RAG回答机器人
教学视频: 12. 基于Gradio搭建基于公司制度RAG_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV11VXRYTErZ/ 环境配置: python版本:3.10.8 服务器:Ubuntu 依赖包requirements.txt文件内容: aiofiles23.2.1 …...
Linux 文件类型,目录与路径,文件与目录管理
文件类型 后面的字符表示文件类型标志 普通文件:-(纯文本文件,二进制文件,数据格式文件) 如文本文件、图片、程序文件等。 目录文件:d(directory) 用来存放其他文件或子目录。 设备…...
IGP(Interior Gateway Protocol,内部网关协议)
IGP(Interior Gateway Protocol,内部网关协议) 是一种用于在一个自治系统(AS)内部传递路由信息的路由协议,主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...
在Ubuntu中设置开机自动运行(sudo)指令的指南
在Ubuntu系统中,有时需要在系统启动时自动执行某些命令,特别是需要 sudo权限的指令。为了实现这一功能,可以使用多种方法,包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法,并提供…...
今日科技热点速览
🔥 今日科技热点速览 🎮 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售,主打更强图形性能与沉浸式体验,支持多模态交互,受到全球玩家热捧 。 🤖 人工智能持续突破 DeepSeek-R1&…...
【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统
目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索(基于物理空间 广播范围)2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...
C++ 设计模式 《小明的奶茶加料风波》
👨🎓 模式名称:装饰器模式(Decorator Pattern) 👦 小明最近上线了校园奶茶配送功能,业务火爆,大家都在加料: 有的同学要加波霸 🟤,有的要加椰果…...
windows系统MySQL安装文档
概览:本文讨论了MySQL的安装、使用过程中涉及的解压、配置、初始化、注册服务、启动、修改密码、登录、退出以及卸载等相关内容,为学习者提供全面的操作指导。关键要点包括: 解压 :下载完成后解压压缩包,得到MySQL 8.…...
SQL Server 触发器调用存储过程实现发送 HTTP 请求
文章目录 需求分析解决第 1 步:前置条件,启用 OLE 自动化方式 1:使用 SQL 实现启用 OLE 自动化方式 2:Sql Server 2005启动OLE自动化方式 3:Sql Server 2008启动OLE自动化第 2 步:创建存储过程第 3 步:创建触发器扩展 - 如何调试?第 1 步:登录 SQL Server 2008第 2 步…...
深度剖析 DeepSeek 开源模型部署与应用:策略、权衡与未来走向
在人工智能技术呈指数级发展的当下,大模型已然成为推动各行业变革的核心驱动力。DeepSeek 开源模型以其卓越的性能和灵活的开源特性,吸引了众多企业与开发者的目光。如何高效且合理地部署与运用 DeepSeek 模型,成为释放其巨大潜力的关键所在&…...
PH热榜 | 2025-06-08
1. Thiings 标语:一套超过1900个免费AI生成的3D图标集合 介绍:Thiings是一个不断扩展的免费AI生成3D图标库,目前已有超过1900个图标。你可以按照主题浏览,生成自己的图标,或者下载整个图标集。所有图标都可以在个人或…...
