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

代码随想录算法训练营|day30

第七章 回溯算法

  • 332.重新安排行程
  • 51.N皇后
  • 37.解数独
  • 代码随想录文章详解

332.重新安排行程

(1)参考
创建map存储src,[]dest映射关系,并对[]dest排序
每次取map中第一个dest访问,将其作为新的src,每访问一条src->dest,删除该记录。
如果访问的src没有dest了,将当前节点加入结果集,并沿栈返回。
结果是沿栈返回的,故需要逆序输出

func findItinerary(tickets [][]string) []string {res := []string{}m := make(map[string][]string, 0)for _, ticket := range tickets {src, dest := ticket[0], ticket[1]m[src] = append(m[src], dest)}for k:= range m {sort.Strings(m[k])}var help func(srcTicket string)help = func(srcTicket string) {for {if v, ok := m[srcTicket]; !ok || len(v) == 0 {break}tmp := m[srcTicket][0]m[srcTicket] = m[srcTicket][1:]help(tmp)}res = append(res, srcTicket)}help("JFK")for i, j := 0, len(res)-1; i < j; i, j = i+1, j-1 {res[i], res[j] = res[j], res[i]}return res
}

(2)回溯:超时了
排列问题。先对tickets排序,used记录当前车票是否被使用
若车票使用完并找到路径,返回,否则回溯查找路径

func findItinerary(tickets [][]string) []string {sort.Slice(tickets, func(i, j int) bool {return tickets[i][1] < tickets[j][1]})path := []string{"JFK"}used := make([]bool, len(tickets))var help func(srcTicket string, ticket [][]string) boolhelp = func(srcTicket string, ticket [][]string) bool {if len(path) == len(tickets)+1 {return true}for i, next := range tickets {if next[0] == path[len(path)-1] && !used[i] {path = append(path, next[1])used[i] = trueif help(next[1], tickets) {return true}path = path[:len(path)-1]used[i] = false}}return false}help("JFK", tickets)return path
}

51.N皇后

回溯
row控制递归深度,for循环控制列,进而确定当前位置
判断当前值是否有效:因为每行只选取一个位置,故只需判断列和正斜、反斜方向是否有皇后

func solveNQueens(n int) [][]string {res := [][]string{}board := make([][]string, n)for i := 0; i < n; i++ {board[i] = make([]string, n)}for i := 0; i < n; i++ {for j := 0; j < n; j++ {board[i][j] = "."}}var help func(row int, board [][]string) boolhelp = func(row int, board [][]string) bool {if row == n {temp := make([]string, n)for i, rowStr := range board {temp[i] = strings.Join(rowStr, "")}res = append(res, temp)}for i := 0; i < n; i++ {if isValid(n, row, i, board) {board[row][i] = "Q"if help(row+1, board) {return true}board[row][i] = "."}}return false}help(0, board)return res
}func isValid(n, row, col int, board [][]string) bool {for i := 0; i < row; i++ {if board[i][col] == "Q" {return false}}for i, j := row-1, col-1; i >= 0 && j >= 0; i, j = i-1, j-1 {if board[i][j] == "Q" {return false}}for i, j := row-1, col+1; i >= 0 && j < n; i, j = i-1, j+1 {if board[i][j] == "Q" {return false}}return true
}

37.解数独

回溯
当前位置有效性判断:行、列、九宫格数字不重复
如果当前位置能放数字,且有效,递归,否则回溯

func solveSudoku(board [][]byte) {var help func(board [][]byte) boolhelp = func(board [][]byte) bool {for i := 0; i < 9; i++ {for j := 0; j < 9; j++ {if board[i][j] == '.' {for k := '1'; k <= '9'; k++ {if isValid(i, j, byte(k), board) {board[i][j] = byte(k)if help(board) {return true}board[i][j] = '.'}}return false}}}return true}help(board)
}func isValid(row, col int, val byte, board [][]byte) bool {for i := 0; i < 9; i++ {if board[row][i] == val {return false}}for i := 0; i < 9; i++ {if board[i][col] == val {return false}}startRow := (row / 3) * 3startCol := (col / 3) * 3for i := startRow; i < startRow+3; i++ {for j := startCol; j < startCol+3; j++ {if board[i][j] == val {return false}}}return true
}

代码随想录文章详解

332.重新安排行程
51.N皇后
37.解数独
回溯总结篇

相关文章:

代码随想录算法训练营|day30

第七章 回溯算法 332.重新安排行程51.N皇后37.解数独代码随想录文章详解 332.重新安排行程 (1)参考 创建map存储src&#xff0c;[]dest映射关系&#xff0c;并对[]dest排序 每次取map中第一个dest访问&#xff0c;将其作为新的src&#xff0c;每访问一条src->dest&#xff…...

