当前位置: 首页 > 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确认完成后 即链路层配置完成排查网络层错误 排查终端主…...

接口测试中缓存处理策略

在接口测试中&#xff0c;缓存处理策略是一个关键环节&#xff0c;直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性&#xff0c;避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明&#xff1a; 一、缓存处理的核…...

【Python】 -- 趣味代码 - 小恐龙游戏

文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

如何将联系人从 iPhone 转移到 Android

从 iPhone 换到 Android 手机时&#xff0c;你可能需要保留重要的数据&#xff0c;例如通讯录。好在&#xff0c;将通讯录从 iPhone 转移到 Android 手机非常简单&#xff0c;你可以从本文中学习 6 种可靠的方法&#xff0c;确保随时保持连接&#xff0c;不错过任何信息。 第 1…...

Ascend NPU上适配Step-Audio模型

1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统&#xff0c;支持多语言对话&#xff08;如 中文&#xff0c;英文&#xff0c;日语&#xff09;&#xff0c;语音情感&#xff08;如 开心&#xff0c;悲伤&#xff09;&#x…...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

tree 树组件大数据卡顿问题优化

问题背景 项目中有用到树组件用来做文件目录&#xff0c;但是由于这个树组件的节点越来越多&#xff0c;导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多&#xff0c;导致的浏览器卡顿&#xff0c;这里很明显就需要用到虚拟列表的技术&…...

R语言速释制剂QBD解决方案之三

本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...

GruntJS-前端自动化任务运行器从入门到实战

Grunt 完全指南&#xff1a;从入门到实战 一、Grunt 是什么&#xff1f; Grunt是一个基于 Node.js 的前端自动化任务运行器&#xff0c;主要用于自动化执行项目开发中重复性高的任务&#xff0c;例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...

Go语言多线程问题

打印零与奇偶数&#xff08;leetcode 1116&#xff09; 方法1&#xff1a;使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...