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

【算法】回溯算法专题③ ——排列型回溯 python

news 来源：原创 2025/5/15 21:58:09

前置

【算法】回溯算法专题① ——子集型回溯 python
【算法】回溯算法专题② ——组合型回溯 + 剪枝 python

小试牛刀

全排列 https://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]]

提示：

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数互不相同

思路:

用一个vis标记数组:对已选的数字打上标记

题解:

class Solution:def permute(self, nums: List[int]) -> List[List[int]]:n = len(nums)path = []ans = []vis = [0] * (n + 1)def dfs(i):if i == n:ans.append(path.copy())returnfor j in range(n):if not vis[j]:vis[j] = 1path.append(nums[j])dfs(i + 1)path.pop()vis[j] = 0 # 别忘了回溯时将vis打回0dfs(0)return ans

当然vis标记数组可以通过递归时传入一个set参数代替

题解2:

class Solution:def permute(self, nums: List[int]) -> List[List[int]]:n = len(nums)path = []ans = []def dfs(i, s): # s:setif i == n:ans.append(path.copy())returnfor x in s:path.append(x)dfs(i + 1, s - {x})path.pop()dfs(0, set(nums)) # 用集合可以 O(1)判断元素是否在里面return ans

回归经典

N皇后 https://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”]]

提示：
1 <= n <= 9

思路:

同一对角线不能有多个皇后
（可以通过计算行号加或减列号来判断）

在这里插入图片描述

题解code:

class Solution:def solveNQueens(self, n: int) -> List[List[str]]:ans = []col = [0] * n  # col:列vis = [0] * n  # vis:标记数组diag1 = [0] * (2 * n)diag2 = [0] * (2 * n)# 分别表示两个对角线def dfs(r):  # row:行if r == n:ans.append(["." * c + "Q" + "." * (n - 1 - c) for c in col])returnfor c in range(n):if not vis[c] and not diag1[r + c] and not diag2[r - c]:col[r] = cvis[c] = diag1[r + c] = diag2[r - c] = 1dfs(r + 1)vis[c] = diag1[r + c] = diag2[r - c] = 0dfs(0)return ans

举一反三

小小变化一下,可以在对角线上,但有前提: 行号至少相差3

受伤的皇后 https://www.lanqiao.cn/problems/552/learning/

在这里插入图片描述

思路:

主要问题在于判断相同对角线上行号之差
以(2, 2)为例：
【右对角线】的点是 (1, 3)，【左对角线】的点是 (3, 3)，
可以发现：
(2, 2)和 (1, 3)的横坐标之差的绝对值=纵坐标之差的绝对值
同样的(2, 2)和 (3, 3)亦是如此，
所以判断两点是否在同一对角线，
即判断这两点的横纵坐标绝对值之差是否相等

题解code:

col = [0] * n
vis = [0] * n
diag1 = [0] * 2 * n
diag2 = [0] * 2 * ndef check(x, y):if not vis[y] and not diag1[x + y] and not diag2[x - y]:for i in range(x):if abs(i - x) == abs(col[i] - y) and abs(x - i) < 3:return 0return 1return 0def dfs(r):if r == n:global ansans += 1returnfor c in range(n):if check(r, c):col[r] = cvis[c] = diag1[r + c] = diag2[r - c] = 1dfs(r + 1)col[r] = 0vis[c] = diag1[r + c] = diag2[r - c] = 0n = int(input())
ans = 0
dfs(0)
print(ans)

总结

回溯法是一种通过尝试每一种可能性来找到所有解的算法。对于N皇后问题，特别是带有额外约束条件的问题（如本题中的皇后之间在同一条45度角斜线上至少相隔3行），回溯法是一个非常合适的选择。

END
如果有更多问题或需要进一步的帮助，可以在评论区留言讨论哦！
如果喜欢的话，请给博主点个关注谢谢

【算法】回溯算法专题③ ——排列型回溯 python

目录前置小试牛刀回归经典举一反三总结前置【算法】回溯算法专题① ——子集型回溯 python 【算法】回溯算法专题② ——组合型回溯剪枝 python 小试牛刀全排列 https://leetcode.cn/problems/permutations/description/ 给定一个不含重复数字的数组 nums ，返…...

编程日记 2025/5/15 21:58:09

利用deepseek参与软件测试基本架构如何又该在什么环节接入deepseek

利用DeepSeek参与软件测试，可以考虑以下基本架构和接入环节： ### 基本架构 - **数据层** - **测试数据存储**：用于存放各种测试数据，包括正常输入数据、边界值数据、异常数据等，这些数据可以作为DeepSeek的输入&…...

