代码随想录第三十天 | 回溯问题P6 | ● 332● 51● 37● 总结

332.重新安排行程 

给你一份航线列表 tickets ,其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。

所有这些机票都属于一个从 JFK(肯尼迪国际机场)出发的先生,所以该行程必须从 JFK 开始。如果存在多种有效的行程,请你按字典排序返回最小的行程组合。

  • 例如,行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小,排序更靠前。

假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。

示例 1:

输入:tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
输出:["JFK","MUC","LHR","SFO","SJC"]

示例 2:

输入:tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
输出:["JFK","ATL","JFK","SFO","ATL","SFO"]
解释:另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"] ,但是它字典排序更大更靠后。

思路

代码 

class Solution {
    public List<String> path = new ArrayList<>();
    public List<String> res;
    public List<String> findItinerary(List<List<String>> tickets) {
        //使用lambda表达式,按照目的地将 航线列表 进行排序,使得其满足字典排序,
        // 这样首次得到的有效行程一定是所有可能的有效行程中最小的
        Collections.sort(tickets,(a, b) -> a.get(1).compareTo(b.get(1)));
        //用于记录某机票是否被用过
        boolean[] used = new boolean[tickets.size()];
        path.add("JFK");
        backtracking((ArrayList<List<String>>) tickets, used);

        return res;
    }

    public boolean backtracking(ArrayList<List<String>> tickets, boolean[] used){
        //此时已完成所有行程
        if(path.size() -1 == tickets.size()){
            res = new ArrayList<>(path);
            return true;
        }

        for(int i = 0; i < tickets.size(); i++){
            //机票未用过且可以使用
            if(!used[i] && tickets.get(i).get(0).equals(path.get(path.size() - 1))){
                used[i] = true;
                path.add(tickets.get(i).get(1));

                if(backtracking(tickets, used)){
                    return true;
                }

                used[i] = false;
                path.remove(path.size() - 1);
            }
        }
        return false;
    }
}

51. N皇后 

37. 解数独 

总结 

代码随想录 (programmercarl.com)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/519633.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

docker从入门到熟悉

一、什么是docker&#xff1f; Docker是一个用于开发&#xff0c;交付和运行应用程序的开放平台。Docker使您能够将应用程序与基础架构分开&#xff0c;从而可以快速交付软件。借助Docker&#xff0c;您可以以与管理应用程序相同的方式来管理基础架构。通过利用Docker的快速交付…

11-1(2)-CSS 背景+CSS 精灵图

个人主页&#xff1a;学习前端的小z 个人专栏&#xff1a;HTML5和CSS3悦读 本专栏旨在分享记录每日学习的前端知识和学习笔记的归纳总结&#xff0c;欢迎大家在评论区交流讨论&#xff01; 文章目录 一、CSS 背景1 背景颜色2 背景色半透明3 背景图片4 背景平铺5 背景图片位置6 …

LCD屏幕mmap显示

目录 前言 一.LCD显示 二.LCD颜色显示 2.1 直接显示 2.2 mmap映射显示 前言 mmap是一种内存映射文件的方法&#xff0c;它允许将文件或其它对象映射到进程的地址空间。 使用mmap映射函数进行映射显示&#xff0c;与屏幕普通直接显示相比有很大的优势 一.LCD显示基础 像素、分辨…

2. 如何让mybatis-plus的逻辑删除注解@TableLogic临时失效

文章目录 如何让mybatis-plus的逻辑删除注解TableLogic临时失效1. 场景复现1.1 controller代码1.2 service层代码1.3 entity代码 2. 问题分析3. 解决方案3.1 说明3.2 核心代码3.3 service方法对应修改为3.4 运行结果 如何让mybatis-plus的逻辑删除注解TableLogic临时失效 1. 场…

数学矩阵GCD和lCM(详解)

矩阵乘法 知阵乘法是《线性代数》中的基础内容&#xff0c;但在考察数学的算法题中也会出现。 本节我们学习基础的矩阵乘法规则。 每个矩阵会有一个行数和一个列数&#xff0c;只有当相乘的两个矩阵的左矩阵的列数等于右矩阵的行数 时&#xff0c;才能相乘&#xff0c;否则不允…

移动Web学习05-移动端适配Less预处理器

7、移动端适配 7.1、什么是适配&#xff1f; 简单理解就是、同一个网页&#xff0c;在不同屏幕分辨率的设备下、显示还是一样的&#xff0c;你可以理解为、网页当中的图片&#xff0c;盒子之间的距离、文字的大小、随着屏幕分辨率的变化而变化 前面我们学习了flex布局的方式…

关系型数据库与非关系型数据库、Redis数据库

相比于其他的内存/缓存数据库&#xff0c;redis可以方便的实现持久化的功能&#xff08;保存至磁盘中&#xff09; 一、关系数据库与非关系型数据库 1.1 关系型数据库 一个结构化的数据库&#xff0c;创建在关系模型基础上一般面向于记录 SQL语句 (标准数据查询语言) 就是一种…

二叉树学习

树 树是n个结点的有限集合&#xff0c;当n0时为空树&#xff0c;在任意一颗非空的树中&#xff0c;有且只有一个特定的称为根的结点&#xff0c;当n>1时&#xff0c;其余结点又可以分为m个不相交的有限集&#xff0c;其中每一个集合又是一棵树&#xff0c;并且称为根的子树…

