算法力扣刷题记录 八十九【332.重新安排行程】

2024-08-23 14:28
文章标签 算法 力扣 记录 刷题 八十九 行程 重新安排 332

本文主要是介绍算法力扣刷题记录 八十九【332.重新安排行程】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言

回溯章节第13篇。

记录 八十九【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"] ，但是它字典排序更大更靠后。

提示：

1 <= tickets.length <= 300
tickets[i].length == 2
fromi.length == 3
toi.length == 3
from i 和 to i 由大写英文字母组成
from i != to i

二、尝试实现

2.1分析题目，确定方法

  1. 理解题目：
  • 给的参数是tickets 数组，其中每一个元素代表一张机票，该机票表现形式是[fromi, toi] ，表示出发地和终点；如下图：
    在这里插入图片描述
  • 题目要求把tickets都串联起来，从JFK的机票开始，形成一条航线。比如示例一：
    在这里插入图片描述
  1. 理解题目含义之后：
  • 明显看出来这不是贪心或者动态规划类的题目。没有办法从前一个状态推到下一个状态。
  • tickets集合可以将节点构成一个有向图，使用图论中的搜索方式，找到一条路径如何？应该可以。但是第一步需要先把tickets变成图的表示方法：邻接表。
  • 根据记录 八十二【图论理论基础及深度优先搜索算法】和记录 八十五【图论的广度优先搜索理论基础】，广度优先搜索应用在两点之间最短路径查找多，本题目应该选用深度优先搜索，因为是找一条路径，当找不通时，回溯更改方向继续搜索。如果搜到路径（并且排序最小），应该返回。
  • 那么：本题方法——深搜+回溯。
  • 用到回溯算法：参考为回溯新开了一个章节。那么相当于从tickets集合中顺序选择机票，串联起来，找一个排列。（另一个角度，所以不需要把tickets转换成邻接表）

2.2 回溯思路【排列角度】

  1. 题目只返回一条行程，按字典排序最小的行程。那么，先把tickets进行从小到大排序。第一个问题：如何解决排序？

  • 现有的sort函数没有办法对tickets[i]：vector< string> 形式排序，所以要自己实现比较函数。如下：

    1. static修饰：如果调用类的非静态成员函数要创建对象。为了力扣的核心代码形式，所以加static。
2. 先比较from出发地。如果from一样，比较end终点。从小到大排列。
static bool compare(const vector<string>& ticket_a,const vector<string>& ticket_b){if(ticket_a[0] == ticket_b[0]){return ticket_a[1] < ticket_b[1];}else{return ticket_a[0] < ticket_b[0];}}

  • 排序之后，找到的第一条路径肯定是字典排序后最小的。 只搜集第一个叶子结点。

  1. 递归搜索：回溯的过程。
  • 确定递归的返回值：用一个成员vector< string> temp;记录结果。
  • 确定递归的参数：
    • vector< bool>& used：表明这个tickets[i]有没有被使用过。题目说所有的tickets[i]都要被使用且使用1次，所以used作用在此；
    • string from ：代表下一个机票的出发地 。上一个ticket的降落地 = 下一个ticket的出发地；
    • int& usenum：代表使用过的tickets总数。控制终止条件。usenum == tickets.size()时终止；
    • const vector<vector< string>>& tickets ：输入的tickets数组。
  • 确定递归的终止条件：
    • 如果从temp.size来判断终止不太方便，所以用一个变量usenum表示现在使用了多少个ticket，如果usenum == tickets.size()代表使用了所有的tickets，那么应该return。
  • 确定递归的逻辑：
    • 在主函数中先sort tickets数组，结果相当于求一个排列，所以每次for循环从0开始到tickets.size()。
    • 重复使用处理：if(used[i]) continue;如果标记该tickets[i]使用过，那么continue；
    • 地点不连续处理：if(tickets[i][0] != from) continue;如果出发地不是上一层传递的from，那么continue；
    • 找到的第一个没使用过且from出发地符合的tickets[i]一定是最小路径的一员。（提醒排过序了）
    • tickets处理：把该tickets[i]的目的地放入temp；used = true；usenum++；
    • 递到下一层：from赋值上一步的tickets[i]的目的地（toi）;
    • 回溯：把temp放入的目的地pop；used = false；usenum - -；
  • 细节处理：本题只返回一条排序最小的路径，所以只搜集一个叶子结点。
    • 设置一个全局的标志：bool ok = false；
    • 在终止条件中，ok = true；
    • 在for循环中，回溯之前先判断if(ok) ，那么break;
  1. 该回溯实现的树形结构，以示例一为例：
    在这里插入图片描述
    在这里插入图片描述