编程日记 2025/5/15 21:20:03

99.20 金融难点通俗解释：中药配方比喻马科维茨资产组合模型(MPT)

目录 0. 承前1. 核心知识点拆解2. 中药搭配比喻方案分析2.1 比喻的合理性 3. 通俗易懂的解释3.1 以中药房为例3.2 配方原理 4. 实际应用举例4.1 基础配方示例4.2 效果说明 5. 注意事项5.1 个性化配置5.2 定期调整 6. 总结7. 代码实现 0. 承前本文主旨： 本文通过中…...

编程日记 2025/5/12 16:45:38

为AI聊天工具添加一个知识系统之79 详细设计之20 正则表达式之7

本文要点要点 “正则表达式” 本来是计算机科学计算机科学的一个概念。本项目将它推广（扩张）到认知科学的“认知范畴”概念， 聚合（收敛）到神经科学的“神经元”概念。做法是：用reg 来系统化定义认知…...

编程日记 2025/5/13 9:41:16

[ Spring ] Spring Boot Mybatis++ 2025

文章目录 StructureMyBatis Controller AbilitiesConfigure Plugins and RepositoriesApply Plugins and Add DependenciesMyBatis Spring PropertiesMyBatis ApplicationMyBatis BeansMyBatis MapperMyBatis Query Builder Structure this blog introduce 3 ways using mybat…...

编程日记 2025/5/15 21:01:46

虚幻基础17：动画层接口

能帮到你的话，就给个赞吧 😘 文章目录 animation layer interface animation layer interface 动画层接口：动画图表的集。仅有名字。添加到动画蓝图中，由动画蓝图实现动画图表。...

编程日记 2025/5/15 20:50:58

前缀和算法

文章目录算法总览题目1371.每个元音包含偶数次的最长子字符串算法总览题目 1371.每个元音包含偶数次的最长子字符串 1371.每个元音包含偶数次的最长子字符串参考博主的讲解思路分析：就是得使用前缀和记录情况，dp[i][j]表示s[0] 到s[i] 中&…...

编程日记 2025/5/15 21:11:09

稀疏混合专家架构语言模型（MoE）

注：本文为 “稀疏混合专家架构语言模型（MoE）” 相关文章合辑。手把手教你，从零开始实现一个稀疏混合专家架构语言模型（MoE） 机器之心 2024年02月11日 12:21 河南选自huggingface 机器之心编译机器之心…...

编程日记 2025/5/14 23:57:23

深入理解 `box-sizing: border-box；`：CSS 布局的利器

深入理解 box-sizing: border-box;：CSS 布局的利器默认行为示例代码使用 box-sizing: border-box;示例代码全局应用 box-sizing: border-box;示例代码实际应用场景1. 表单布局2. 网格布局总结在 CSS 中，box-sizing 属性决定了元素的总宽度和高度是…...

编程日记 2025/5/12 14:18:26

MySQL不适合创建索引的11种情况

文章目录前言1. **数据量小的表**2. **频繁更新的列**3. **低选择性的列**4. **频繁插入和删除的表**5. **查询中很少使用的列**6. **大文本或BLOB列**7. **复合索引中未使用的前导列**8. **频繁进行批量插入的表**9. **查询返回大部分数据的表**10. **临时表**11. **列值频繁…...

编程日记 2025/5/12 9:47:58

shell呈现数据——在脚本中重定向

重定向输出只需简单地重定向相应的文件描述符，就可以在脚本中用文件描述符STDOUT和STDERR在多个位置生成输出。在脚本中重定向输出的方法有两种。临时重定向每一行。永久重定向脚本中的所有命令。下面将具体展示这两种方法的工作原理。 1.临时重定向如果你…...

编程日记 2025/5/13 9:41:03

vector容器（详解）

本文最后是模拟实现全部讲解，文章穿插有彩色字体，是我总结的技巧和关键 1.vector的介绍及使用 1.1 vector的介绍 https://cplusplus.com/reference/vector/vector/（vector的介绍） 了解 1. vector是表示可变大小数组的序列容器。…...

编程日记 2025/5/15 20:43:27

【初/高中生讲机器学习】0. 本专栏 “食用” 指南——写在一周年之际⭐

创建时间：2025-01-27 首发时间：2025-01-29 最后编辑时间：2025-01-29 作者：Geeker_LStar 你好呀~这里是 Geeker_LStar 的人工智能学习专栏，很高兴遇见你~ 我是 Geeker_LStar，一名高一学生，热爱计…...

编程日记 2025/5/13 3:28:35

SAP SD学习笔记28 - 请求计划(开票计划)之2 - Milestone请求(里程碑开票)

