算法day30 回溯6

332 重新安排行程

给你一份航线列表 tickets ,其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。

所有这些机票都属于一个从 JFK(肯尼迪国际机场)出发的先生,所以该行程必须从 JFK 开始。如果存在多种有效的行程,请你按字典排序返回最小的行程组合。

例如,行程 [“JFK”, “LGA”] 与 [“JFK”, “LGB”] 相比就更小,排序更靠前。
假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。
在这里插入图片描述

# 回溯+used
def backtracking(tickets,used,path,cur,result):
	if len(path)==len(tickets)+1:
		result.append(path[:]) # 因为剪枝,对应下面找到一个路径就返回,不能return path[:]
		return True 
	for i,ticket in enumerate(tickets):
		if ticket[0]==cur and used[i]==False:
			used[i]=True
			path.append(ticket[1])
			state=backtracking(tickets,used,path,ticket[1],result)
			path.pop()
			used[i]=False
			if state:
				return True # 找到一个路径就行,不需要再搜索
def findItinerary(tickets:'List[List[str]]')->'List[str]':
	tickets.sort() #字母小的排在前面
	used=[False]*len(tickets)
	path=['JFK']
	result=[]
	backtracking(tickets,used,path,'JKF',result):
	return result[0]

# 回溯+字典 
# 待搞懂
def findItinerary(tickets):
	target=defaultdict(list)
	for ticket in tickets:
		target[ticket[0]].append(ticket[1])
	for airport in target:
		target[airport].sort()
	path=['JFK']
	backtracking(target,path,len(tickets))
	return path 
		
def backtracking(target,path,ticketNum):
	if len(path)==ticketNum+1:
		return True
	airport=path[-1]
	destinations=target[airport]
	for i,dest in enumerate(destinations):
		target[airport].pop(i)
		path.append(dest)
		if backtracking(target,path,ticketNum):
			return True
		target[airport].insert(i,dest)
		path.pop()
	return False

51 N皇后

按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。

给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
在这里插入图片描述
在这里插入图片描述

def solveNQueens(n:int)->'List[List[str]]':
	result=[]
	chessboard=['.'*n for _ in range(n)]  # 原本n*n -> 1*n
	backtracking(n,0,chessboard,result)
	return [[''.join(row)for row in solution]for solution in result] 

def backtracking(n,row,chessboard,result):
	if row==n:
		result.append(chessboard[:])
		return 
	for col in range(n):
		if isValid(row,col,chessboard):
			chessboard[row]=chessboard[row][:col]+'Q'+chessboard[row][col+1:]
			backtracking(n,row+1,chessboard,result)
			chessboard[row]=chessboard[row][:col]+'.'+chessboard[row][col+1:]

def isValid(row,col,chessboard):
	# 是否同一列出现多个Q 
	for i in range(row):
		if chessboard[i][col]=='Q': 
			return False 
	# 是否45度角出现多个Q
	i,j=row-1,col-1
	while i>=0 and j>=0:
		if chessboard[i][j]=='Q':
			return False
		i-=1
		j-=1
	# 是否135度角出现多个Q
	i,j=row-1,col+1
	while i>=0 and j<len(chessboard):
		if chessboard[i][j]=='Q':
			return False
		i-=1
		j+=1
	return True
		

37 解数独

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

数独的解法需 遵循如下规则:

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。(请参考示例图)
数独部分空格内已填入了数字,空白格用 ‘.’ 表示。
在这里插入图片描述

def backtracking(board)->bool:
	for i in range(len(board)):#行
		for j in range(len(board[0])):#列
			if board[i][j]!='.':
				continue
			for k in range(1,10):
				if isValid(i,j,k,board):
					board[i][j]=str(k)
					if backtracking(board):
						return True
					board[i][j]='.'
			return False #1-9都不能成功填入,无解返回Fasle
	return True