2.3 代码实现【回溯算法+排列角度】

class Solution {
public:vector<string> temp;//中间结果bool ok= false;static bool compare(const vector<string>& ticket_a,const vector<string>& ticket_b){if(ticket_a[0] == ticket_b[0]){return ticket_a[1] < ticket_b[1];}else{return ticket_a[0] < ticket_b[0];}}void backtracking(vector<bool>& used,string from,int& usenum,const vector<vector<string>>& tickets){//终止条件，是否所有机票都被使用过if(usenum == tickets.size()){ok = true;return;}for(int i = 0;i < tickets.size();i++){if(tickets[i][0] != from) continue;if(used[i]) continue;temp.push_back(tickets[i][1]);//把目的地放入used[i] = true;//该机票使用过usenum++;backtracking(used,tickets[i][1],usenum,tickets);//递到下一层if(ok) break;//只返回最小的行程，所以另一终止条件.只搜集一个叶子节点。temp.pop_back();used[i] = false;usenum--;}}vector<string> findItinerary(vector<vector<string>>& tickets) {sort(tickets.begin(),tickets.end(),compare);//把所有机票从小到大排列temp.clear();temp.push_back("JFK");vector<bool> used(tickets.size(),false);int usenum = 0;backtracking(used,"JFK",usenum,tickets);return temp;}
};

问题：提交后超时，无法通过；

  • 分析时间复杂度：
    • 首先sort，排序方式快排，时间复杂度O(nlogn)；
    • 在进入递归：递归次数最差情况需要找到排列树形结构中的最后一个叶子节点。所以时间复杂度是O(n!)；
    • 那么整体的时间复杂度：O(n* n! * logn)；

三、参考学习

【332.重新安排行程】参考学习链接

如何解决超时的问题？

3.1 学习思路

  1. 深搜离不开回溯。这道题就是深度优先搜索，深搜中必须用到回溯。
  2. 问题一：如何避开死循环？以参考给的示例：如果处理不好会在“JFK”和“NRT”之间来回跳跃。
  • 尝试实现没有出现这个问题：使用used数组记录是否使用过，且使用1次，并不会出现这种情况。进入死循环，是因为把某个机票重复使用多次，或者有重复的机票。
    在这里插入图片描述
  1. 问题二：处理映射关系。一个出发地可能对应有多个目的地。
    解决：在unordered_map中使得出发机场没有重复的，且无需排序，底层实现是哈希表；map不允许重复，有序，底层实现是红黑树（二叉搜索树）；

unordered_map<string, map<string, int>> targets：unordered_map<出发机场, map<到达机场, 航班次数>> targets
航班次数用来解决：tickets中有重复的机票。如果“航班次数”大于零，说明目的地还可以到达，如果“航班次数”等于零说明目的地无法到达。
map<到达机场, 航班次数>完成2.3代码中的排序操作。

  1. 递归回溯实现：
    • 递归的参数：
      • unordered_map<string, map<string, int>> targets：在函数之前先解决映射关系；
      • vector < string>& result：存放路径结果；相当于2.3代码的temp；
      • int ticketNum。终止条件使用，表示航班总数（终止条件会用上）= tickets数组的总数。
    • 递归的返回值：bool
      • 2.2中的细节处理：只搜集一个叶子节点，个人用bool ok做了标记；在for循环中，回溯之前先判断if(ok) break;
      • 参考使用：返回值bool。
    • 递归终止条件：if (result.size() == ticketNum + 1) { return true; }
    • 递归函数的逻辑：
      • 遍历result[result.size()-1]（相当于2.3代码中的from参数的作用）所映射的map；
      • 先判断**“航班次数”** 是否大于0，还有无机会到达该目的地；
      • 处理航班：如果可以，把**“到达机场”** 放入result中，再“航班次数”++；
      • 递到下一层，根据下一层的返回值，是否直接return true；相当于2.3代码中的if(ok) break;
      • 回溯操作：把**“到达机场”** 从result中pop，再“航班次数”- -；

