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

代码随想录算法训练营第三十天 | 332.重新安排行程 51. N皇后 37. 解数独 总结

打卡第30天,回溯算法第二刷。

今日任务

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

332.重新安排行程

给你一份航线列表 tickets ,其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
所有这些机票都属于一个从 JFK(肯尼迪国际机场)出发的先生,所以该行程必须从 JFK 开始。如果存在多种有效的行程,请你按字典排序返回最小的行程组合。
例如,行程 [“JFK”, “LGA”] 与 [“JFK”, “LGB”] 相比就更小,排序更靠前。
假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。

在这里插入图片描述
在这里插入图片描述

代码随想录

class Solution {
public:unordered_map<string, map<string, int>> targets;bool backtracking(int ticketNum, vector<string>& res) {if(res.size() == ticketNum + 1) return true;for(pair<const string, int>& target : targets[res[res.size() - 1]]) {if(target.second > 0) {res.push_back(target.first);target.second--;if (backtracking(ticketNum, res)) return true;target.second++;res.pop_back();}}return false;}vector<string> findItinerary(vector<vector<string>>& tickets) {targets.clear();vector<string> res;for(const vector<string>& vec: tickets) {targets[vec[0]][vec[1]]++;}res.push_back("JFK");backtracking(tickets.size(), res);return res;}
};

51.N皇后

按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

代码随想录

class Solution {
public:vector<vector<string>> res;bool isVaild(int row, int col,int n, vector<string>& chessborad) {for(int i = 0; i < row; i++) {if(chessborad[i][col] == 'Q') return false;}for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {if(chessborad[i][j] == 'Q') return false;}for(int i = row  - 1, j = col + 1; i >= 0 && j < n; i--, j++) {if(chessborad[i][j] == 'Q') return false;}return true;}void backtarcking(int n, int row, vector<string>& chessborad) {if(row == n) {res.push_back(chessborad);return;}for(int col = 0; col < n; col++) {if(isVaild(row, col, n, chessborad)) {chessborad[row][col] = 'Q';backtarcking(n, row + 1, chessborad);chessborad[row][col] = '.';}}}vector<vector<string>> solveNQueens(int n) {res.clear();vector<string> chessborad(n, string(n, '.'));backtarcking(n, 0, chessborad);return res;}
};

37.解数独

编写一个程序,通过填充空格来解决数独问题。
数独的解法需 遵循如下规则:
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。(请参考示例图)
数独部分空格内已填入了数字,空白格用 ‘.’ 表示。

在这里插入图片描述
在这里插入图片描述

代码随想录

在这里插入图片描述
一个for循环遍历棋盘的行,一个for循环遍历棋盘的列,一行一列确定下来之后,递归遍历这个位置放9个数字的可能性!

class Solution {
public:bool backtracking(vector<vector<char>>& board) {for(int i = 0; i < board.size(); i++) {for(int j = 0; j < board.size(); j++) {if(board[i][j] != '.') continue;for(char c = '1'; c <= '9'; c++) {if(isValid(board, i, j, c)) {board[i][j] = c;if(backtracking(board)) return true;board[i][j] = '.';}}return false;}}return true;}bool isValid(vector<vector<char>>& board, int row, int col, char c) {for(int i = 0; i < 9; i++) {if(board[row][i] == c) return false;}for(int i = 0; i < 9; i++) {if(board[i][col] == c) return false;}for(int i = row - (row % 3); i < row - (row % 3) + 3; i++) {for(int j = col - (col % 3); j < col - (col % 3) + 3; j++) {if(board[i][j] == c) return false;}}return true;}void solveSudoku(vector<vector<char>>& board) {backtracking(board);}
};

相关文章:

代码随想录算法训练营第三十天 | 332.重新安排行程 51. N皇后 37. 解数独 总结

打卡第30天&#xff0c;回溯算法第二刷。 今日任务 332.重新安排行程51.N皇后37.解数独总结 332.重新安排行程 给你一份航线列表 tickets &#xff0c;其中 tickets[i] [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。 所有这些机票都属于一个从…...

Windows权限提升—MySQL数据库提权

Windows权限提升—MySQL数据库提权1. 前言2. 数据库提权介绍2.1. 常见数据库端口2.2. MySQL数据库提权条件2.3. MySQL数据库提权类型3. MySQL中UDF提权3.1. UDF提权介绍3.2. UDF提权思路3.3. UDF提权步骤3.3.1. 获取外连数据库3.3.1.1. 外连数据库3.3.1.2. 连接数据库3.3.1.3. …...

使用旧电脑玩Linux

