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

回溯——11.重新安排行程

力扣题目链接

给定一个机票的字符串二维数组 [from, to],子数组中的两个成员分别表示飞机出发和降落的机场地点,对该行程进行重新规划排序。所有这些机票都属于一个从 JFK(肯尼迪国际机场)出发的先生,所以该行程必须从 JFK 开始。

提示:

  • 如果存在多种有效的行程,请你按字符自然排序返回最小的行程组合。例如,行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小,排序更靠前
  • 所有的机场都用三个大写字母表示(机场代码)。
  • 假定所有机票至少存在一种合理的行程。
  • 所有的机票必须都用一次 且 只能用一次。

解题思路

  1. 图的建模:把航班信息建模为图,其中城市为节点,航班为边。构建邻接表来表示图。

  2. 排序:对目的地进行字母排序,确保在深度优先搜索中总是优先访问字母顺序靠前的目的地。

  3. DFS遍历:使用深度优先搜索遍历图,从起始城市出发,一直走到所有可能的目的地,记录经过的城市。

  4. 路径重建:由于深度优先搜索会使得路径顺序反向,需要在结果列表中反转顺序以获得正确的行程。

这个方法有效地使用了排序和深度优先搜索来解决旅行路径问题,保证了按照字母顺序访问目的地并生成正确的行程路径。

完整代码如下:

class Solution:def findItinerary(self, tickets: List[List[str]]) -> List[str]:self.adj = {}# sort by the destination alphabetically# 根据航班每一站的重点字母顺序排序tickets.sort(key=lambda x:x[1])# get all possible connection for each destination# 罗列每一站的下一个可选项for u,v in tickets:if u in self.adj: self.adj[u].append(v)else: self.adj[u] = [v]# 从JFK出发self.result = []self.dfs("JFK")  # start with JFKreturn self.result[::-1]  # reverse to get the resultdef dfs(self, s):# if depart city has flight and the flight can go to another citywhile s in self.adj and len(self.adj[s]) > 0:# 找到s能到哪里,选能到的第一个机场v = self.adj[s][0]  # we go to the 1 choice of the city# 在之后的可选项机场中去掉这个机场self.adj[s].pop(0)  # get rid of this choice since we used it# 从当前的新出发点开始self.dfs(v)  # we start from the new airportself.result.append(s)  # after append, it will back track to last node, thus the result list is in reversed order
self.adj = {}

self.adj 用于存储每个城市的邻接表。邻接表是一个字典,键是出发城市,值是一个列表,表示从该城市出发可以到达的目的城市。

tickets.sort(key=lambda x: x[1])

tickets 列表按照每个航班的目的地(x[1])进行排序。这样做是为了在后续的处理过程中能优先选择字母顺序靠前的目的地。

for u, v in tickets:if u in self.adj:self.adj[u].append(v)else:self.adj[u] = [v]
  • 遍历排序后的航班列表,为每个出发城市 u 创建一个目的地列表。若 u 已经在 self.adj 字典中,则将 v 加入到对应的列表中;否则创建一个新的列表。

self.result = []
self.dfs("JFK")

初始化 self.result 列表,用于存储最终的行程路径。调用 dfs 方法从起始城市 "JFK" 开始进行深度优先搜索。

def dfs(self, s):while s in self.adj and len(self.adj[s]) > 0:v = self.adj[s][0]self.adj[s].pop(0)self.dfs(v)self.result.append(s)

dfs 方法中,首先检查当前城市 s 是否有可用的航班(即 s 是否在 self.adj 中且有目的地)。如果有,取出列表中的第一个目的地 v(因为航班列表已按字母排序过,选择第一个保证了字母顺序),并从列表中删除这个目的地。然后递归调用 dfs 方法继续从 v 出发。递归完成后,将当前城市 s 添加到 self.result 中。注意,self.result 中的城市顺序是逆序的,因为每次递归都会先处理后续的城市,最后返回到当前城市。

return self.result[::-1]

最后,返回 self.result 的反转列表,即按照正确的旅行顺序输出最终的行程路径。

相关文章:

回溯——11.重新安排行程