3.2 代码实现【回溯+航班映射】

class Solution {
public:unordered_map<string,map<string,int>> targets;bool backtracking(int ticketSum,vector<string>& result){if(result.size() == ticketSum+1){return true;}for(pair<const string,int>& target:targets[result[result.size()-1]]){if(target.second > 0){result.push_back(target.first);target.second--;if(backtracking(ticketSum,result)) return true;result.pop_back();target.second++;}}return false;}vector<string> findItinerary(vector<vector<string>>& tickets) {targets.clear();for(int i = 0;i < tickets.size();i++){targets[tickets[i][0]][tickets[i][1]]++;}vector<string> result;result.push_back("JFK");backtracking(tickets.size(),result);return result;}
};

注意点：

  1. 主函数中result要先放入起点“JFK”；

  2. 在使用rangefor遍历from出发地映射的map时，target必须是引用，因为target.second做了修改，需要传递到下一层；

  3. pair<const string,int>类型必须加const，因为target必须是引用，就必须在 string 前面加上 const，因为map中的key 是不可修改的。或者直接auto让编译器自动识别类型。

    for(auto& target:targets[result[result.size()-1]])

3.3 分析时间复杂度

对比2.3和3.2 两个代码实现：深搜和回溯的思路一致，但是容器的使用和处理上不一样导致一个出现超时的用例，一个没有超时风险。

  1. 完成映射的时间复杂度是O(n)；
  2. 进入到递归中。使用unordered_map找到from映射的map，底层是哈希表，查找O(1)常数级；再考虑递归次数：从排列角度看结果是获得一个排列，搜索顶多O(n!)；
  3. 那么3.2的时间复杂度是O(n * n!)；
  4. 因为使用映射容器，使得在查找from出发地时，用unordered_map减少了时间；递归中的for循环时间减少，并且排序时间也减少，两个地方使得3.2的代码实现比2.3更好。

总结

在这里插入图片描述
（欢迎指正，转载标明出处）

这篇关于算法力扣刷题记录 八十九【332.重新安排行程】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1099641。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...
秋招最新大模型算法面试，熬夜都要肝完它

秋招最新大模型算法面试，熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候，不知道面试完会不会复盘、总结，做笔记的习惯，这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助，都附有完整答案，熬夜也要看完，祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN，还有完整版的大模型 AI 学习资料，朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费
阅读更多...
dp算法练习题【8】

dp算法练习题【8】

不同二叉搜索树 96. 不同的二叉搜索树 给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。 示例 1： 输入：n = 3输出：5 示例 2： 输入：n = 1输出：1 class Solution {public int numTrees(int n) {int[] dp = new int
阅读更多...
Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数，每次操作将其分成2^q份，对于每一份内部的数进行翻转(逆序)，每次操作完后输出操作后新序列的逆序对数。 图一：  划分子问题。 图二： 分而治之，=>  合并 。 图三： 回溯：
阅读更多...
Node.js学习记录（二）

Node.js学习记录（二）

目录 一、express 1、初识express 2、安装express 3、创建并启动web服务器 4、监听 GET&POST 请求、响应内容给客户端 5、获取URL中携带的查询参数 6、获取URL中动态参数 7、静态资源托管 二、工具nodemon 三、express路由 1、express中路由 2、路由的匹配 3、路由模块化 4、路由模块添加前缀 四、中间件
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2