🌕 🌕 🌗 332. 重新安排行程

难度: 🌕 🌕 🌗

问题描述

---

解法

class Solution {
    HashMap<String, TreeMap<String, Integer>> map;
    int total;
    List<String> res;
    public List<String> findItinerary(List<List<String>> tickets) {
        // 思路：
        // 字典序最小的行程组合 - 排序 - TreeSet
        // 机票存在重复 - 记录次数 - TreeMap
        int len = tickets.size();
        total = len + 1; // 需要经历的站点数
        map = new HashMap<>();
        // 初始化 map
        for(List<String> cur: tickets) {
            String from = cur.get(0);
            String to = cur.get(1);
            if(!map.containsKey(from)) {
                TreeMap<String, Integer> tmpMap = new TreeMap<>();
                map.put(from, tmpMap);
            }
            TreeMap<String, Integer> tmap = map.get(from);
            if(!tmap.containsKey(to)) {
                tmap.put(to, 1);
            } else {
                int fre = tmap.get(to);
                fre ++;
                tmap.put(to, fre);
            }
            map.put(from, tmap); // 更新票数
        }
        // 回溯
        String first = "JFK";
        LinkedList<String> path = new LinkedList<>();
        path.addLast(first);
        mySol(first, path);
        return res;
    }

    private boolean mySol(String from, LinkedList<String> path) {
        // System.out.println(Arrays.toString(path.toArray()));
        // 递归终止条件
        if(path.size() == total) {
            // 所有机票已经用完
            res = new LinkedList<String>(path);
            return true;
        }
        // 继续从当前站点出发
        TreeMap<String, Integer> tmap = map.get(from);
        if(tmap == null) {
            return false;
        }
        for(Map.Entry<String, Integer> entry: tmap.entrySet()) {
            String to = entry.getKey();
            int count = entry.getValue();
            if(count <= 0) {
                continue;
            }
            // System.out.println(from + " --> " + to + "  " + count);
            count --;
            tmap.put(to, count);
            map.put(from, tmap);
            path.addLast(to);
            if(mySol(to, path)) {
                return true;
            }
            count ++;
            // count 为基本数据类型，因此需要手动刷回 map
            tmap.put(to, count);
            map.put(from, tmap);
            path.removeLast();
        }
        return false;
    }
}

---

输出