力扣题目链接 给定一个机票的字符串二维数组 [from, to],子数组中的两个成员分别表示飞机出发和降落的机场地点,对该行程进行重新规划排序。所有这些机票都属于一个从 JFK(肯尼迪国际机场)出发的先生,所以该行程必须从…...

python+pytest+request 接口自动化测试

一、环境配置 1.安装python3 brew update brew install pyenv 然后在 .bash_profile 文件中添加 eval “$(pyenv init -)” pyenv install 3.5.3 -v pyenv rehash 安装完成后,更新数据库 pyenv versions 查看目前系统已安装的 Python 版本 pyenv global 3.5…...

《JavaEE进阶》----10.<SpringMVC应用分层:【三层架构】>

本篇博客我们主要讲解 1.应用的分层:三层架构 2.Spring MVC和三层架构的区别和联系 3.软件设计原则:高内聚低耦合 4.应用分层的好处 5.通过应用分层后的代码示例 一、三层架构简介 阿里开发手册中,关于工程结构部分,定义了常见工程的应用分层结构: 上图…...

【网络】网络通信的传输方式

目录 1.网络通信中的两种基本通信模式 1.1.怎么理解连接 1.2.面向有连接类型 1.3.面向无连接类型 2.实现这两种通信模式的具体交换技术 2.1.电路交换 2.2.分组交换 3.根据接收端数量分类 单播(Unicast) 广播(Broadcast) …...

数据仓库理论知识

1、数据仓库的概念 数据仓库(英文:Date Warehouse,简称数仓、DW),是一个用于数据存储、分析、报告的数据系统。数据仓库的建设目的是面向分析的集成化数据环境,其数据来源于不同的外部系统&#…...

容易中、见刊快的6本医学期刊推荐!