今天给大家讲讲使用旧电脑玩Linux&#xff0c;大家应该都知道旧电脑的硬件一般比较落后&#xff0c;特别是一些非常老的电脑&#xff0c;目前还在使用的是机械硬盘&#xff0c;如是要跑windows可想而知&#xff0c;但是Linux系统对硬件性能的要求可比windows低的多了&#xff0…...

Linux安装EMQX(简洁版)

安装目录 mkdir /opt/emqx && cd /opt/emqx 安装包下载 yum -y install wget && wget https://www.emqx.com/zh/downloads/broker/5.0.20/emqx-5.0.20-el7-amd64.tar.gz 注意&#xff1a;https://www.emqx.com/zh/downloads/broker获取下载链接并替换(后缀&…...

基于STM32 + FPGA 的软体机器人的 CAN总线运动控制器的设计

针对在软体机器人控制时&#xff0c;多电机协同控制过程中难度大、通用性差、协同性差等缺点&#xff0c;设计了基于 A&#xff32;M和 FPGA的软体机器人的控制器局域网络 ( controller area network&#xff0c;CAN) 总线运动控制器&#xff0c;采用 A&#xff32;MCortex-M4 …...

ROC曲线和AUC值

ROC曲线&#xff08;Receiver Operating Characteristic&#xff0c;受试者工作特征&#xff09;评价分类模型的可视化工具&#xff0c;是一条横纵坐标都限制在0-1范围内的曲线横坐标是假正率FPR&#xff0c;错误地判断为正例的概率纵坐标是真正率TPR&#xff0c;正确地判断为正…...

【vue.js】在网页中实现一个金属抛光质感的按钮

文章目录前言效果电脑效果手机效果说明完整代码index.html前言 诶&#xff1f;这有一个按钮(&#xff5e;&#xffe3;▽&#xffe3;)&#xff5e;&#xff0c;这是一个在html中实现的具有金属质感并且能镜面反射的按钮~ 效果 电脑效果 手机效果 说明 主要思路是使用 navig…...

android实现评论区功能

效果 activity_detail.xml <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas.android.com/apk/res/android"xmlns:app"http://schemas.android.com/apk/res-auto"xmlns:tools"http…...

Java每日一练(20230319)

目录 1. 最大矩形 &#x1f31f;&#x1f31f;&#x1f31f; 2. 回文对 &#x1f31f;&#x1f31f;&#x1f31f; 3. 给表达式添加运算符 &#x1f31f;&#x1f31f;&#x1f31f; &#x1f31f; 每日一练刷题专栏 &#x1f31f; Golang每日一练 专栏 Python每日一练…...

Redis缓存双写一致性

目录双写一致性Redis与Mysql双写一致性canal配置流程代码案例双写一致性理解缓存操作细分缓存一致性多种更新策略挂牌报错,凌晨升级先更新数据库,在更新缓存先删除缓存,在更新数据库先更新数据库,在删除缓存延迟双删策略总结双写一致性 Redis与Mysql双写一致性 canal 主要是…...

【2023-Pytorch-检测教程】手把手教你使用YOLOV5做交通标志检测

项目下载地址&#xff1a;YOLOV5交通标志识别检测数据集代码模型教学视频-深度学习文档类资源-CSDN文库 交通标志的目标检测算法在计算机视觉领域一直属于热点研究问题&#xff0c;改进的优化算法不断地被提出。国内外许多学者针对现有的目标检测方法中网络结构、目标定位、损…...

Java中的二叉树

文章目录前言一、树形结构&#xff08;了解&#xff09;1.1 概念1.2 概念&#xff08;重要&#xff09;1.3 树的表示形式&#xff08;了解&#xff09;1.4 树的应用二、二叉树&#xff08;重点&#xff09;2.1 概念2.2 两种特殊的二叉树2.3 二叉树的性质2.5 二叉树的存储2.5 二…...

基于 gma 绘制古代洛阳 5 大都城遗址空间分布地图

了解 gma gma 是什么&#xff1f; gma 是一个基于 Python 的地理、气象数据快速处理和数据分析函数包&#xff08;Geographic and Meteorological Analysis&#xff0c;gma&#xff09;。gma 网站&#xff1a;地理与气象分析库。 gma 的主要功能有哪些&#xff1f; 气候气象&a…...

分析 Spring 的依赖注入模式

一、依赖注入二、Field Injection优点缺点三、Constructor Injection优点1. 容易发现 code smell优点2. 容易厘清依赖关系优点3. 容易写单元测试优点4. Immutable Object缺点&#xff1a;循环依赖四、总结一、依赖注入 依赖注入 &#xff08;Dependency Injection&#xff0c;…...

IntelliJ IDEA创建Servlet

目录 ——————————————————————————————— 一、创建Java项目 1、创建java项目 2、选择java 3、next 4、给项目命名 5、新创建完java项目的目录结构 二、变java为servlet项目 1、变servlet项目 2、选择Web Application 3、更新完成后的目录…...

