代码随想录训练营Day30
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档
文章目录
- 前言
- 一、重新安排行程
前言
提示:这里可以添加本文要记录的大概内容:
今天是跟着代码随想录刷题的第30天,主要是复习了回溯算法、重新安排形成、N皇后的内容。
提示:以下是本篇文章正文内容,下面案例可供参考
一、重新安排行程
重新安排行程
思路:就是建立一个双层map,unordered_map<string, map<string, int>> targets,第一个string存出发点,第二个string存飞到的地方,和次数(如果没用就是一次),然后把tickets的东西全部放入这个双层map以后,开始从开头遍历这个map对应的内层,比如说开头是jfk,就开始找哪些是开头jfk开始飞的,找到以后,把jfk飞到的对应地方放到result里,然后result中对应的这个地方当做开头,此时要把次数减1,因为不能重复飞,再去找以这个为开头能飞的,比如说有多个,第一个先看看后续怎么样,如果整个的行程等于航班+1就相当于是结束了,把结果放到result里直接返回就行了,如果找到这个起飞的地方没有能飞的了,就直接返回false,把之前的那步再复原,看看上一个作为起飞点有没有可以飞的其他地方,再去其他地方试试,直到能找到一个有航班+1的一个形成就可以了。
这道题的几个难点:
- 一个行程中,如果航班处理不好容易变成一个圈,成为死循环
- 有多种解法,字母序靠前排在前面,让很多同学望而退步,如何该记录映射关系呢 ?
- 使用回溯法(也可以说深搜) 的话,那么终止条件是什么呢?
- 搜索的过程中,如何遍历一个机场所对应的所有机场。
- 咱们的递归可以解决死循环的问题,因为用过的不能再用了。
- 所以搜索的过程中就是要不断的删multiset里的元素,那么推荐使用unordered_map<string, map<string, int>> targets。
在遍历 unordered_map<出发机场, map<到达机场, 航班次数>> targets的过程中,可以使用"航班次数"这个字段的数字做相应的增减,来标记到达机场是否使用过了。
如果“航班次数”大于零,说明目的地还可以飞,如果“航班次数”等于零说明目的地不能飞了,而不用对集合做删除元素或者增加元素的操作。 - 我们回溯遍历的过程中,遇到的机场个数,如果达到了(航班数量+1),那么我们就找到了一个行程,把所有航班串在一起了。
- 用递归加回溯来遍历。
代码:
class Solution {
private: // 定义一个私有成员变量,用于存储从出发机场到其对应到达机场及其航班次数的映射 // unordered_map<出发机场, map<到达机场, 航班次数>> unordered_map<string, map<string, int>> targets; // 定义一个私有回溯函数,用于寻找从指定起始机场出发,经过所有给定航班的行程 bool backtracking(int ticketNum, vector<string>& result) { // 如果结果列表的大小等于给定的航班数量加1(因为起始机场已经加入),说明找到了一个完整的行程 if (result.size() == ticketNum + 1) { return true; } // 遍历从当前机场出发的所有航班 for (pair<const string, int>& target : targets[result[result.size() - 1]]) { // 如果当前航班的次数大于0(即该航班还没有被完全使用) if (target.second > 0) { // 将当前航班的到达机场加入到结果列表中 result.push_back(target.first); // 将当前航班的次数减1,表示已经使用了该航班 target.second--; // 递归调用backtracking函数,继续寻找下一个航班 if (backtracking(ticketNum, result)) return true; // 如果递归调用返回false,说明当前路径不可行,需要回溯 // 将之前加入的航班到达机场从结果列表中移除 result.pop_back(); // 恢复之前航班的次数 target.second++; } } // 如果所有从当前机场出发的航班都尝试过了,仍然没有找到完整的行程,返回false return false; } public: // 定义一个公共函数,用于找到从"JFK"出发,经过所有给定航班的行程 vector<string> findItinerary(vector<vector<string>>& tickets) { // 清空targets映射,确保没有之前的航班信息 targets.clear(); // 定义一个结果列表,用于存储找到的行程 vector<string> result; // 遍历所有给定的航班信息 for (const vector<string>& vec : tickets) { // 将航班的出发机场和到达机场及其次数记录到targets映射中 targets[vec[0]][vec[1]]++; } // 假设起始机场是"JFK",将其加入到结果列表中 result.push_back("JFK"); // 调用backtracking函数来寻找一个有效的行程 backtracking(tickets.size(), result); // 返回找到的行程 return result; }
};
相关文章:
代码随想录训练营Day30
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、重新安排行程 前言 提示:这里可以添加本文要记录的大概内容: 今天是跟着代码随想录刷题的第30天,主要是复习了回溯算法…...