PHPExcel导出excel

PHPExcel下载地址 https://gitee.com/mirrors/phpexcelhttps://github.com/PHPOffice/PHPExcel 下载后目录结构 需要的文件如下图所示 将上面的PHPExcel文件夹和PHPExcel.php复制到你需要的地方 这是一个简单的示例代码 <?php$dir dirname(__FILE__); //require_once …...

ubuntu系统下c++ cmakelist vscode debug(带传参的debug)的详细示例

c和cmake的debug&#xff0c;网上很多都需要配置launch.json&#xff0c;cpp.json啥的&#xff0c;记不住也太复杂了&#xff0c;我这里使用cmake插件带有的设置&#xff0c;各位可以看一看啊✌(不知不觉&#xff0c;竟然了解了vscode中配置文件的生效逻辑&#x1f923;) 克隆…...

聊聊JIT优化技术

&#x1f3ac;作者简介&#xff1a;大家好&#xff0c;我是小徐&#x1f947;☁️博客首页&#xff1a;CSDN主页小徐的博客&#x1f304;每日一句&#xff1a;好学而不勤非真好学者 &#x1f4dc; 欢迎大家关注&#xff01; ❤️ 我们知道&#xff0c;想要把高级语言转变成计算…...

LabVIEW动平衡测试与振动分析系统

LabVIEW动平衡测试与振动分析系统 介绍了利用LabVIEW软件和虚拟仪器技术开发一个动平衡测试与振动分析系统。该系统旨在提高旋转机械设备的测试精度和可靠性&#xff0c;通过精确测量和分析设备的振动数据&#xff0c;以识别和校正不平衡问题&#xff0c;从而保证机械设备的高…...

《低功耗方法学》翻译——附录B:UPF命令语法

附录B&#xff1a;UPF命令语法 本章介绍了文本中引用的所选UPF命令的语法。 节选自“统一电源格式&#xff08;UPF&#xff09;标准&#xff0c;1.0版”&#xff0c;经该Accellera许可复制。版权所有&#xff1a;(c)2006-2007。Accellera不声明或代表摘录材料的准确性或内容&…...

Leetcode 3027. Find the Number of Ways to Place People II

Leetcode 3027. Find the Number of Ways to Place People II 1. 解题思路2. 代码实现 题目链接&#xff1a;3027. Find the Number of Ways to Place People II 1. 解题思路 这一题的话我也没想到啥特别好的思路&#xff0c;采用的纯粹是遍历剪枝的思路。 遍历的话好理解&…...

android inset 管理

目录 简介 Insets管理架构 Insets相关类图 app侧的类 WMS侧的类 inset show的流程 接口 流程 WMS侧确定InsetsSourceControl的流程 两个问题 窗口显示时不改变现有的inset状态 全屏窗口上的dialog 不显示statusbar问题 View 和 DecorView 设置insets信息 输入法显…...

Python中使用opencv-python库进行颜色检测

Python中使用opencv-python库进行颜色检测 之前写过一篇VC中使用OpenCV进行颜色检测的博文&#xff0c;当然使用opencv-python库也可以实现。 在Python中使用opencv-python库进行颜色检测非常简单&#xff0c;首选读取一张彩色图像&#xff0c;并调用函数imgHSV cv2.cvtColor…...

如何修改远程端服务器密钥

前言 一段时间没改密码后&#xff0c;远程就会自动提示CtrlAltEnd键修改密码。但我电脑是笔记本&#xff0c;没有end键。打开屏幕键盘按这三个键也没用。 解决方法 打开远程 1、远程端WINC 输入osk 可以发现打开了屏幕键盘 2、电脑键盘同时按住CtrlAlt&#xff08;若自身电…...

lnmp指令

LNMP官网&#xff1a;https://lnmp.org 作者: licess adminlnmp.org 问题反馈&技术支持论坛&#xff1a;https://bbs.vpser.net/forum-25-1.html 打赏捐赠&#xff1a;https://lnmp.org/donation.html 自定义参数 lnmp.conf配置文件&#xff0c;可以修改lnmp.conf自定义下…...

Go语言每日一题——链表篇(七)

传送门 牛客面试笔试必刷101题 ----------------删除链表的倒数第n个节点 题目以及解析 题目 解题代码及解析 解析 这一道题与昨天的题目在解题思路上有一定的相似之处&#xff0c;都是基于双指针定义快慢指针&#xff0c;这里我们让快指针先走n步&#xff0c;又因为n一定…...

