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

数据结构与算法学习笔记----DFS

news 来源：原创 2025/5/12 22:14:41

数据结构与算法学习笔记----DFS

@@ author: 明月清了个风

@@ first publish time: 2024.12.4

@@ revised: 2024.12.5 - 加了Acwing 843. n-皇后问题。

ps⛹感觉DFS的题基本的思想就是递归，但是每题都有不一样的地方，每一题的思路和模拟过程都单独写在每一题里了。

Acwing 842. 排列数字

[原题链接](842. 排列数字 - AcWing题库)

给定一个整数 $n$ ，将数字 $\sim n$ 排成一排，将会有很多种排列方法。

现在，请你按照字典序将所有的排列方法输出。

输入格式

共一行，包含一个整数 $n$ 。

输出格式

按照字典序输出所有排列方案，每个方案占一行。

数据范围

$\leq n \leq 7$ ,

思路

感觉这里的搜索思路相对简单，用一个path[]数组记录路径，st[]数组记录每个数字的使用状态。

具体的手动模拟一遍应该就懂了，下面代码的注释也比较全面了

代码

#include <iostream>using namespace std;const int N = 10;int path[N];
bool st[N];
int n;void dfs(int u)   // 参数u表示当前path中已经有了几个数字，
{if(u == n) // path中记录了n个数字后，表示排列完成并输出path{for(int i = 0; i < n; i ++)cout << path[i] << ' ';cout << endl;return ;}for(int i = 1; i <= n; i ++)    // 因为要按字典序，所以每次都是从1开始看{if(!st[i])    // 看这个数字在这组排列中有没有被使用过{path[u] = i;    // 没有使用过，那就使用这个数字st[i] = true; 	// 并且将这个数字标记为使用过dfs(u + 1);     // 这一轮中使用了一个数字，因此path中多一个数，进一步搜索下一位st[i] = false;   // dfs返回后应将刚刚使用过的数字标记为未使用恢复现场。}}return ;
}int main()
{cin >> n;dfs(0);return 0;
}

Acwing 843. n-皇后问题

[原题链接](843. n-皇后问题 - AcWing题库)

$n$ 皇后问题是指将 $n$ 个皇后放在 $\times n$ de 国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。

现给定整数 $n$ ，请你输出所有的满足条件的棋子摆法。

输入格式

共一行，包含一个整数 $n$ 。

输出格式

每个解决方案占 $n$ 行，每行输出一个长度为 $n$ 的字符串，用来表示完整的期盼状态。

其中.表示某一个位置为空，Q表示某一个位置的放个上摆着皇后。

每个方案输出完成后，输出一个空行。

数据范围

$\leq n \leq 9$ ,

思路

⭐️注意点就是对角线和反对角线的判断了，可以将对角线和反对角线看成y = x + a和y = -x + b，对于不同的x和y，两条对角线会映射到不同的截距a和b，下面的代码中加了n是因为对于y - x = a来说，可能会出现算出来的截距小于0，因此要加上一个偏移量，其实如果能自己找到方式，将所有的对角线映射到不同的值就行啦，不一定一定要这样映射。

第一种搜索顺序

根据题意，每一个格子只有放和不放两种状态，因此可以直接按顺序搜索每种格子的两种情况，最后判断是否满足条件即可，具体的看下面代码吧，注释很多。