常笑医学整理了6本容易中、见刊快的医学期刊,以及期刊详细参数与投稿经验,供医生、医学生们在论文投稿时参考。投稿经历均来自常笑医学网用户真实分享,欢迎大家到常笑医学网分享自己的投稿经历和实用经验。 1.《中国医药科学》 (详…...

nnunetv2系列:使用默认的预测类推理2D数据

nnunetv2系列:使用默认的预测类推理2D数据 这里参考源代码nnUNet/nnunetv2/inference/predict_from_raw_data.py中给的示例进行调整和测试。 代码示例 from torch import device from nnunetv2.inference.predict_from_raw_data import nnUNetPredictor# from nn…...

伺服电机如何计算扭矩——看这一篇就够了

#零基础学工控##西门子PLC##V90##电机##工控分享##自动化#工控人加入PLC工业自动化精英社群 工控人加入PLC工业自动化精英社群...

数据库C语言删除修改和输出

#include<myhead.h> #include<sqlite3.h> int out_callback(void *arg,int column_num, char **msgrow,char **msgcolumn)//输出查找的工人信息 { int i 0, j 0; while(i<column_num) { printf("%s\t" ,*(msgcolumni)); …...

插槽slot

一、简介&#xff1a; 插槽是 Vue 组件化开发中非常强大且灵活的工具&#xff0c;它使得组件的复用性和可定制性大大提高。通过合理地使用不同类型的插槽&#xff0c;可以构建出更加灵活和可维护的 Vue 应用程序。 二、使用场景 可重用组件的定制化 比如一个通用的弹窗组件&am…...

交换技术是一种在计算机网络和通信系统中广泛应用的关键技术,它主要通过交换设备(如交换机、路由器等)实现数据的转发和传输

交换技术是一种在计算机网络和通信系统中广泛应用的关键技术&#xff0c;它主要通过交换设备&#xff08;如交换机、路由器等&#xff09;实现数据的转发和传输。交换技术的核心目的是在不同的设备之间高效地传输数据&#xff0c;实现信息的互联互通。 一、交换技术的定义 交换…...

数仓建模:数仓设计中的10个陷阱

目录 0 引言 1 主要内容 1.1 过于迷恋技术&#xff0c;而没有将重点放在业务需求和目标上 1.2 没有或无法找到一个有影响的、平易近人的、明白事理的高级管理人员作为数仓建设的发起人 1.3 将项目处理为一个巨大的持续多年的项目&#xff0c;而不是追求更容易管理的、虽然…...

Vue如何将网页转换成图片或PDF并上传

一.使用html2canvas获取页面元素并绘制成图片 htmlcanvas中文文档 npm install --save html2canvas<template><div><button click"uploadImg">上传</button><div ref"yourDom"><!-- ...图片中页面内容 --><img s…...

【引领数据分析革命】TaskWeaver框架全景解读与入门指南!

亲爱的技术爱好者们&#xff0c;我是你们的老朋友—— 一个热爱.NET和AI相关技术的博主&#xff0c;在今天这个信息与数据爆炸的时代&#xff0c;我们始终寻求着处理数据分析任务的更优雅、更高效的方式。Microsoft团队推出了一个叫做TaskWeaver的神器&#xff0c;这可不仅仅是…...

LabVIEW灵活集成与调试的方法

在LabVIEW开发中&#xff0c;为了构建一个既便于调试又能灵活集成到主VI中的控制VI&#xff0c;开发者需要采用适当的编程方式和架构。常见的选择包括模块化设计、状态机架构以及事件驱动编程。这些方法有助于简化调试过程、提高系统的稳定性&#xff0c;并确保代码的重用性和可…...

网络药理学:分子对接之二:PDB数据库的使用(已知PDB ID)、PubChem数据库如果没有3D结构

PDB数据库使用 官方地址&#xff1a;https://www.rcsb.org/ 首页如下&#xff1a; 我们以热休克蛋白HSP90AA1为例&#xff0c;其PDB ID为7DHG&#xff0c;所以我们在搜索栏输入7DHG&#xff1a; 主要关注红框里的几个地方。 Download 下载文件&#xff0c;一般选择PDB For…...

JS获取页面中video标签视频的封面和时长

从HTML中提取Video信息 /*** 从html字符串中提取video标签* 入参&#xff1a; {String} htmlString* 出参&#xff1a;{Array} 数组*/ function extractVideosFromHTML(htmlString) {const dom new DOMParser().parseFromString(htmlString, text/html);const videos Arr…...

LLM大模型学习:AI Agent综述

AI Agent是什么 将LLM思想链接到一起&#xff0c;自主实现用户设定的任何目标。只需要告诉AutoGPT一个目标&#xff0c;能自主生成执行计划。 吴恩达&#xff1a;“与其争论哪些工作才算是真正的 Agent&#xff0c;不如承认系统可以具有不同程度的 Agentic 特性。” 核心在于…...

极米科技:走出舒适圈,推动数据架构现代化升级 | OceanBase 《DB大咖说》

《DB 大咖说》第 13 期&#xff0c;邀请到了极米科技软件与创新产品线高级架构师施刘凡来进行分享。 在小红书平台上&#xff0c;“是否应将家里的电视升级为投影仪&#xff1f;”这一话题激发了上百万篇笔记的分享与推荐&#xff0c;反映出年轻群体对投影仪的偏好。随着手机、…...

IP学习——Fiveday

设备排错 [R1]display ip interface brief 查看路由器接口的IP地址信息 [R1]display current-configuration int g0/0/1.10 查看路由器接口的IP地址信息 TG---> trunk查看vlan指令:displayvan其中UT--->accessc.vlan确认完成后 即链路层配置完成排查网络层错误 排查终端主…...

Cursor实现用excel数据填充word模版的方法

cursor主页&#xff1a;https://www.cursor.com/ 任务目标&#xff1a;把excel格式的数据里的单元格&#xff0c;按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例&#xff0c;…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

AspectJ 在 Android 中的完整使用指南

一、环境配置&#xff08;Gradle 7.0 适配&#xff09; 1. 项目级 build.gradle // 注意&#xff1a;沪江插件已停更&#xff0c;推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...

九天毕昇深度学习平台 | 如何安装库?

pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子&#xff1a; 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...

Razor编程中@Html的方法使用大全

文章目录 1. 基础HTML辅助方法1.1 Html.ActionLink()1.2 Html.RouteLink()1.3 Html.Display() / Html.DisplayFor()1.4 Html.Editor() / Html.EditorFor()1.5 Html.Label() / Html.LabelFor()1.6 Html.TextBox() / Html.TextBoxFor() 2. 表单相关辅助方法2.1 Html.BeginForm() …...