首页 > 其他分享 >332. 重新安排行程

332. 重新安排行程

时间:2023-04-15 19:46:37浏览次数:32  
标签:tickets used return res 行程 332 重新安排 vector path

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

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

例如,行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小,排序更靠前。
假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。

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

> 我的解法
用常规的回溯,当测试用例一多,就不能通过,所以标准解法用map的关键字有序性来进行回溯。

class cmp{
public:
    bool operator()(const vector<string> &lhs,const vector<string> &rhs){
        for (int i = 0; i < lhs.size(); i++) {
            if (lhs[i] == rhs[i]) continue;
            else return lhs[i] < rhs[i];
        }
        return false;
    }
};

class Solution {
private:
    bool use_tickets(vector<bool> &used) {
        for (const auto& p : used) {
            if (p == false) return false;
        }
        return true;
    }
    void traversal(vector<vector<string>>& tickets, vector<bool> &used) {
        if (use_tickets(used)) {
            res.emplace_back(path);
            return;
        }
        for (int i = 0; i < tickets.size(); i++) {
            if(used[i]) continue;
            else if (path.empty() && tickets[i][0] == "JFK" && used[i] == false) {
                path.emplace_back(tickets[i][0]);
                path.emplace_back(tickets[i][1]);
                used[i] = true;
                traversal(tickets, used);
                used[i] = false;
                path.pop_back();
                path.pop_back();
            }
            else if (!path.empty() && path.back() == tickets[i][0] && used[i] == false) {
                path.emplace_back(tickets[i][1]);
                used[i] = true;
                traversal(tickets, used);
                used[i] = false;
                path.pop_back();
            }
            else continue;
        }
    }
    vector<string> tickets_sort(vector<vector<string>>& res) {
        if (res.empty()) return { "" };
        std::priority_queue<vector<string>,vector<vector<string>>,cmp> que;
        for(const auto &ele:res){
            if(que.empty())
            {
                que.push(ele);
            }
            else{
                que.push(ele);
                que.pop();
            }
        }
        return que.top();
        // std::sort(res.begin(), res.end(),
        //     [](const vector<string>& lhs, const vector<string>& rhs)->bool {
        //         for (int i = 0; i < lhs.size(); i++) {
        //             if (lhs[i] == rhs[i]) continue;
        //             else return lhs[i] < rhs[i];
        //         }
        //         return false;
        //     });
        // return res[0];
    }
public:
    vector<vector<string>> res;
    vector<string> path;
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        if (tickets.size() == 1) return tickets[0];
        res.clear();
        path.clear();
        vector<bool> used(tickets.size(),false);
        traversal(tickets, used);
        return tickets_sort(res);
    }
};

> 标准解法

class Solution {
private:
    bool traversal(string ticket,int ticknum){
        if(res.size() == ticknum + 1) return true;
        bool find = false;
        for(auto &ele: mp[ticket]){
            if(ele.second > 0){
                string arrive = ele.first;
                res.emplace_back(arrive);
                ele.second--;
                find = traversal(arrive,ticknum);
                if(find) return true;
                ele.second++;
                res.pop_back();
            }
        }
        return false;
    }
public:
    map<string,map<string,int>> mp;
    vector<string> res;
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        if (tickets.size() == 1) return tickets[0];
        mp.clear();
        res.clear();
        for(const auto &element:tickets){
            mp[element[0]][element[1]]++;
        }
        res.emplace_back("JFK");
        traversal("JFK",tickets.size());
        return res;
    }
};

标签:tickets,used,return,res,行程,332,重新安排,vector,path
From: https://www.cnblogs.com/lihaoxiang/p/17321705.html

相关文章

  • day30| 332+51+37
    332.重新安排行程题目简述:给你一份航线列表tickets,其中tickets[i]=[fromi,toi]表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。所有这些机票都属于一个从JFK(肯尼迪国际机场)出发的先生,所以该行程必须从JFK开始。如果存在多种有效的行程,请你按字典排序......
  • JAVA生成行程单PDF
    JAVA生成行程单PDF一、pom依赖首先引入PDF需要的pom依赖<!--pdf--><dependency><groupId>com.itextpdf</groupId><artifactId>itextpdf</artifactId><version>5.5.13</version>......
  • 汇编_第一个可执行程序
    第一个可执行程序代码assumecs:codesg ;假设某一段寄存器和某一个程序段相联系codesgsegment ;定义一个段 movax,0123H movbx,0456H addax,bx addax,ax movax,4c00H int21H ;程序返回codesgendsend ;标识程序结束搭建汇编编译、链接和运行环境......
  • w1 洛谷T233243
      主要思路就是计算每一个长度为2的子串出现的次数,计数的同时用数组记录次数,打擂台找到出现次数最多的子串,首字符出现的位置就是数组的下标。最后输出出现最多的子串。代码如下:#include<bits/stdc++.h>usingnamespacestd;intcnt[100];intmain(){ intn,max=-1; ......
  • 3500/15 133292-01 到达时间预测解决方案阶段
    3500/15133292-01到达时间预测解决方案阶段今天,墨西哥的公共交通系统不具有提供信息来确定公共汽车的到达时间或者知道到达用户的公共汽车站的下一辆公共汽车上是否有空位的功能。这一信息与墨西哥城市密切相关,那里每天都有数百万用户需要移动。所提出的解决方案基于这样的事实......
  • Rust编程语言入门之项目实例:- 命令行程序
    项目实例:-命令行程序一、实例:接收命令行参数本章内容12.1接收命令行参数12.2读取文件12.3重构:改进模块和错误处理12.4使用TDD(测试驱动开发)开发库功能12.5使用环境变量12.6将错误消息写入标准错误而不是标准输出创建项目~/rust➜cargonewminigrepCre......
  • Python 自动化指南(繁琐工作自动化)第二版:附录 B:运行程序
    原文:https://automateboringuff.com/2e/appendixb/如果您在Mu中打开了一个程序,运行它只需按F5或单击窗口顶部的运行按钮。这是一种在编写程序的同时运行程序的简单方法,但是打开Mu来运行你完成的程序可能是一种负担。根据您使用的操作系统,有更方便的方法来执行Python脚......
  • win10计划任务程序库实现定时任务的自动执行程序及问题解决。
    win10计划任务程序库可以实现按照规则频率执行脚本的功能。现在将设置方法记录如下:创建任务步骤1、右键点击我的电脑,选择管理,依次点击:系统工具-》任务计划程序-》任务计划程序库。 2、点击最右侧操作中的创建基本任务,打开下面的弹窗。 3、创建任务的基本信息,下一步选择......
  • HDU 3328 Flipper 栈的应用
    FlipperTimeLimit:2000/1000MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):521    AcceptedSubmission(s):334ProblemDescriptionLittleBobbyRoberts(sonofBigBob,ofProblemG)playsthissolitairememory......
  • 202031607332-阿卜杜热合曼·麦麦提艾萨 实验一 软件工程准备—对课程的初步认识
    项目内容班级博客链接2023年春软件工程(2020级计算机科学与技术本次作业要求链接实验一软件工程准备我的课程学习目标1.学习博客园软件开发者学习社区使用技巧和经验2.了解Github的基本操作本次作业在哪些方面帮我实现学习目标学习了博客园使用技巧,Github的......