def isValid(row,col,val,board)->bool:
	for i in range(9):
		if board[row][i]==str(val):
			return False
	for j in range(9):
		if board[j][col]==str(val):
			return False
	# 根据row、col判断在第几个子子宫格内
	start_row=(row//3)*3
	start_col=(col//3)*3
	for i in range(start_row,start_row+3):
		for j in range(start_col,start_col+3):
			if board[i][j]==str(val):
				return False
	return True  
def solveSudoku(board:'List[List[str]]')->None:
	backtracking(board)
	
	
		
	 

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

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

相关文章

【网站项目】果蔬经营平台系统

&#x1f64a;作者简介&#xff1a;拥有多年开发工作经验&#xff0c;分享技术代码帮助学生学习&#xff0c;独立完成自己的项目或者毕业设计。 代码可以私聊博主获取。&#x1f339;赠送计算机毕业设计600个选题excel文件&#xff0c;帮助大学选题。赠送开题报告模板&#xff…

红黑树的性质与操作:吸收红结点及其对树结构的影响

红黑树的性质与操作&#xff1a;吸收红结点及其对树结构的影响 1.红黑树的基本性质2.吸收红结点的过程2.1黑色结点的度2.2 叶结点深度 3.伪代码实现4. C语言代码实现5. 结论 红黑树作为一种高效的自平衡二叉搜索树&#xff0c;在计算机科学中扮演着重要的角色。它通过一系列复杂…

C++理解std::move和转发(std::forward)

理解 std::move 标准库move函数是使用右值引用的模板的一个很好的例子。 幸运的是&#xff0c;我们不必理解move所使用的模板机制也可以直接使用它。 但是&#xff0c;研究move是如何工作的可以帮助我们巩固对模板的理解和使用。 我们注意到&#xff0c;虽然不能直接将一个…

【C语言】linux内核pci_register_driver

一、注释 以下是对源代码中英文注释的中文翻译&#xff0c;可能会略去一些编程上的专有词汇&#xff08;例如函数名、类型名等&#xff09;&#xff0c;以使翻译更易理解。 // drivers\pci\pci-driver.c /*** __pci_register_driver - 注册一个新的PCI驱动* drv: 需要注册的驱…

【QT入门】 无边框窗口设计综合运用之自定义标题栏带圆角阴影的窗口

往期回顾&#xff1a; 【QT入门】 自定义标题栏界面qss美化按钮功能实现-CSDN博客 【QT入门】 无边框窗口设计之实现窗口阴影-CSDN博客 【QT入门】 无边框窗口设计之实现圆角窗口-CSDN博客 【QT入门】 无边框窗口设计综合运用之自定义标题栏带圆角阴影的窗口 一、最终效果 二、…

数据结构进阶篇 之 【交换排序】(冒泡排序,快速排序递归、非递归实现)

当你觉的自己不行时&#xff0c;你就走到斑马线上&#xff0c;这样你就会成为一个行人 一、交换排序 1.冒泡排序 BubbleSort 1.1 基本思想 1.2 实现原理 1.3 代码实现 1.4 冒泡排序的特性总结 2.快速排序 QuickSort 2.1 基本思想 2.2 递归实现 2.2.1 hoare版 2.2.2 …

开发环境->生产环境

1、数据迁移 不涉及docker # 以数据库用户导出数据 mysqldump -h 192.168.1.168 -P 3307 -u abragent -pabragebb17 abragent > abragent.sql# 以root用户导出数据 mysqldump -h 192.168.1.168 -P 3307 -u root -p8d3Ba1b abragent > abragent.sql 涉及docker …

java自动化学习-IntelliJ IDEA新建项目

1、新建项目 2、新建类&#xff0c;右键”src” > “new” >”Java Class” 3、重命名类名

【史上最细教程】项目本地切换Nexus私服步骤

文章目录 1.上传所有jar/pom到私服仓库方式1&#xff1a;Nexus手动上传方式2&#xff1a;mvn deploy命令上传 2.替换项目中所有pom.xml上传下载地址为私服仓库3.替换本地maven setting.xml配置文件4.下载上传验证操作下载jar出现的问题mvn deploy上传jarmvn deploy上传执行脚本…

R语言实现蒙特卡洛模拟算法

&#x1f349;CSDN小墨&晓末:https://blog.csdn.net/jd1813346972 个人介绍: 研一&#xff5c;统计学&#xff5c;干货分享          擅长Python、Matlab、R等主流编程软件          累计十余项国家级比赛奖项&#xff0c;参与研究经费10w、40w级横向 文…

java 数据结构 Map和Set

目录 搜索树 操作-查找 操作-插入 操作-删除&#xff08;难点&#xff09; Map Map 的常用方法 Set 哈希表 哈希函数 哈希冲突 冲突-避免-负载因子调节&#xff08;重点掌握&#xff09; 冲突-解决 冲突-解决-开散列/哈希桶(重点掌握) 实现HashBuck类 put方法 …

C++实现 “你被骗了” 自动拦截,反诈神器

“Never Gonna Give You Up” &#xff0c; 已经是历经十五年的名梗了&#xff0c;点开这个视频&#xff0c;就说明 你被骗了。 无论是自己点进了一些奇奇怪怪的链接&#xff0c;还是被自动跳转&#xff0c;你都不希望 展开 0x01 原理&规则 【本程序B站视频链接】快去B站…

layui框架实战案例(26):layui-carousel轮播组件添加多个Echarts图标的效果

在Layui中&#xff0c;使用layui-carousel轮播组件嵌套Echarts图表来实现多个图表的展示。 css层叠样式表 调整轮播图背景色为白色&#xff1b;调整当个Echarts图表显示loading…状态&#xff1b;同一个DIV轮播项目添加多个Echarts的 .layui-carousel {background-color: #f…

【图论】有向无环图中一个节点的所有祖先 - 邻接表(DFS)

文章目录 题目&#xff1a;有向无环图中一个节点的所有祖先题目描述代码与解题思路 题目&#xff1a;有向无环图中一个节点的所有祖先 2192. 有向无环图中一个节点的所有祖先 题目描述 代码与解题思路 func getAncestors(n int, edges [][]int) [][]int {g : make([][]int, …

C#清空窗体的背景图片

目录 一、涉及到的知识点 1.设置窗体的背景图 2.加载窗体背景图 3.清空窗体的背景图 二、 示例 一、涉及到的知识点 1.设置窗体的背景图 详见本文作者的其他文章&#xff1a;C#手动改变自制窗体的大小-CSDN博客 https://wenchm.blog.csdn.net/article/details/137027140…

链路追踪原理

分布式系统为什么需要链路追踪&#xff1f; 随着互联网业务快速扩展&#xff0c;软件架构也日益变得复杂&#xff0c;为了适应海量用户高并发请求&#xff0c;系统中越来越多的组件开始走向分布式化&#xff0c;如单体架构拆分为微服务、服务内缓存变为分布式缓存、服务组件通…

IDEA2023.1.1中文插件

1.启动IDEA 选中Customize 2.选择All settings 3.选中Plugins,再搜索栏里输入Chinese,找到 "Chinese (Simplified) Language"插件&#xff0c;点击 Install 进行安装。 4. 安装完成后&#xff0c;重启IntelliJ IDEA&#xff0c;即可看到界面语言已经变为中文。

HashMap为啥线程不安全?

1. HashMap1.7在多线程并发下扩容时&#xff0c;头插法会出现环。 /*** Rehashes the contents of this map into a new array with a* larger capacity. This method is called automatically when the* number of keys in this map reaches its threshold.** If current cap…

回溯算法|491.递增子序列

力扣题目链接 class Solution { private:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& nums, int startIndex) {if (path.size() > 1) {result.push_back(path);// 注意这里不要加return&#xff0c;要取树上…

[计算机知识] TCP/IP网络模型、MySQL的结构

TCP/IP网络模型 应用层 给用户提供应用功能&#xff0c;如HTTP, DNS 应用层处于用户态&#xff0c;传输层及以下处于内核态 传输层 给应用层提供网络支持&#xff0c;如TCP, UDP TCP提供稳定、面向连接的网络传输协议 应用层的数据可能会太大&#xff0c;就需要进行拆分…