Swift 序列(Sequence)排序面面俱到 - 从过去到现在(二)
概览 在上篇 Swift 序列(Sequence)排序面面俱到 - 从过去到现在(一)博文中,我们讨论了 Swift 语言中序列和集合元素排序的一些基本知识,我们还给出了以自定义类型中任意属性排序的“康庄大道”。 不过在实际的撸码场景中,我们往往需要的是“多属性”同时参与到排序的考…...

STM32F103C8T6基于HAL库移植uC/OS-III
文章目录 一、建立STM32CubeMX工程二、移植1、 uC/OS-III源码2、移植过程 三、配置相关代码1、bsp.c和bsp.h2、main.c3、修改启动代码4、修改app_cfg.h文件5、修改includes.h文件6、修改lib_cfg.h文件 四、编译与烧录总结参考资料 学习嵌入式实时操作系统(RTOS&…...

微服务学习Day9-分布式事务Seata
文章目录 分布式事务seata引入理论基础CAP定理BASE理论 初识Seata动手实践XA模式AT模式TCC模式SAGA模式 高可用 分布式事务seata 引入 理论基础 CAP定理 BASE理论 初识Seata 动手实践 XA模式 AT模式 TCC模式 Service Slf4j public class AccountTCCServiceImpl implements A…...
vue用vite配置代理解决跨域问题(target、rewrite和changeOrigin的使用场景)
Vite的target、rewrite和changeOrigin的使用场景 1. target 使用场景:target 属性在 Vite 的 vite.config.ts 或 vite.config.js 文件的 server.proxy 配置中指定,用于设置代理服务器应该将请求转发到的目标地址。这通常是一个后端服务的API接口地址。…...

为什么PPT录制没有声音 电脑ppt录屏没有声音怎么办
一、为什么PPT录制没有声音 1.软件问题 我们下载软件的时候可能遇到软件损坏的问题,导致录制没有声音,但其他功能还是可以使用的。我建议使用PPT的隐藏功能,下载插件,在PPT界面的加载项选项卡中就能使用。我推荐一款可以解决录屏…...

JDBC学习笔记(三)高级篇
一、JDBC 优化及工具类封装 1.1 现有问题 1.2 JDBC 工具类封装 V1.0 resources/db.properties配置文件: driverClassNamecom.mysql.cj.jdbc.Driver urljdbc:mysql:///atguigu usernameroot password123456 initialSize10 maxActive20 工具类代码: p…...

c++编译器在什么情况下会提供类的默认构造函数等,与析构函数
我们都知道,在 c 里,编写的简单类,若没有自己编写构造析构函数与 copy 构造函数 与 赋值运算符函数,那么编译器会提供这些函数,并实现简单的语义,比如成员赋值。看 源码时,出现了下图类似的情形…...

SpringBoot3整合Mybatis-Plus3.5.5出现的问题
主要是由于 mybatis-plus 中 mybatis 的整合包版本不够导致的 排除 mybatis-plus 中自带的 mybatis 整合包,单独引入即可 java.lang.IllegalArgumentException: Invalid value type for attribute factoryBeanObjectType: java.lang.Stringat org.springframework.…...

服务器数据恢复—强制上线raid5阵列离线硬盘导致raid不可用的数据恢复案例
服务器数据恢复环境: 某品牌2850服务器中有一组由6块SCSI硬盘组建的raid5磁盘阵列,linux操作系统ext3文件系统。 服务器故障: 服务器运行过程中突然瘫痪。服务器管理员检查阵列后发现raid5阵列中有两块硬盘离线,将其中一块硬盘进行…...

初入阿里云,上手走一波
初入阿里云,上手走一波 一阶:ECSMysqlDMS安装Mysql初始化MysqlMysql操作DMS管理Mysql 二阶:ECSOSS远程连接ECSOSS控制台其他图片服务 三阶:更多搭配操作 可以说个人在日常使用过程中,操作最多的阿里云产品就是阿里云服…...
[C++] 小游戏 斗破苍穹 2.2.1至2.11.5所有版本(中) zty出品
目录 2.8.2 2.9.1 2.10.1 2.10.2 2.10.3 2.10.4 2.10.5 2.8.2 #include<stdio.h> #include<iostream> #include<ctime> #include<bits/stdc.h> #include<time.h> //suiji #include<windows.h> //SLEEP函数 using namespace std; st…...

Javaweb---HTTPS
题记 为了保护数据的隐私性我们引入了HTTPS 加密的方式都有那些呢? 1.对称加密: 加密和解密使用的密钥是同一个密钥 2.非对称加密:有两个密钥(一对),分为公钥和私钥(公钥是公开的,私钥是要藏好的) HTTPS的工作过程(旨在对body和header进行加密) 1.对称加密 上述引出的…...
[已解决]ESP32-C3上传程序成功但没有反应的问题
ESP32-C3上传程序成功但没有反应的问题 ESP32-C3是一款功能强大的微控制器,常用于物联网(IoT)应用的开发和原型设计。然而,有时候在上传程序成功后,设备却没有任何反应,十分让人费解。通过各种尝试已解决这…...
使用 OCLint进行静态代码分析:一个完整的配置示例
文章目录 0. 概述1. 安装 oclint2. oclint配置文件3. 脚本详解3.1 禁用的规则列表3.2 需要启用的规则代码风格代码复杂性命名规范性能安全性其他 4. 检测执行1. 使用 CMake 生成 compile_commands.json2. 运行 Oclint 0. 概述 OCLint是一个静态代码分析工具,通过词…...

【Linux】线程的互斥
一、进程线程间的互斥相关的背景概念 临界资源:多线程执行流共享的资源就叫做临界资源临界区:每一个线程内部,访问临界资源的代码,就叫做临界区互斥:任何时刻,互斥保证有且只有一个执行流进入临界区&#…...
electron如何让你窗口总是显示在最前面【mac解决全屏窗口alwaysOnTop参数不起作用】
你创建了一个使用Electron框架的应用程序,并希望它在以下情况下始终保持可见: 在切换工作区(桌面)时可见在其他应用程序之上显示当其他应用程序全屏显示时,它也显示在顶部当Keynote处于演示模式时,它也能显示在顶部 特别是当Keynote处于演示模式时,要实现这一点比较困难…...

XR和Steam VR项目合并问题
最近有一个项目是用Steam VR开发的,里面部分场景是用VRTK框架做的,还有一部分是用SteamVR SDK自带的Player预制直接开发的。 这样本身没有问题,因为最终都是通过SteamVR SDK处理的,VRTK也管理好了SteamVR的逻辑,并且支…...
uni-app:利用Vue的原型对象Vue.prototype设置全局方法及其引用
一、在main.js中设置方法checkPermission绑定到Vue.prototype 核心代码 Vue.prototype.$checkPermission function(username) {console.log(Checking permission for:, username); }; 完整代码 import App from ./App// 添加 checkPermission 方法到 Vue.prototype 上,检查…...
django接入djangorestframework-simplejwt步骤
版本:django 4.2 python: 3.8 安装 pip install djangorestframework-simplejwtuser子应用models.py文件 from django.db import models from django.contrib.auth.models import AbstractUserclass User(AbstractUser):mobile models.CharField(max_length11, u…...
模型参数、模型存储精度、参数与显存
模型参数量衡量单位 M:百万(Million) B:十亿(Billion) 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的,但是一个参数所表示多少字节不一定,需要看这个参数以什么…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂
蛋白质结合剂(如抗体、抑制肽)在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上,高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术,但这类方法普遍面临资源消耗巨大、研发周期冗长…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者
抖音增长新引擎:品融电商,一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中,品牌如何破浪前行?自建团队成本高、效果难控;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

剑指offer20_链表中环的入口节点
链表中环的入口节点 给定一个链表,若其中包含环,则输出环的入口节点。 若其中不包含环,则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

高危文件识别的常用算法:原理、应用与企业场景
高危文件识别的常用算法:原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件,如包含恶意代码、敏感数据或欺诈内容的文档,在企业协同办公环境中(如Teams、Google Workspace)尤为重要。结合大模型技术&…...

网络编程(UDP编程)
思维导图 UDP基础编程(单播) 1.流程图 服务器:短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...
Swagger和OpenApi的前世今生
Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章,二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑: 🔄 一、起源与初创期:Swagger的诞生(2010-2014) 核心…...
Element Plus 表单(el-form)中关于正整数输入的校验规则
目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入(联动)2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...
React---day11
14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store: 我们在使用异步的时候理应是要使用中间件的,但是configureStore 已经自动集成了 redux-thunk,注意action里面要返回函数 import { configureS…...

Docker 本地安装 mysql 数据库
Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker ;并安装。 基础操作不再赘述。 打开 macOS 终端,开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...