#include <iostream>using namespace std;const int N =10;char g[N][N];
bool col[N], row[N], dg[N * 2], udg[N * 2];
int n;void dfs(int x, int y, int s)  // x, y表示当前枚举的格子，s表示当前放了几个皇后
{if(s > n) return ;   // 放的个数超过了n，直接返回if(y == n) y = 0, x ++;  // 列数越界了，进入下一行if(x == n)     // 到了最后一行{if(s == n)  // 满足条件，输出矩阵{for(int i = 0; i < n; i ++) cout << g[i] << endl;cout << endl;}return;}g[x][y] = '.';   // 这一格子不放，继续搜索dfs(x, y + 1, s);if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n])   // 判断这个格子能不能放，能放就放，然后继续搜索{row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;g[x][y] = 'Q';dfs(x, y + 1, s + 1);g[x][y] = '.';   // 搜索回来了，恢复现场，还原到之前的状态row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;}}int main()
{cin >> n;dfs(0 , 0, 0);return 0;
}

第二种搜索顺序

根据题意可以知道，每一行，每一列，每一个斜线都只会有一个皇后，因此，可以直接枚举每一行放在哪，然后判断其他是否成立，这样的顺序会比上面快很多，因为是按行来枚举，代码如下

#include <iostream>
#include <cstring>using namespace std;const int N = 20;char g[N][N];
int n;
bool col[N], dg[N * 2], udg[N * 2];void dfs(int u)
{if(u == n){for(int i = 0; i < n; i ++) puts(g[i]);cout << endl;return ;}for(int i = 0; i < n; i ++){if(!col[i] && !dg[u + i] && !udg[n - u + i]){col[i] = dg[u + i] = udg[n - u + i] = true;g[u][i] = 'Q';dfs(u + 1);g[u][i] = '.';col[i] = dg[u + i] = udg[n - u + i] = false;}}return ;
}int main()
{cin >> n;for (int i = 0; i < n; i ++ )for (int j = 0; j < n; j ++ )g[i][j] = '.';dfs(0);return 0;
}

数据结构与算法学习笔记----DFS

数据结构与算法学习笔记----DFS author: 明月清了个风 first publish time: 2024.12.4 revised: 2024.12.5 - 加了Acwing 843. n-皇后问题。 ps⛹感觉DFS的题基本的思想就是递归，但是每题都有不一样的地方，每一题的思路和模拟过程都单独写在每一题里…...

编程日记 2025/5/12 22:14:41

力扣54.螺旋矩阵

题目描述题目链接54. 螺旋矩阵给你一个 m 行 n 列的矩阵 matrix ，请按照顺时针螺旋顺序 ，返回矩阵中的所有元素。示例 1： 输入：matrix [[1,2,3],[4,5,6],[7,8,9]] 输出：[1,2,3,6,9,8,7,4,5]示例 2：…...

编程日记 2025/5/12 21:34:35

【原生js案例】webApp实现一个分享到的功能

这种分享到的效果很常见，在我们的网站上。鼠标滑入展示，滑出就隐藏。现在我们使用定时器功能来实现这种滑动效果。感兴趣的可以关注下我的系列课程【webApp之h5端实战】，里面有大量的css3动画效果制作原生知识分析，讲解&#xf…...

编程日记 2025/5/12 21:14:14

iPhone手机清理软件：相册清理大师推荐

随着智能手机成为我们日常生活的必需品，手机中的数据日益膨胀，尤其是照片和视频这类容易积累的文件。对于iPhone用户来说，管理这些文件，特别是清理相册变得尤为重要。本文将介绍一款备受推崇的iPhone手机清理软件——CleanMyPhone…...

编程日记 2025/5/11 21:58:01

Javaweb梳理21——Servlet

Javaweb梳理21——Servlet 21 Servlet21.1 简介21.3 执行流程21.4 生命周期4.5 方法介绍21.6 体系结构21.7 urlPattern配置21.8 XML配置 21 Servlet 21.1 简介 Servlet是JavaWeb最为核心的内容，它是Java提供的一门动态web资源开发技术。使用Servlet就可以实现&…...

编程日记 2025/5/12 21:30:19

Serverless 时代

前端的边界探索，从客户端展开，以跨端为目标，用一套 JavaScript 代码生成多端平台，以此来实现大前端的统一。虽然在这条路上还不算尽善尽美，但各家公司的跨端方案已基本趋于成熟，并且已经运用到生产环境中。…...

编程日记 2025/5/7 15:24:09

docker安装clickhouse副本集群

docker安装clickhouse副本集群 1、clickhouse副本集群搭建1.1、docker安装zookeeper集群1.1.1、zookeeper第一个节点安装1.1.2、zookeeper第二个节点安装1.1.3、zookeeper第三个节点安装1.1.4、zookeeper客户端命令 2、Clickhouse副本集群搭建2.1、clickhouse搭建2.2、验证集群…...

编程日记 2025/5/12 19:57:57

详解AI网关助力配电房实现智能化管控应用

对于一些建设年份久远的老旧配电房，由于配套降温散热设施设备不完善、线路设备老化等因素，极易出现因环境过热而影响设备正常稳定运行，进而导致电气故障甚至火灾等事故产生。基于AI网关的配电房智能监控及管理针对配电房的实时安全监测及…...

编程日记 2025/5/12 22:00:17

uniapp调用腾讯定位api

1、注册腾讯地址api接口，创建应用获取key WebService API | 腾讯位置服务 2、配置获取方法getCity // 定位服务getCity(latitude, longitude) {const key XXXX-XXXX-XXXX-XXXX-XXXX; // 替换为你的腾讯位置服务密钥const url /apis.map.qq.com/ws/geocoder/v1/…...

编程日记 2025/5/12 19:49:11

映射vim键位,基本功能键位表(未更完)

键位映射：建议使用jj代替esc,毕竟esc离手那么远 linux下修改方法是：vim /etc/vim/vimrc 在该文件尾添加inoremap jj <Esc>该方法可以同样可以用到其他键位映射上 i：表示这个映射是在插入模式（insert mode）下有效…...

编程日记 2025/5/12 21:46:20

【Python】爬虫实战03：自动化抢票脚本【某麦网】

1. 脚本介绍 1.1 背景介绍在这个数字化时代，演唱会、体育赛事和各种活动的门票销售往往在线上进行。由于热门活动的高需求和门票的有限供应，抢票成为了一场激烈的竞争。许多粉丝和爱好者经常因为手速不够快或网络延迟而错失购票机会。为了提高抢票的成…...

编程日记 2025/5/11 23:25:38

继承System.Web.Http.ApiController的Action的Model如果被[Serializable]定义，会导致Model的字段无法绑定。 Microsoft.AspNet.WebApi.Core.5.2.3\lib\net45\System.Web.Http.dll [Serializable] public class Model {public string id { get; set; } }public MyA…...

编程日记 2025/5/6 8:21:28

ISAAC SIM踩坑记录--添加第三方3D场景

ISAAC SIM仿真首先就是要有合适的3D场景，官方提供了一些场景，如果不能满足要求，那就只能自己建。对于我这种不会3D建模的菜鸟，只能到网上下载了，sketchfab就是一个不错的平台，有不少免费资源可以下载。 …...

编程日记 2025/5/11 0:24:17

Linux中Crontab（定时任务）命令详解

文章目录 Linux中Crontab（定时任务）命令详解一、引言二、Crontab的基本使用1、Crontab命令格式2、Crontab常用操作三、Crontab的配置与服务管理1、配置Crontab2、服务管理四、使用示例1、每天凌晨2点备份网站数据2、每周一凌晨3点清理临时文件3、每月的…...

编程日记 2025/5/11 14:59:29

在Ubuntu中运行和管理AppImage

文章目录什么是AppImage？如何在Ubuntu中运行AppImage？如何管理AppImage？安装AppImageLauncher如何添加AppImage到系统？如何从系统中移除AppImage？ 总结什么是AppImage？ AppImage是一种将应用程序打包为单…...

编程日记 2025/5/10 14:15:46

2024年12月大语言模型最新对比：GPT-4、Claude 3、文心一言等详细评测

前言随着人工智能技术的快速发展，大语言模型(LLM)已经成为了技术领域最热门的话题。本文将详细对比目前主流的大语言模型，帮助大家选择最适合的工具。一、OpenAI GPT系列 1. GPT-4 核心优势： 多模态理解能力强逻辑推理能力出色创造…...

编程日记 2025/5/3 4:32:15

上下位关系自动检测方法

✨✨ 欢迎大家来访Srlua的博文（づ￣3￣）づ╭❤～✨✨ 🌟🌟 欢迎各位亲爱的读者，感谢你们抽出宝贵的时间来阅读我的文章。我是Srlua小谢，在这里我会分享我的知识和经验。&am…...

编程日记 2025/5/8 22:59:07

Linux入门攻坚——40、Linux集群系统入门-lvs（1）

Cluster，集群，为了解决某个特定问题将多台计算机组合起来形成的单个系统。这个单个集群系统可以扩展，系统扩展的方式：scale up，向上扩展，更换更好的主机；scale out，向外扩展&…...

编程日记 2025/4/29 21:59:26

结构篇| 浅析LLaMA网络架构

01 前言 LLaMA（Large Language Model Meta AI）是由Meta AI 发布的一个开放且高效的大型基础语言模型。为什么突然讲这个模型，主要LLaMA 已经成为了最受欢迎的开源大语言模型之一，LLaMA 系列模型在学术界和工业界引起了广泛的关注，对于推动大语言模型技术的开源发展做出了…...

编程日记 2025/5/6 5:49:47

CTF-PWN: 全保护下格式化字符串利用 [第一届“吾杯”网络安全技能大赛如果能重来] 赛后学习(不会)

通过网盘分享的文件：如果能重来.zip 链接: https://pan.baidu.com/s/1XKIJx32nWVcSpKiWFQGpYA?pwd1111 提取码: 1111 --来自百度网盘超级会员v2的分享漏洞分析格式化字符串漏洞,在printf(format); __int64 sub_13D7() {char format[56]; // [rsp10h] [rbp-40h]…...

编程日记 2025/5/5 23:59:22

openEuler卸载 rpm安装的 redis

停止 Redis 服务 sudo systemctl stop redis禁用 Redis 服务 sudo systemctl disable redis 卸载 Redis 软件包 sudo yum remove redis查找并删除 Redis 的残留文件 find / -name red*删除 Redis 配置文件删除 Redis 数据文件 sudo rm -rf /var/lib/redis检查 Redis 是否…...

编程日记 2025/5/11 5:09:34

xxl-job分布式任务调度

XXL-JOB是一个轻量级分布式任务调度平台，其核心设计目标是开发迅速、学习简单、轻量级、易扩展。现已开放源代码并接入多家公司线上产品线，开箱即用。 GitHub：https://github.com/xuxueli/xxl-job 码云：https://gitee.com/xuxue…...

编程日记 2025/5/6 3:15:57

flutter_quill如何设置Editor中的文字为富文本

比如一个场景在输入框中，某某某是一个颜色，其他文本是一个颜色这里要注意 const QuillEditor({required this.controller,required this.focusNode,required this.scrollController,required this.scrollable,required this.padding,required this…...

编程日记 2025/5/7 20:52:42

shell语法（1）bash

shell是我们通过命令行与操作系统沟通的语言，是一种解释型语言 shell脚本可以直接在命令行中执行，也可以将一套逻辑组织成一个文件，方便复用 Linux系统中一般默认使用bash为脚本解释器在Linux中创建一个.sh文件，例如vim test.sh…...

编程日记 2025/5/11 17:55:15

AgGrid 组件封装设计笔记：自定义 icon 以及每个 icon 的点击事件处理

文章目录问题目前解决效果 v1思路目前解决效果 v0思路代码V1 问题自己封装的 AgGrid 如何自定义传递 icon ，以及点击事件的处理？ 目前解决效果 v1 思路目前解决效果 v0 思路一张图片说明一下代码 V1 父组件使用 <template><MyPageL…...

编程日记 2025/5/11 8:03:26

什么是TCP的三次握手

TCP（传输控制协议）的三次握手是一个用于在两个网络通信的计算机之间建立连接的过程。这个过程确保了双方都有能力接收和发送数据，并且初始化双方的序列号。以下是三次握手的详细步骤： 第一次握手（SYN）&…...

编程日记 2025/5/7 23:33:12

ElasticSearch学习记录

服务器操作系统版本：Ubuntu 24.04 Java版本：21 Spring Boot版本：3.3.5 如果打算用GUI，虚拟机安装Ubuntu 24.04，见虚拟机安装Ubuntu 24.04及其常用软件(2024.7)_ubuntu24.04-CSDN博客文章浏览阅读6.6k次&#xff0…...

编程日记 2025/5/7 14:55:32

10.在 Vue 3 中使用 OpenLayers 加载引用 Stamen 地图（多种形式）

在 Web 地图开发中，OpenLayers 是一个非常强大且灵活的 JavaScript 库，它可以帮助我们加载各种地图层（如 OpenStreetMap、Google Maps、Bing Maps 等）。而 Stamen 地图是一个非常常见的地图样式，它提供了多种地图样式&…...

编程日记 2025/5/5 23:23:30

json与proto序列化,反序列化性能对比

1. 说proto快,必须知道他快多少?为什么快? 快多少? // 测试proto序列化和反序列化的性能func BenchmarkProtobufMarshal(b *testing.B) {// 创建一个 Request 对象req : &demo.Request{Ping: "ping",}// 测试序列化的性能b.ResetTimer()for i : 0; i < b…...

编程日记 2025/5/6 19:56:07

[Redis#14] 持久化 | RDB | bgsave | check-rdb | 灾备

目录 0.概述持久化的策略 1 RDB 1.1 触发机制 1.2 流程说明 1.3 RDB 的优缺点 0.概述在学习 MySQL 数据库时，我们了解到事务的四个核心特性：原子性、一致性、持久性和隔离性。这些特性确保了数据库操作的安全性和可靠性。当我们转向 Redis 时&a…...

编程日记 2025/5/8 14:57:00

ubuntu部署RocketMQ

Quick Start RocketMQ 下载解压把下载的文件解压重命名，放在想放的位置需要提前配置JDK环境变量，或者直接在配置文件中指定JAVA_HOME 编辑编辑 rocketmq/bin下的 runserver.sh 和runbroker.sh文件，把内存大小改小一点，因为…...

编程日记 2025/5/8 22:39:41

深入浅出：PHP中的变量与常量全解析

文章目录引言理解变量普通变量赋值操作变量间赋值引用赋值取消引用可变变量预定义变量理解常量声明常量使用define()函数const关键字使用常量预定义常量扩展话题：作用域与生命周期实战案例总结与展望参考资料引言在编程的世界里，变量和常量是两种…...

编程日记 2025/5/9 9:53:44

概率论相关知识随记

作为基础知识的补充，随学随记，方便以后查阅。概率论相关知识随记期望（Expectation）期望的定义离散型随机变量的期望示例：掷骰子的期望连续型随机变量的期望示例：均匀分布的期望期望的性质线性性质期望的…...

编程日记 2025/5/6 17:34:27

gpt-computer-assistant - 极简的 GPT-4o 客户端

更多AI开源软件： AI开源 - 小众AIhttps://www.aiinn.cn/sources gpt-computer-assistant是一个将 ChatGPT MacOS 应用程序提供给 Windows 和 Linux 的替代工作。因此，这是一个全新且稳定的项目。此时，您可以轻松地将其作为 Python 库安装&am…...

编程日记 2025/5/8 0:11:14

【Java开发】Springboot集成mybatis-plus

1、引入 mybatis-plus 依赖 <dependency> <groupId>com.baomidou</groupId> <artifactId>mybatis-plus-boot-starter</artifactId> <version>3.5.0</version> </dependency>  <dependen…...

编程日记 2025/5/11 14:10:15

本地运行打包好的dist

首先输入打包命令每个人设置不一样一般人是npm run build如果不知道可以去package.json里去看。打包好文件如下命令行输入 :npm i -g http-server 进入到dist目录下输入命令cmd 输入 http-server 成功...

编程日记 2025/5/7 5:16:00

mac安装php和xdebug调试

要在Mac上安装PHP 7.4，你可以通过几种方式来完成，但鉴于PHP7.4官方已不再维护，并且Homebrew默认仓库中不再提供此版本，我们需要从第三方仓库或直接从源代码进行安装。本文以brew方式安装，如果安装的是8.0以上&#xff…...

编程日记 2025/5/12 21:53:15

使用Rufus制作Ubuntu需要注意

‌在使用Rufus制作Ubuntu启动盘并进行BIOS设置时，需要注意以下几点‌： ‌关闭RST（英特尔快速存储技术）‌：在BIOS设置中，如果电脑启用了RST功能，需要将其关闭。因为Ubuntu可能无法检测到硬盘&a…...

编程日记 2025/5/12 8:16:34

2024 阿里云Debian12.8安装apach2【图文讲解】

1. 更新系统，确保您的系统软件包是最新的 sudo apt update sudo apt upgrade -y 2. 安装 Apache Web 服务器 apt install apache2 -y 3. 安装 PHP 及常用的扩展 apt install php libapache2-mod-php -y apt install php-mysql php-xml php-mbstring php-curl php…...

编程日记 2025/4/27 2:25:38

iOS平台接入Facebook登录

1、FB开发者后台注册账户 2、完善App信息 3、git clone库文件代码接入 4、印尼手机卡开热点调试备注： 可能遇到的问题： 1、Cocos2dx新建的项目要更改xcode的git设置，不然卡在clone，无法在线获取FBSDK 2、动态库链接需要在…...

编程日记 2025/5/11 1:28:36

关于在ubuntu上无法运行EasyConnect的解决方法

需要这三个文件 libpangocairo-1.0-0_1.40.14-1_amd64.deb libpangoft2-1.0-0_1.40.14-1_amd64.deb libpango-1.0-0_1.40.14-1_amd64.deb然后执行 cp source /usr/share/sangfor/EasyConnect再重启EasyConnect即可下载链接 http://kr.archive.ubuntu.com/ubuntu/pool/main/…...

编程日记 2025/5/11 3:49:21

常用 Linux 各资源指标监控示例（长期更新）

1、在 linux 中，查看指定进程下各线程运行情况 # ps 方式，查看 pid 为 776 的进程有哪些线程 ps -Tp 776 #> PID SPID TTY TIME CMD #> 776 776 ? 00:00:01 zebra #> 776 778 ? 00:00:00 RCU sweeper #&g…...

编程日记 2025/5/10 23:23:54

【目标跟踪】AntiUAV600数据集详细介绍

AntiUAV600数据集的提出是为了适应真实场景，即无人机可能会随时随地出现和消失。目前提出的Anti-UAV任务都只是将其看做与跟踪其他目标一样的任务，没有结合现实情况考虑。论文链接：https://arxiv.org/pdf/2306.15767https://arxiv.org/pdf/…...

编程日记 2025/4/30 21:36:08

数学建模之RSR秩和比综合评价法（详细）

RSR秩和比综合评价法一、概述秩和比法(Rank-sum ratio，简称RSR法)是我国学者田凤调于1988年提出的，田教授是我国杰出的卫生统计学家，该方法最初提出时用于解决医学卫生领域的综合评价问题，后经各领域学者的补充和完善&#xf…...

编程日记 2025/5/8 0:40:08

【Vue3】【Naive UI】＜NAutoComplete＞标签

【Vue3】【Naive UI】标签 <NAutoComplete> 是 Naive UI 库中的一个组件，用于实现自动完成或联想输入功能。它允许用户在输入时看到与当前输入匹配的建议列表，从而帮助用户更快地填写表单字段。这个组件通常用于搜索框、地址输入等场景&#xff…...

编程日记 2025/4/24 4:10:09

SpringBoot自动装配原理

SpringBoot自动装配原理在介绍SpringBoot自动装配原理之前我们需要先看一个注解 --> SpringBootApplication SpringBootApplication public class BackendApp {public static void main(String[] args) {SpringApplication.run(BackendApp.class, args);} }我们都知道Spr…...

编程日记 2025/5/3 17:28:36

Flask: flask框架是如何实现非阻塞并发的

写在前面：Flask框架是通过多线程/多进程+阻塞的socket实现非阻塞，其本质是基于python的源库socketserver实现的前言认识WSGI协议认识Werkzeug flask是如何实现非阻塞的本文使用的flask框架为最新的1.1.1版本，所有代码基于python3运行一：前言使用过flask或者其他web框…...

编程日记 2025/5/12 6:37:03