当前位置: 首页 > 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…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

如何为服务器生成TLS证书

TLS&#xff08;Transport Layer Security&#xff09;证书是确保网络通信安全的重要手段&#xff0c;它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书&#xff0c;可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

如何在网页里填写 PDF 表格?

有时候&#xff0c;你可能希望用户能在你的网站上填写 PDF 表单。然而&#xff0c;这件事并不简单&#xff0c;因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件&#xff0c;但原生并不支持编辑或填写它们。更糟的是&#xff0c;如果你想收集表单数据&#xff…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

基于PHP的连锁酒店管理系统

有需要请加文章底部Q哦 可远程调试 基于PHP的连锁酒店管理系统 一 介绍 连锁酒店管理系统基于原生PHP开发&#xff0c;数据库mysql&#xff0c;前端bootstrap。系统角色分为用户和管理员。 技术栈 phpmysqlbootstrapphpstudyvscode 二 功能 用户 1 注册/登录/注销 2 个人中…...

uniapp 集成腾讯云 IM 富媒体消息(地理位置/文件)

UniApp 集成腾讯云 IM 富媒体消息全攻略&#xff08;地理位置/文件&#xff09; 一、功能实现原理 腾讯云 IM 通过 消息扩展机制 支持富媒体类型&#xff0c;核心实现方式&#xff1a; 标准消息类型&#xff1a;直接使用 SDK 内置类型&#xff08;文件、图片等&#xff09;自…...

全面解析数据库:从基础概念到前沿应用​

在数字化时代&#xff0c;数据已成为企业和社会发展的核心资产&#xff0c;而数据库作为存储、管理和处理数据的关键工具&#xff0c;在各个领域发挥着举足轻重的作用。从电商平台的商品信息管理&#xff0c;到社交网络的用户数据存储&#xff0c;再到金融行业的交易记录处理&a…...

算法—栈系列

一&#xff1a;删除字符串中的所有相邻重复项 class Solution { public:string removeDuplicates(string s) {stack<char> st;for(int i 0; i < s.size(); i){char target s[i];if(!st.empty() && target st.top())st.pop();elsest.push(s[i]);}string ret…...

VSCode 使用CMake 构建 Qt 5 窗口程序

首先,目录结构如下图: 运行效果: cmake -B build cmake --build build 运行: windeployqt.exe F:\testQt5\build\Debug\app.exe main.cpp #include "mainwindow.h"#include <QAppli...