332. 重新安排行程

给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。

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

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

示例 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
  • fromi 和 toi 由大写英文字母组成
  • fromi != toi

思路：
经典的欧拉通路问题，只是题目要求输出字典序最小的行程组合。
记录一笔画中的所有点

  1. class Solution {
  2.     Map<String, Queue<String>> map = new HashMap<>();
  3.     List<String> res = new ArrayList<>();
  4.     public List<String> findItinerary(List<List<String>> tickets) {
  5.         Collections.sort(tickets, (o1, o2) -> {
  6.             if (o1.get(0).equals(o2.get(0))) {
  7.                 return o1.get(1).compareTo(o2.get(1));
  8.             } else {
  9.                 return o1.get(0).compareTo(o2.get(0));
  10.             }
  11.         });
  12.         for (List<String> list : tickets) {
  13.             String S = list.get(0), E = list.get(1);
  14.             map.computeIfAbsent(S, key -> new LinkedList<>()).offer(E);
  15.         }
  17.         dfs("JFK");
  18.         res.add("JFK");
  19.         Collections.reverse(res);
  20.         return res;
  21.     }
  22.     void dfs(String u) {
  23.         Queue<String> q = map.get(u);
  24.         if (q == null) return;
  26.         while (!q.isEmpty()) {
  27.             String ne = q.poll();
  28.             dfs(ne);
  29.             res.add(ne);
  30.         }
  31.     }
  32. }
  1. class Solution {
  2.     int[] res = new int[310];
  3.     int cnt = 0;
  4.     public List<String> findItinerary(List<List<String>> tickets) {
  5.         TreeSet<String> set = new TreeSet<>();
  6.         Map<String, Integer> map = new HashMap<>();
  7.         for (var t : tickets) {
  8.             for (var s : t)
  9.                 set.add(s);
  10.         }
  11.         int n = set.size();
  12.         String[] unmap = new String[n];
  13.         int idx = 0;
  14.         for (String s : set) {
  15.             unmap[idx] = s;
  16.             map.put(s, idx++);
  17.         }
  19.         int[][] g = new int[n][n];
  20.         for (var t : tickets) {
  21.             String a = t.get(0), b = t.get(1);
  22.             int x = map.get(a), y = map.get(b);
  23.             g[x][y]++;
  24.         }
  26.         dfs(map.get("JFK"), g);
  27.         List<String> ans = new ArrayList<>();
  28.         for (int i = cnt; i > 0; i--)
  29.             ans.add(unmap[res[i]]);
  30.         return ans;
  31.     }
  33.     void dfs(int u, int[][] g) {
  34.         for (int i = 0; i < g[u].length; i++) {
  35.             if (g[u][i] > 0) {
  36.                 g[u][i] --;
  37.                 dfs(i, g);
  38.             }
  39.         }
  40.         res[++cnt] = u;
  41.     }
  42. }

5932. 合法重新排列数对

思路：
记录一笔画中的所有边

  1. class Solution {
  2.     Map<Integer, Queue<Integer>> map = new HashMap<>();
  3.     List<int[]> res = new ArrayList<>();
  4.     public int[][] validArrangement(int[][] pairs) {
  5.         Map<Integer, Integer> din = new HashMap<>();
  6.         Map<Integer, Integer> dout = new HashMap<>();
  8.         int min = Integer.MAX_VALUE;
  9.         for (int[] p : pairs) {
  10.             int a = p[0], b = p[1];
  11.             din.merge(b, 1, Integer::sum);
  12.             dout.merge(a, 1, Integer::sum);
  13.             min = Math.min(a, min);
  14.             map.computeIfAbsent(a, key -> new LinkedList<>()).offer(b);
  15.         }
  17.         for (int key : map.keySet()) {
  18.             if (din.getOrDefault(key, 0) + 1 == dout.getOrDefault(key, 0)) {
  19.                 min = key;
  20.                 break;
  21.             }
  22.         }
  24.         dfs(min);
  25.         Collections.reverse(res);
  26.         return res.toArray(new int[pairs.length][]);
  27.     }
  29.     void dfs(int u) {
  30.         var q = map.get(u);
  31.         if (q == null || q.isEmpty()) return;
  32.         while (!q.isEmpty()) {
  33.             int v = q.poll();
  34.             dfs(v);
  35.             res.add(new int[]{u, v});
  36.         }
  37.     }
  38. }

753. 破解保险箱

思路：
将每个密码看作一条边，而图中的节点正好是密码的位数减一能组成的字符串
证明：图是连通的，且每个节点的入度等于出度
说明可以构成欧拉回路

  1. class Solution {
  2.     int k;
  3.     Set<String> used = new HashSet<>();
  4.     StringBuilder ans = new StringBuilder();
  5.     public String crackSafe(int n, int k) {
  6.         this.k = k;
  7.         StringBuilder start = new StringBuilder();
  8.         for (int i = 1; i < n; i++)
  9.             start.append("0");
  11.         dfs(start.toString());
  12.         ans.append(start);
  13.         return ans.toString();
  14.     }
  16.     void dfs(String s) {
  17.         for (int i = 0; i < k; i++) {
  18.             String v = s + i;
  19.             if (!used.contains(v)) {
  20.                 used.add(v);
  21.                 dfs(v.substring(1, v.length()));
  22.                 ans.append(i);
  23.             }
  24.         }
  25.     }
  26. }