Spring Boot如何让自己的bean优先加载

背景介绍 在一些需求中&#xff0c;可能存在某些场景&#xff0c;比如先加载自己的bean&#xff0c;然后自己的bean做一些DB操作&#xff0c;初始化配置问题&#xff0c;然后后面的bean基于这个配置文件&#xff0c;继续做其他的业务逻辑。因此有了本文的这个题目。 实现方法…...

LeetCode分类刷题----动态规划

动态规划509.斐波那契数列70.爬楼梯746.使用最小花费怕楼梯62.不同路径63.不同路径||343.整数拆分96.不同的二叉搜索树01背包问题416.分割等和子集1049.最后一块石头的重量||494.目标和474.一和零完全背包问题518.零钱兑换||377.组合总和IV322.零钱兑换279.完全平方数139.单词拆…...

今年好像没有金三银四了?

大家好&#xff0c;我是记得诚。 金三银四&#xff0c;是换工作的高峰期&#xff0c;新的一年结束了&#xff0c;在年前拿完年终奖&#xff0c;在年后3月和4月换个满意的工作。 单从我公司来看&#xff0c;目前还没有一个人离职&#xff0c;往年离职率是要高一些的。 还有我…...

【C++】入门知识之 函数重载

前言提到重载这个词&#xff0c;我们会想到什么呢&#xff1f;重载有一种一词多义的意思&#xff0c;中华文化博大精深&#xff0c;之前有一个笑话&#xff0c;中国的乒乓球谁都打不过&#xff0c;男足谁都打不过&#xff0c;哈哈哈这也是非常有意思的&#xff0c;但是今天我们…...

文心一言发布,你怎么看?chatGPT

百度全新一代知识增强大语言模型“文心一言”于2021年3月16日正式发布&#xff0c;作为一款自然语言处理技术&#xff0c;它引起了广泛的关注和讨论。 首先&#xff0c;文心一言是一款具有重大意义的自然语言处理技术。在人工智能领域&#xff0c;自然语言处理技术一直是一个难…...

Python:操作 Excel 折叠

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...

【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习

禁止商业或二改转载&#xff0c;仅供自学使用&#xff0c;侵权必究&#xff0c;如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...

以光量子为例,详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...

技术栈RabbitMq的介绍和使用

目录 1. 什么是消息队列&#xff1f;2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...

02.运算符

目录 什么是运算符 算术运算符 1.基本四则运算符 2.增量运算符 3.自增/自减运算符 关系运算符 逻辑运算符 &&&#xff1a;逻辑与 ||&#xff1a;逻辑或 &#xff01;&#xff1a;逻辑非 短路求值 位运算符 按位与&&#xff1a; 按位或 | 按位取反~ …...

鸿蒙Navigation路由导航-基本使用介绍

1. Navigation介绍 Navigation组件是路由导航的根视图容器&#xff0c;一般作为Page页面的根容器使用&#xff0c;其内部默认包含了标题栏、内容区和工具栏&#xff0c;其中内容区默认首页显示导航内容&#xff08;Navigation的子组件&#xff09;或非首页显示&#xff08;Nav…...

CMS内容管理系统的设计与实现:多站点模式的实现

在一套内容管理系统中&#xff0c;其实有很多站点&#xff0c;比如企业门户网站&#xff0c;产品手册&#xff0c;知识帮助手册等&#xff0c;因此会需要多个站点&#xff0c;甚至PC、mobile、ipad各有一个站点。 每个站点关联的有站点所在目录及所属的域名。 一、站点表设计…...

Qt Quick Controls模块功能及架构

Qt Quick Controls是Qt Quick的一个附加模块&#xff0c;提供了一套用于构建完整用户界面的UI控件。在Qt 6.0中&#xff0c;这个模块经历了重大重构和改进。 一、主要功能和特点 1. 架构重构 完全重写了底层架构&#xff0c;与Qt Quick更紧密集成 移除了对Qt Widgets的依赖&…...

轻量安全的密码管理工具Vaultwarden

一、Vaultwarden概述 Vaultwarden主要作用是提供一个自托管的密码管理器服务。它是Bitwarden密码管理器的第三方轻量版&#xff0c;由国外开发者在Bitwarden的基础上&#xff0c;采用Rust语言重写而成。 &#xff08;一&#xff09;Vaultwarden镜像的作用及特点 轻量级与高性…...

机器学习复习3--模型评估

误差与过拟合 我们将学习器对样本的实际预测结果与样本的真实值之间的差异称为&#xff1a;误差&#xff08;error&#xff09;。 误差定义&#xff1a; ①在训练集上的误差称为训练误差&#xff08;training error&#xff09;或经验误差&#xff08;empirical error&#x…...