【stomp实战】websocket原理解析与简单使用

一、WebSocket 原理 WebSocket是HTML5提供的一种浏览器与服务器进行全双工通讯的网络技术&#xff0c;属于应用层协议。它基于TCP传输协议&#xff0c;并复用HTTP的握手通道。浏览器和服务器只需要完成一次握手&#xff0c;两者之间就直接可以创建持久性的连接&#xff0c; 并…...

2024.1.30力扣每日一题——使循环数组所有元素相等的最少秒数

2024.1.30 题目来源我的题解方法一 暴力模拟&#xff08;无法通过&#xff09;方法二 哈希表数学 题目来源 力扣每日一题&#xff1b;题序&#xff1a;2808 我的题解 方法一 暴力模拟&#xff08;无法通过&#xff09; 直接暴力枚举。记录每一个元素所在的位置&#xff0c;然…...

【Java万花筒】数据魔术师:探索Java商业智能与数据可视化

开发者的数据魔杖&#xff1a;掌握Java商业智能工具的秘诀 前言 在当今信息爆炸的时代&#xff0c;数据已经成为企业决策和业务发展的重要驱动力。为了更好地理解和利用数据&#xff0c;商业智能&#xff08;BI&#xff09;和数据可视化工具变得至关重要。本文将介绍几种基于…...

python用yaml装参数并支持命令行修改

效果&#xff1a; 将实验用的参数写入 yaml 文件&#xff0c;而不是全部用 argparse 传&#xff0c;否则命令会很长&#xff1b;同时支持在命令行临时加、改一些参数&#xff0c;避免事必要在 yaml 中改参数&#xff0c;比较灵活&#xff08;如 grid-search 时遍历不同的 loss…...

第59讲订单数据下拉实现

import com.baomidou.mybatisplus.extension.plugins.pagination.Page;/*** 订单查询 type值 0 全部订单 1待付款 2 待收货 3 退款/退货* param type* return*/RequestMapping("/list")public R list(Integer type,Integer page,Integer pageSize){System.out.pri…...

[当人工智能遇上安全] 11.威胁情报实体识别 (2)基于BiGRU-CRF的中文实体识别万字详解

您或许知道&#xff0c;作者后续分享网络安全的文章会越来越少。但如果您想学习人工智能和安全结合的应用&#xff0c;您就有福利了&#xff0c;作者将重新打造一个《当人工智能遇上安全》系列博客&#xff0c;详细介绍人工智能与安全相关的论文、实践&#xff0c;并分享各种案…...

16:定时器和计数器

定时器和计数器 1、定时器和计数器的介绍2、定时器是如何工作3、寄存器4、51单片机定时器简介&#xff08;数据手册&#xff09;5、定时器中的寄存器&#xff08;数据手册&#xff09;5.1、TCON&#xff08;定时器控制寄存器&#xff09;5.2、TMOD&#xff08;工作模式寄存器&a…...

c#通过ExpressionTree 表达式树实现对象关系映射

//反射expression实现对象自动映射 void Main() {Person p1new(){Id1,Name"abc"};var persondto p1.MapTo<Person, PersonDto>();Console.WriteLine($"id:{persondto.Id}-name:{persondto.Name}"); }public static class AutoMapperExs { public s…...

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录

ASP.NET Core 是一个跨平台的开源框架&#xff0c;用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录&#xff0c;以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

day52 ResNet18 CBAM

在深度学习的旅程中&#xff0c;我们不断探索如何提升模型的性能。今天&#xff0c;我将分享我在 ResNet18 模型中插入 CBAM&#xff08;Convolutional Block Attention Module&#xff09;模块&#xff0c;并采用分阶段微调策略的实践过程。通过这个过程&#xff0c;我不仅提升…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

自然语言处理——Transformer

自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效&#xff0c;它能挖掘数据中的时序信息以及语义信息&#xff0c;但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN&#xff0c;但是…...

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)

Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败&#xff0c;具体原因是客户端发送了密码认证请求&#xff0c;但Redis服务器未设置密码 1.为Redis设置密码&#xff08;匹配客户端配置&#xff09; 步骤&#xff1a; 1&#xff09;.修…...

ip子接口配置及删除

配置永久生效的子接口&#xff0c;2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...

python报错No module named ‘tensorflow.keras‘

是由于不同版本的tensorflow下的keras所在的路径不同&#xff0c;结合所安装的tensorflow的目录结构修改from语句即可。 原语句&#xff1a; from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后&#xff1a; from tensorflow.python.keras.lay…...