一亩三分地

 找回密码 注册账号

扫描二维码登录本站

BBS
Offer多多
Salarytics
交友
Learn
Who's Hiring?
Visa Tracker
疫情动态
指尖新闻
Instant
客户端
微信公众号
扫码关注公众号
留学申请公众号
扫码关注留学申请公众号
Youtube频道
留学博客
关于我们
查看: 305|回复: 4
收起左侧

[学Java/C#] LeetCode 332. Reconstruct Itinerary 有人能看懂这个DFS解法吗?

[复制链接] |只看干货 |学java/c#, 刷题
我的人缘0

分享帖子到朋友圈
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   74% (236)
 
 
25% (79)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
本帖最后由 zurich.hill 于 2020-9-25 07:25 编辑

代码不难但是,好难理解啊?  似乎和Hierholzer算法有关系吗?  

求一粒米。

(此外,是否有可能有3个飞机站,有奇数个入度)

[Java] 纯文本查看 复制代码
public class Solution {

   public List<String> findItinerary(String[][] tickets) {
       
        for (String[] ticket : tickets) {
            targets.computeIfAbsent(ticket[0], k -> new PriorityQueue()).add(ticket[1]);
        }
       
        visit("JFK");

        return route;
    }

    Map<String, PriorityQueue<String>> targets = new HashMap<>();
    
    List<String> route = new LinkedList();

    void visit(String airport) {
        
        while(targets.containsKey(airport) && !targets.get(airport).isEmpty()) {
         
            visit( targets.get(airport).poll() );
        }
        
        route.add(0, airport);
    }
}
  



跪求战友解答

评分

参与人数 1大米 +1 收起 理由
14417335 + 1

查看全部评分


上一篇:请教下Binary Search模版
下一篇:求教leetcode会员用法
我的人缘0

升级   2.58%

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   95% (870)
 
 
4% (38)    👎
建议看一下一笔画的问题: https://en.m.wikipedia.org/wiki/Eulerian_path

说不定你就明白了
回复

使用道具 举报

我的人缘0
 楼主| zurich.hill 2020-9-25 10:55:44 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   74% (236)
 
 
25% (79)    👎
wx6807 发表于 2020-9-25 07:40
建议看一下一笔画的问题: https://en.m.wikipedia.org/wiki/Eulerian_path

说不定你就明白了

看完才发帖的。
回复

使用道具 举报

我的人缘0

升级   52%

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (306)
 
 
1% (6)    👎
可以设个breakpoint在dfs里面看看airport的值
如果是死胡同+字典序 一定是第一个跳出recursion 然后插入到结果的最后一段
回复

使用道具 举报

我的人缘0
 楼主| zurich.hill 2020-9-26 03:29:31 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   74% (236)
 
 
25% (79)    👎
Musclekai 发表于 2020-9-25 17:10
可以设个breakpoint在dfs里面看看airport的值
如果是死胡同+字典序 一定是第一个跳出recursion 然后插入到 ...

不懂不懂不懂不懂不懂
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

Some icons made by Freepik from flaticon.com

快速回复 返回顶部 返回列表