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

代码随想录训练营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的一个形成就可以了。
这道题的几个难点:

  1. 一个行程中,如果航班处理不好容易变成一个圈,成为死循环
  2. 有多种解法,字母序靠前排在前面,让很多同学望而退步,如何该记录映射关系呢 ?
  3. 使用回溯法(也可以说深搜) 的话,那么终止条件是什么呢?
  4. 搜索的过程中,如何遍历一个机场所对应的所有机场。
  5. 咱们的递归可以解决死循环的问题,因为用过的不能再用了。
  6. 所以搜索的过程中就是要不断的删multiset里的元素,那么推荐使用unordered_map<string, map<string, int>> targets。
    在遍历 unordered_map<出发机场, map<到达机场, 航班次数>> targets的过程中,可以使用"航班次数"这个字段的数字做相应的增减,来标记到达机场是否使用过了。
    如果“航班次数”大于零,说明目的地还可以飞,如果“航班次数”等于零说明目的地不能飞了,而不用对集合做删除元素或者增加元素的操作。
  7. 我们回溯遍历的过程中,遇到的机场个数,如果达到了(航班数量+1),那么我们就找到了一个行程,把所有航班串在一起了。
  8. 用递归加回溯来遍历。
    代码:
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

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、重新安排行程 前言 提示&#xff1a;这里可以添加本文要记录的大概内容&#xff1a; 今天是跟着代码随想录刷题的第30天&#xff0c;主要是复习了回溯算法…...

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文件 四、编译与烧录总结参考资料 学习嵌入式实时操作系统&#xff08;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 使用场景&#xff1a;target 属性在 Vite 的 vite.config.ts 或 vite.config.js 文件的 server.proxy 配置中指定&#xff0c;用于设置代理服务器应该将请求转发到的目标地址。这通常是一个后端服务的API接口地址。…...

为什么PPT录制没有声音 电脑ppt录屏没有声音怎么办

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

JDBC学习笔记(三)高级篇

一、JDBC 优化及工具类封装 1.1 现有问题 1.2 JDBC 工具类封装 V1.0 resources/db.properties配置文件&#xff1a; driverClassNamecom.mysql.cj.jdbc.Driver urljdbc:mysql:///atguigu usernameroot password123456 initialSize10 maxActive20 工具类代码&#xff1a; p…...

c++编译器在什么情况下会提供类的默认构造函数等,与析构函数

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

SpringBoot3整合Mybatis-Plus3.5.5出现的问题

主要是由于 mybatis-plus 中 mybatis 的整合包版本不够导致的 排除 mybatis-plus 中自带的 mybatis 整合包&#xff0c;单独引入即可 java.lang.IllegalArgumentException: Invalid value type for attribute factoryBeanObjectType: java.lang.Stringat org.springframework.…...

服务器数据恢复—强制上线raid5阵列离线硬盘导致raid不可用的数据恢复案例

服务器数据恢复环境&#xff1a; 某品牌2850服务器中有一组由6块SCSI硬盘组建的raid5磁盘阵列&#xff0c;linux操作系统ext3文件系统。 服务器故障&#xff1a; 服务器运行过程中突然瘫痪。服务器管理员检查阵列后发现raid5阵列中有两块硬盘离线&#xff0c;将其中一块硬盘进行…...

初入阿里云,上手走一波

初入阿里云&#xff0c;上手走一波 一阶&#xff1a;ECSMysqlDMS安装Mysql初始化MysqlMysql操作DMS管理Mysql 二阶&#xff1a;ECSOSS远程连接ECSOSS控制台其他图片服务 三阶&#xff1a;更多搭配操作 可以说个人在日常使用过程中&#xff0c;操作最多的阿里云产品就是阿里云服…...

[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是一款功能强大的微控制器&#xff0c;常用于物联网&#xff08;IoT&#xff09;应用的开发和原型设计。然而&#xff0c;有时候在上传程序成功后&#xff0c;设备却没有任何反应&#xff0c;十分让人费解。通过各种尝试已解决这…...

使用 OCLint进行静态代码分析:一个完整的配置示例

文章目录 0. 概述1. 安装 oclint2. oclint配置文件3. 脚本详解3.1 禁用的规则列表3.2 需要启用的规则代码风格代码复杂性命名规范性能安全性其他 4. 检测执行1. 使用 CMake 生成 compile_commands.json2. 运行 Oclint 0. 概述 OCLint是一个静态代码分析工具&#xff0c;通过词…...

【Linux】线程的互斥

一、进程线程间的互斥相关的背景概念 临界资源&#xff1a;多线程执行流共享的资源就叫做临界资源临界区&#xff1a;每一个线程内部&#xff0c;访问临界资源的代码&#xff0c;就叫做临界区互斥&#xff1a;任何时刻&#xff0c;互斥保证有且只有一个执行流进入临界区&#…...

electron如何让你窗口总是显示在最前面【mac解决全屏窗口alwaysOnTop参数不起作用】

你创建了一个使用Electron框架的应用程序,并希望它在以下情况下始终保持可见: 在切换工作区(桌面)时可见在其他应用程序之上显示当其他应用程序全屏显示时,它也显示在顶部当Keynote处于演示模式时,它也能显示在顶部 特别是当Keynote处于演示模式时,要实现这一点比较困难…...

XR和Steam VR项目合并问题

最近有一个项目是用Steam VR开发的&#xff0c;里面部分场景是用VRTK框架做的&#xff0c;还有一部分是用SteamVR SDK自带的Player预制直接开发的。 这样本身没有问题&#xff0c;因为最终都是通过SteamVR SDK处理的&#xff0c;VRTK也管理好了SteamVR的逻辑&#xff0c;并且支…...

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步骤

版本&#xff1a;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&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

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

剑指offer20_链表中环的入口节点

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

高危文件识别的常用算法:原理、应用与企业场景

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

网络编程(UDP编程)

思维导图 UDP基础编程&#xff08;单播&#xff09; 1.流程图 服务器&#xff1a;短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

Element Plus 表单(el-form)中关于正整数输入的校验规则

目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入&#xff08;联动&#xff09;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&#xff1a; 我们在使用异步的时候理应是要使用中间件的&#xff0c;但是configureStore 已经自动集成了 redux-thunk&#xff0c;注意action里面要返回函数 import { configureS…...

Docker 本地安装 mysql 数据库

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