上一章讲了请求计划（开票计划）中的定期请求。 SAP SD学习笔记27 - 请求计划(开票计划)之1 - 定期请求-CSDN博客本章继续来讲请求计划（开票计划）的其他内容： Milestone请求(里程碑请求)。目录 1，Miles…...

编程日记 2025/5/15 2:12:06

【PyTorch介绍】

PyTorch 是什么？ PyTorch 是一个开源的深度学习框架，由 Facebook 的人工智能研究实验室（FAIR）开发和维护。它是一个基于 Python 的库，专为深度学习和人工智能研究设计，支持动态计算图（dynamic …...

编程日记 2025/5/15 17:49:53

语言月赛 202412【正在联系教练退赛】题解（AC）

》》》点我查看「视频」详解》》》 [语言月赛 202412] 正在联系教练退赛题目背景在本题中，我们称一个字符串 y y y 是一个字符串 x x x 的子串，当且仅当从 x x x 的开头和结尾删去若干个（可以为 0 0 0 个）字符后剩余的字…...

编程日记 2025/5/14 9:29:12

【C++】B2122 单词翻转

博客主页： [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: C 文章目录 💯前言💯题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 💯一、我的做法代码实现：代码解析思路分析 💯二、老师的第一种做法代码实现&a…...

编程日记 2025/5/11 22:07:00

redis基本数据结构

基本数据结构 String String是Redis中最常见的数据存储类型： 其基本编码方式是RAW，基于简单动态字符串（SDS）实现，存储上限为512mb。如果存储的SDS长度小于44字节，则会采用EMBSTR编码，此时ob…...

编程日记 2025/5/12 10:25:30

基于STM32景区环境监测系统的设计与实现（论文+源码）

1系统方案设计根据系统功能的设计要求，展开基于STM32景区环境监测系统设计。如图2.1所示为系统总体设计框图。系统以STM32单片机作为系统主控模块，通过DHT11传感器、MQ传感器、声音传感器实时监测景区环境中的温湿度、空气质量以及噪音数据。系统监测环…...

编程日记 2025/5/13 10:09:19

使用冒泡排序模拟实现qsort函数

1.冒泡排序 #define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h>int main() {int arr[] { 0,2,5,3,4,8,9,7,6,1 };int sz sizeof(arr) / sizeof(arr[0]);//冒泡排序一共排序 sz-1 趟for (int i 0; i < sz - 1; i){//标志位，如果有序，直接…...

编程日记 2025/5/14 17:33:54

探秘Linux IO虚拟化：virtio的奇幻之旅

在当今数字化时代，虚拟化技术早已成为推动计算机领域发展的重要力量。想象一下，一台物理主机上能同时运行多个相互隔离的虚拟机，每个虚拟机都仿佛拥有自己独立的硬件资源，这一切是如何实现的呢？今天，就让我…...

编程日记 2025/5/15 16:01:14

在React中使用redux

一、首先安装两个插件 1.Redux Toolkit 2.react-redux 第一步：创建模块counterStore 第二步：在store的入口文件进行子模块的导入组合第三步：在index.js中进行store的全局注入第四步：在组件中进行使用第五步：在组件中…...

编程日记 2025/5/14 4:35:11

从 C 到 C++：理解结构体中字符串的存储与操作

对于刚入门 C/C 的程序员来说，字符串的存储和操作可能是个容易混淆的知识点。在 C 中，std::string 提供了非常友好的接口，我们可以轻松地在结构体中使用字符串类型，无需关注底层细节。然而，在 C 语言中，字符…...

编程日记 2025/5/15 5:59:12

2.3学习总结

图： 1.图的基本概念 2.图的存储和遍历 3.最小生成树 4.最短路径 5.拓扑排序和关键路径一、图的基本概念图的定义：不允许没有顶点，但边集可以为空 {无向图 {有向图：边弧，弧头（有箭头）…...

编程日记 2025/5/13 9:24:20

wordpress代码结构解析

WordPress 是一个基于 PHP 和 MySQL 的开源内容管理系统（CMS），广泛用于构建网站和博客。要解析 WordPress 代码，首先需要了解其核心结构、主要文件和常用的函数。以下是 WordPress 代码解析的基本指南： --- ### 1. *…...

编程日记 2025/5/10 1:20:40

使用 Numpy 自定义数据集，使用pytorch框架实现逻辑回归并保存模型，然后保存模型后再加载模型进行预测，对预测结果计算精确度和召回率及F1分数

1. 导入必要的库首先，导入我们需要的库：Numpy、Pytorch 和相关工具包。 import numpy as np import torch import torch.nn as nn import torch.optim as optim from sklearn.metrics import accuracy_score, recall_score, f1_score2. 自定义数据集 …...

编程日记 2025/5/12 9:05:37

FPGA|例化生成的PLL功能IP核

1、例化上一篇文章中调用的IP核，新建文件PLL_test.v 2、代码如图 timescale 1ns / 1ps module PLL_test(input clk,input rst_n,output clkout0,output clkout1,output clkout2,output clkout3,output clkout4);wire locked;PLL pll_inst(.inclk0(clk),.c0(clkout0)…...

编程日记 2025/5/15 13:53:53

K个不同子数组的数目--滑动窗口--字节--亚马逊

Stay hungry, stay foolish 题目描述给定一个正整数数组 nums和一个整数 k，返回 nums 中「好子数组」的数目。如果 nums 的某个子数组中不同整数的个数恰好为 k，则称 nums 的这个连续、不一定不同的子数组为「好子数组」。例如，[1,2,…...

编程日记 2025/5/15 16:23:36

手机连接WIFI可以上网，笔记本电脑连接WIFI却不能上网？解决方法？

原因：DNS受污染了解决办法 step 1：清空域名解析记录（清空DNS） ipconfig /flushdns (Windows cmd命令行输入) step 2：重新从DHCP 获取IP ipconfig /release（释放当前IP地址） ipconfig /renew &…...

编程日记 2025/5/15 16:23:35

大模型综述一镜到底（全文八万字） ——《Large Language Models: A Survey》

论文链接：https://arxiv.org/abs/2402.06196 摘要：自2022年11月ChatGPT发布以来，大语言模型（LLMs）因其在广泛的自然语言任务上的强大性能而备受关注。正如缩放定律所预测的那样，大语言模型通过在大量文本数…...

编程日记 2025/5/15 16:23:34

C语言按位取反【~】详解，含原码反码补码的0基础讲解【原码反码补码严格意义上来说属于计算机组成原理的范畴，不过这也是学好编程初级阶段的必修课】

目录概述【适合0基础看的简要描述】： 上述加粗下划线的内容提取版： 从上述概述中提取的核心知识点，需背诵： 整数【包含整数，负整数和0】的原码反码补码相互转换的过程图示： 过程详细刨析：…...

编程日记 2025/5/15 16:23:32

本地部署与使用SenseVoice语音大模型简析

前言 SenseVoice 是一种语音基础模型，具有多种语音理解功能，包括自动语音识别 (ASR)、口语识别 (LID)、语音情感识别 (SER) 和音频事件检测 (AED)。本博客将指导您安装和使用 SenseVoice 模型，使其尽可能方便用户使用。 Github 仓库链接: ht…...

编程日记 2025/5/15 16:23:31

QMK启用摇杆和鼠标按键功能

虽然选择了触摸屏，我仍选择为机械键盘嵌入摇杆模块，这本质上是对"操作连续性"的执着。值得深思的是，本次开发过程中借助DeepSeek的代码生成与逻辑推理，其展现的能力已然颠覆传统编程范式，需求描述可自动…...

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

排序算法与查找算法

1.十大经典排序算法我们希望数据以一种有序的形式组织起来，无序的数据我们要尽量将其变得有序一般说来有10种比较经典的排序算法简单记忆为Miss D----D小姐时间复杂度 ：红色<绿色<蓝色空间复杂度：圆越大越占空间稳定性&…...

编程日记 2025/5/15 16:23:29

基于Spring Security 6的OAuth2 系列之九 - 授权服务器--token的获取

之所以想写这一系列，是因为之前工作过程中使用Spring Security OAuth2搭建了网关和授权服务器，但当时基于spring-boot 2.3.x，其默认的Spring Security是5.3.x。之后新项目升级到了spring-boot 3.3.0，结果一看Spring Security也升级…...

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

【思维导图】redis

学习计划：将目前已经学的知识点串成一个思维导图。在往后的学习过程中，不断往思维导图里补充，形成自己整个知识体系。对于思维导图里的每个技术知识，自己用简洁的话概括出来， 训练自己的表达能力。...

编程日记 2025/5/14 23:50:55

【Git】使用笔记总结

目录概述安装Git注册GitHub配置Git常用命令常见场景1. 修改文件2. 版本回退3. 分支管理常见问题1. git add [中文文件夹] 无法显示中文问题2. git add [文件夹] 文件名中含有空格3. git add 触发 LF 回车换行警告4. git push 提示不存在 Origin 仓库5. Git与GitHub中默认分支…...

编程日记 2025/5/14 17:24:00

cf div3 998 E(并查集）

E : 给出两个简单无向图 （没有重边和自环）f g . 可以对f 进行删边和加边的操作。问至少操作多少次 ，使得 f 和 g 的点的联通情况相同（并查集的情况相同） 首先思考删边 ： 对于我 f 图存在边 e &#x…...

编程日记 2025/5/15 16:23:25

【C++】string类(上)：string类的常用接口介绍

文章目录前言一、C中设计string类的意义二、string类的常用接口说明1. string类对象的常见构造2. string类对象的容量操作2.1 size、capacity 和 empty的使用2.2 clear的使用2.3 reserve的使用2.4 resize的使用 3. string类对象的访问及遍历操作3.1 下标[ ] 和 at3.2 迭代器it…...

编程日记 2025/5/15 16:23:24

[SAP ABAP] ABAP SQL跟踪工具

事务码ST05 操作步骤步骤1：使用事务码ST05之前，将要检测的程序生成的页面先呈现出来，这里我们想看下面程序的取数操作，所以停留在选择界面步骤2： 新建一个GUI窗口，输入事务码ST05，点击 Acti…...

编程日记 2025/5/15 16:23:23

OpenGL学习笔记（六）：Transformations 变换（变换矩阵、坐标系统、GLM库应用）

文章目录向量变换使用GLM变换（缩放、旋转、位移）将变换矩阵传递给着色器坐标系统与MVP矩阵三维变换绘制3D立方体 & 深度测试（Z-buffer）练习1——更多立方体现在我们已经知道了如何创建一个物体、着色、加入纹理。但它们都还…...

编程日记 2025/5/15 16:23:23

PHP 常用函数2025.02

PHP implode() 函数语法 implode(separator,array) 参数描述separator可选。规定数组元素之间放置的内容。默认是 ""（空字符串）。array必需。要组合为字符串的数组。技术细节返回值：返回一个由数组元素组合成的字符串。PHP 版…...

编程日记 2025/5/15 16:23:21

17.3.4 颜色矩阵

编程日记 2025/5/15 16:23:20

1. 【.NET 8 实战--孢子记账--从单体到微服务--转向微服务】--前言

在我们的专栏《单体开发》中，我们实现了一个简单的记账软件的服务端，并且成功上线。随着用户数量的不断增长，问题逐渐开始显现。访问量逐渐增加，服务端的压力也随之加大。随着访问量的攀升，服务端的响应时间变得越来越…...

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

02.04 数据类型

请写出以下几个数据的类型： 整数 a ----->int a的地址 ----->int* 存放a的数组b ----->int[] 存放a的地址的数组c ----->int*[] b的地址 ----->int* c的地址 ----->int** 指向printf函数的指针d ----->int (*)(const char*, ...) …...

编程日记 2025/5/11 18:20:02

WPS动画：使图形平移、围绕某个顶点旋转一定角度

1、平移案例三角形如下图，需求：该三角形的A点平移至原点 （1）在预想动画结束的位置绘制出图形 （2）点击选中原始图像，插入/动画/绘制自定义路径/直线 （3）十字星绘制的直线…...

编程日记 2025/5/13 9:24:16

想表示消息返回值为Customer集合

道奈特(240***10) 14:34:55 EA中序列图。我想表示消息返回值为 Customer 集合。目前只有一个Customer实体类，我需要另外新建一个CustomerList 类吗？ 潘加宇(35***47) 17:01:26 不需要。如果是分析，在类的操作中，定义一个参数&…...

编程日记 2025/5/15 16:23:19

93，【1】buuctf web [网鼎杯 2020 朱雀组]phpweb

进入靶场页面一直在刷新在 PHP 中，date() 函数是一个非常常用的处理日期和时间的函数，所以应该用到了再看看警告的那句话 Warning: date(): It is not safe to rely on the systems timezone settings. You are *required* to use the date.timez…...

编程日记 2025/5/15 16:23:18

五、定时器实现呼吸灯

5.1 定时器与计数器简介定时器是一种通过对内部时钟脉冲计数来测量时间间隔的模块。它的核心是一个递增或递减的寄存器（计数器值）。如果系统时钟为 1 MHz，定时器每 1 μs 计数一次。计数器是一种对外部事件（如脉冲信号&#xff…...

编程日记 2025/5/15 16:23:17

顺序打印数字的进一步理解

之前博客写了篇博文，面试时要求使用多线程顺序打印ABC循环20次，这是我当时使用join函数实现代码： public class TestABCJoin {public static void main(String[] args) {// 创建任务Runnable taskA () -> {for (int i 0; i < 5; i) …...

编程日记 2025/5/13 23:52:58

目录

前置

小试牛刀

回归经典

举一反三

总结

相关文章：