深度学习方法;乳腺癌分类

乳腺癌的类型很多&#xff0c;但大多数常见的是浸润性导管癌、导管原位癌和浸润性小叶癌。浸润性导管癌(IDC)是最常见的乳腺癌类型。这些都是恶性肿瘤的亚型。大约80%的乳腺癌是浸润性导管癌(IDC)&#xff0c;它起源于乳腺的乳管。 浸润性是指癌症已经“侵袭”或扩散到周围的乳…

c# wpf template itemtemplate+dataGrid

1.概要 2.代码 <Window x:Class"WpfApp2.Window8"xmlns"http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x"http://schemas.microsoft.com/winfx/2006/xaml"xmlns:d"http://schemas.microsoft.com/expression/blend…

《UE5_C++多人TPS完整教程》学习笔记30 ——《P31 摄像机和弹簧臂(Camera And Spring Arm)》

本文为B站系列教学视频 《UE5_C多人TPS完整教程》 —— 《P31 摄像机和弹簧臂&#xff08;Camera And Spring Arm&#xff09;》 的学习笔记&#xff0c;该系列教学视频为 Udemy 课程 《Unreal Engine 5 C Multiplayer Shooter》 的中文字幕翻译版&#xff0c;UP主&#xff08;…

SpringBoot+ECharts+Html 地图案例详解

1. 技术点 SpringBoot、MyBatis、thymeleaf、MySQL、ECharts 等 此案例使用的地图是在ECharts社区中查找的&#xff1a;makeapie echarts社区图表可视化案例 2. 准备条件 在mysql中创建数据库echartsdb&#xff0c;数据库中创建表t_location_count表&#xff0c;表中设置两个…

梯度下降算法(Gradient Descent)

注意&#xff1a;本文引用自专业人工智能社区Venus AI 更多AI知识请参考原站 &#xff08;[www.aideeplearning.cn]&#xff09; 算法引言 梯度下降算法&#xff0c;这个在机器学习中非常常见的算法&#xff0c;可以用下山的例子来形象地解释。想象一下&#xff0c;你在一座…

Type-c转USBA3.0芯片 USBA3.0转Type-c芯片(USB3.1GEN2 多路切换Switch芯片) VL162

VL162具有CC功能的USB Type-C数据开关USB 3.1 Gen2 (10Gbps) VL162 带CC功能的USB Type-C数据开关 支持最高10Gbps 2差分通道&#xff0c;2:1 MUX/DeMUX 兼容10Gbps USB3.1 Gen2 低功耗&#xff0c;6mW在设备模式下有效 高直流共模电压&#xff0c;支持2.0V 28针QFN 3.5 x 4.5m…

[RK3128_LINUX5.1] 关于 RetroArch 使用

问题描述 查看文档 docs\cn\Linux\ApplicationNote\Rockchip_Use_Guide_Linux_RetroArch_CN.pdf&#xff0c;描述为实验 make menuconfig 后勾选选项 Libretro cores and retroarch -> retroarch 但是SDK中并没有这个选项 解决方案&#xff1a; 目前发布的buildroot SDK…

MySQL -- 08_最流行的查询需求分析(日期相关、生日、年份距离等~)

目录 最流行的查询需求分析08演示数据准备的SQL需求演示日期相关的查询函数46、查询各学生的年龄使用 timestampdiff() 函数更精准 47、查询本周过生日的学生简单写法&#xff1a;weekofyear针对不规范日期格式的判断写法&#xff1a; 48、查询下周过生日的学生49、查询本月过生…

STC89C51学习笔记(四)

STC89C51学习笔记&#xff08;四&#xff09; 综述&#xff1a;本文讲述了在STC89C51中数码管、模块化编程、LCD1602的使用。 一、数码管 1.数码管显示原理 位选&#xff1a;对74HC138芯片的输入端的配置&#xff08;P22、P23、P24&#xff09;&#xff0c;来选择实现位选&…

wordpress全站开发指南-面向开发者及深度用户(全中文实操)--创建新主题

前言 你可以在wordpress里面下载使用人家打包好的主题&#xff0c;但可能不是很好用&#xff0c;接下来就自己做一个自己的主题。你需要先找到xampp文件夹–htdocs–wordpress(我给更名为wplocal)–wp-content–themes 进入该文件夹之后你可以看到你之前下载导入的所有主题文件…

深度学习十大算法之深度Q网络(DQN)

一、简介 深度Q网络&#xff08;DQN&#xff09;是一种结合了深度学习和强化学习的算法&#xff0c;它在近年来成为了人工智能领域的一个热点。DQN首次被引入是在2013年&#xff0c;由DeepMind的研究人员开发。它标志着深度学习技术在解决高维度决策问题上的一大突破。 DQN的…

Redis -- 缓存穿透问题解决思路

缓存穿透 &#xff1a;缓存穿透是指客户端请求的数据在缓存中和数据库中都不存在&#xff0c;这样缓存永远不会生效&#xff0c;这些请求都会打到数据库。 常见的解决方案有两种&#xff1a; 缓存空对象 优点&#xff1a;实现简单&#xff0c;维护方便 缺点&#xff1a; 额外…