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

算法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]=Truepath.append(ticket[1])state=backtracking(tickets,used,path,ticket[1],result)path.pop()used[i]=Falseif 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 Trueairport=path[-1]destinations=target[airport]for i,dest in enumerate(destinations):target[airport].pop(i)path.append(dest)if backtracking(target,path,ticketNum):return Truetarget[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*nbacktracking(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度角出现多个Qi,j=row-1,col-1while i>=0 and j>=0:if chessboard[i][j]=='Q':return Falsei-=1j-=1# 是否135度角出现多个Qi,j=row-1,col+1while i>=0 and j<len(chessboard):if chessboard[i][j]=='Q':return Falsei-=1j+=1return 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]!='.':continuefor k in range(1,10):if isValid(i,j,k,board):board[i][j]=str(k)if backtracking(board):return Trueboard[i][j]='.'return False #1-9都不能成功填入,无解返回Faslereturn True
def isValid(row,col,val,board)->bool:for i in range(9):if board[row][i]==str(val):return Falsefor j in range(9):if board[j][col]==str(val):return False# 根据row、col判断在第几个子子宫格内start_row=(row//3)*3start_col=(col//3)*3for i in range(start_row,start_row+3):for j in range(start_col,start_col+3):if board[i][j]==str(val):return Falsereturn True  
def solveSudoku(board:'List[List[str]]')->None:backtracking(board)

相关文章:

算法day30 回溯6

332 重新安排行程 给你一份航线列表 tickets &#xff0c;其中 tickets[i] [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。 所有这些机票都属于一个从 JFK&#xff08;肯尼迪国际机场&#xff09;出发的先生&#xff0c;所以该行程必须从 JFK …...

分享three.js实现乐高小汽车

前言 Web脚本语言JavaScript入门容易&#xff0c;但是想要熟练掌握却需要几年的学习与实践&#xff0c;还要在弱类型开发语言中习惯于使用模块来构建你的代码&#xff0c;就像小时候玩的乐高积木一样。 应用程序的模块化理念&#xff0c;通过将实现隐藏在一个简单的接口后面&a…...

gpt的构造和原理

gpt是序列预测模型。 问答是通过确定问答格式样本训练出来的&#xff01;比如“Q&#xff1a;xxxx.A:xxx"本质还是根据前面的序列预测后面的序列。在自回归训练过程中&#xff0c;文本序列&#xff08;可能包含问题和紧随其后的答案&#xff09;被视为一个整体输入到模型…...

基于springboot实现教师人事档案管理系统项目【项目源码+论文说明】计算机毕业设计

基于springboot实现IT技术交流和分享平台系统演示 摘要 我国科学技术的不断发展&#xff0c;计算机的应用日渐成熟&#xff0c;其强大的功能给人们留下深刻的印象&#xff0c;它已经应用到了人类社会的各个层次的领域&#xff0c;发挥着重要的不可替换的作用。信息管理作为计算…...

K8S之Job和CronJob控制器

这里写目录标题 Job概念适用场景使用案例 CronJob概念适用场景使用案例 Job 概念 Job控制器用于管理Pod对象运行一次性任务&#xff0c;例如&#xff1a;对数据库备份&#xff0c;可以直接在k8s上启动一个mysqldump备份程序&#xff0c;也可以启动一个pod&#xff0c;这个pod…...

基于SSM的基于个人需求和地域特色的外卖推荐系统(有报告)。Javaee项目。ssm项目。

演示视频&#xff1a; 基于SSM的基于个人需求和地域特色的外卖推荐系统&#xff08;有报告&#xff09;。Javaee项目。ssm项目。 项目介绍&#xff1a; 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#xff09;三层体系结构&…...

哈佛大学商业评论 --- 第三篇:真实世界中的增强现实

AR将全面融入公司发展战略&#xff01; AR将成为人类和机器之间的新接口&#xff01; AR将成为人类的关键技术之一&#xff01; 请将此文转发给您的老板&#xff01; --- 本文作者&#xff1a;Michael E.Porter和James E.Heppelmann 虽然物理世界是三维的&#xff0c;但大…...

华为ICT七力助推文化产业新质生产力发展

创新起主导作用的新质生产力由新劳动者、新劳动对象、新劳动工具、新基础设施等四大要素共同构成&#xff0c;符合新发展理念的先进生产力质态&#xff1b;具有高科技、高能效、高质量等三大突出特征。而通过壮大新产业、打造新模式、激发新动能&#xff0c;新质生产力能够摆脱…...

FastGpt流程

1.知识库 引入文本——>数据清洗 最好将pdf/ppt/xx转换成文本&#xff0c;在文本里面进行数据清洗&#xff08;以防知识库删除后&#xff0c;数据清洗失效&#xff09; 可以插图&#xff0c;将图片通过网页检查F12查看路径放进去 或者直接在csdn放&#xff0c;直接复制链接…...

怎么在UE游戏中加入原生振动效果

我是做振动触感的。人类的五感“视听嗅味触”&#xff0c;其中的“触”就是触觉&#xff0c;是指皮肤、毛发与物体接触时的感觉。触感可以带来更加逼真的沉浸式体验。但也许过于司空见惯&#xff0c;也是习以为常&#xff0c;很多人漠视了触感的价值。大家对触感的认知还远远不…...

【Hadoop技术框架-MapReduce和Yarn的详细描述和部署】

前言&#xff1a; &#x1f49e;&#x1f49e;大家好&#xff0c;我是书生♡&#xff0c;今天的内容主要是Hadoop的后两个组件&#xff1a;MapReduce和yarn的相关内容。同时还有Hadoop的完整流程。希望对大家有所帮助。感谢大家关注点赞。 &#x1f49e;&#x1f49e;前路漫漫&…...

蓝桥杯刷题 前缀和与差分-[3507]异或和之和(C++)

题目描述 给定一个数组 Ai&#xff0c;分别求其每个子段的异或和&#xff0c;并求出它们的和。 或者说&#xff0c;对于每组满足 1≤L≤R≤n 的 L&#xff0c;R求出数组中第 L 至第 R 个元素的异或和。 然后输出每组 L&#xff0c;R 得到的结果加起来的值。 输入格式 输入…...

background背景图参数边渐变CSS中创建背景图像的渐变效果

效果:可以看到灰色边边很难受,希望和背景融为一体 原理: 可以使用线性渐变&#xff08;linear-gradient&#xff09;或径向渐变&#xff08;radial-gradient&#xff09;。以下是一个使用线性渐变作为背景图像 代码: background: linear-gradient(to top, rgba(255,255,255,0)…...

『大模型笔记』吴恩达:AI 智能体工作流引领人工智能新趋势

吴恩达:AI 智能体工作流引领人工智能新趋势 文章目录 一. 概述二. AI 智能体的设计模式2.1. 反思(Reflection)2.2. 使用工具(Tool use)2.3. 规划(Planning)2.4. 多智能体协作(Multi-agent collaboration)三. 最后总结四. 参考文献一. 概述 我期待与大家分享我在 AI 智能体方面…...

腾讯光子工作室群 一面 (30min)

问题&#xff1a; 你毕业是打算考研还是直接工作 深挖项目&#xff08;介绍、剖析遇到问题如何解决&#xff09;&#xff1a; 你在进行攻击的时候会不会有穿模的情况&#xff0c;怎么解决 为什么会造成卡顿&#xff08;多嘴说的&#xff09; 说说行为树和状态机之间的差别 …...

Linux的信号栈的实现(1)

作者 pengdonglin137@163.com 环境 Linux 6.5 + ARM64 概述 在前一篇文章中介绍了Linux系统中的几种栈以及它们之间的切换,进程在用户态和内核态会使用不同的栈,在用户态的主线程和其他线程都有各自的栈,此外进程在执行信号处理程序时也需要栈,那么这个栈来自哪呢? …...

Python学习笔记——heapq

堆排序 思路 堆排序思路是&#xff1a; 将数组以二叉树的形式分析&#xff0c;令根节点索引值为0&#xff0c;索引值为index的节点&#xff0c;子节点索引值分别为index*21、index*22&#xff1b;对二叉树进行维护&#xff0c;使得每个非叶子节点的值&#xff0c;都大于或者…...

搜索与图论——拓扑排序

有向图的拓扑排序就是图的宽度优先遍历的一个应用 有向无环图一定存在拓扑序列&#xff08;有向无环图又被称为拓扑图&#xff09;&#xff0c;有向有环图一定不存在拓扑序列。无向图没有拓扑序列。 拓扑序列&#xff1a;将一个图排成拓扑序后&#xff0c;所有的边都是从前指…...

linux CentOS7配置docker的yum源并安装

[TOC](这里写目录标题 配置yum源Docker的自动化安装一些其他启动相关的命令&#xff1a; 配置yum源 使用以下命令下载CentOS官方的yum源文件 wget -O /etc/yum.repos.d/CentOS-Base.repo http://mirrors.aliyun.com/repo/Centos-7.repo 清除yum缓存 yum clean all 更新yum缓存…...

vue结合Elempent-Plus/UI穿梭框更改宽度以及悬浮文本显示

由于分辨率不同会导致文本内容显示不全&#xff0c;如下所示&#xff1a; 因此需要 1、悬浮到对应行上出现悬浮信息 实现代码如下所示&#xff1a; 这里只演示Vue3版本代码&#xff0c;Vue2版本不再演示 区别就在插槽使用上Vue3使用&#xff1a;#default“”&#xff1b;Vu…...

人脸检测开源生态新成员:cv_resnet101_face-detection_cvpr22papermogface ModelScope集成详解

人脸检测开源生态新成员&#xff1a;cv_resnet101_face-detection_cvpr22papermogface ModelScope集成详解 1. 项目概述 今天要介绍的是一个特别实用的人脸检测工具——基于MogFace模型开发的本地高精度人脸检测系统。这个工具解决了PyTorch新版本加载旧模型的兼容性问题&…...

ai辅助c语言开发:让快马智能生成复杂格式文件读写代码

最近在开发一个C语言程序时需要处理自定义数据包格式&#xff0c;正好体验了用AI辅助开发的便捷。这个数据包格式包含包头标识、包体长度和JSON格式的包体数据&#xff0c;需要实现读写功能。下面分享我的实现过程和AI辅助开发的实用技巧。 数据包结构分析 首先明确数据包由三部…...

Llama-3.2V-11B-cot惊艳效果:多对象遮挡场景下的因果关系链推演

Llama-3.2V-11B-cot惊艳效果&#xff1a;多对象遮挡场景下的因果关系链推演 1. 视觉推理新标杆 在计算机视觉领域&#xff0c;多对象遮挡场景下的因果关系推演一直是个技术难题。传统方法往往只能识别可见部分&#xff0c;而无法理解遮挡背后的逻辑关系。Llama-3.2V-11B-cot的…...

Java 面试八股文(全网最全20w字)

一、Java 基础知识 1、Object 类相关方法 getClass 获取当前运行时对象的 Class 对象。hashCode 返回对象的 hash 码。clone 拷贝当前对象&#xff0c; 必须实现 Cloneable 接口。浅拷贝对基本类型进行值拷贝&#xff0c;对引用类型拷贝引用&#xff1b;深拷贝对基本类型进行…...

【OpenClaw 全面解析:从零到精通】第 025 篇:OpenClaw v2026.3.22+v2026.3.23 安全与架构全面升级:从版本迭代看 AI Agent 工程化实践

系列说明&#xff1a;本系列全面介绍 OpenClaw 开源 AI 智能体框架&#xff0c;从历史背景到核心原理&#xff0c;从安装部署到应用生态。本文为系列第 025 篇&#xff0c;结合 2026 年 3 月 22-24 日最新发布的双版本合并更新&#xff0c;系统解析 OpenClaw 从功能驱动到安全驱…...

从零开始:使用Python Add-in快速构建ArcGIS自定义工具条

1. Python Add-in入门&#xff1a;ArcGIS插件开发新选择 第一次接触ArcGIS插件开发时&#xff0c;我被各种复杂的开发方式搞得晕头转向。直到发现了Python Add-in这个神器&#xff0c;才发现原来开发自定义工具条可以这么简单&#xff01;Python Add-in是Esri在ArcGIS 10.1引入…...

软电话通话30秒自动挂断?一文讲透FreeSWITCH通话超时问题

当你满怀期待地搭建好FreeSWITCH&#xff0c;用两个软电话成功呼叫&#xff0c;却发现通话总是在30秒左右莫名其妙地中断——别急&#xff0c;这是SIP新手最常遇到的“经典Bug”。本文将为你抽丝剥茧&#xff0c;彻底解决这个问题&#xff0c;并附带其他可能引发通话异常中断的…...

多平台网络资源捕获工具:突破下载限制的技术实现与场景化应用

多平台网络资源捕获工具&#xff1a;突破下载限制的技术实现与场景化应用 【免费下载链接】res-downloader 资源下载器、网络资源嗅探&#xff0c;支持微信视频号下载、网页抖音无水印下载、网页快手无水印视频下载、酷狗音乐下载等网络资源拦截下载! 项目地址: https://gitc…...

魔兽世界插件开发完全指南:专业API文档与宏工具平台

魔兽世界插件开发完全指南&#xff1a;专业API文档与宏工具平台 【免费下载链接】wow_api Documents of wow API -- 魔兽世界API资料以及宏工具 项目地址: https://gitcode.com/gh_mirrors/wo/wow_api 魔兽世界插件开发是每位进阶玩家提升游戏体验的必经之路&#xff0c…...

告别串口!STM32F105RCT6的ITM调试秘籍:从零配置到华为/高通项目级日志封装

STM32F105RCT6 ITM调试实战&#xff1a;企业级日志系统设计与性能优化 在嵌入式开发领域&#xff0c;调试效率直接影响项目进度和质量。传统串口调试方式虽然简单易用&#xff0c;但在处理复杂企业级项目时往往显得力不从心。本文将深入探讨基于STM32F105RCT6的ITM调试技术&…...