LintCode 615：课程表

https://www.lintcode.com/problem/course-schedule

描述

现在你总共有 n 门课需要选，记为 0 到 n - 1.
一些课程在修之前需要先修另外的一些课程，比如要学习课程 0 你需要先学习课程 1 ，表示为[0,1]
给定n门课以及他们的先决条件，判断是否可能完成所有课程？

样例

  1. 输入: n = 2, prerequisites = [[1,0]] 
  2. 输出: true
  4. 输入: n = 2, prerequisites = [[1,0],[0,1]] 
  5. 输出: false

解题思路

拓扑排序，不能有环，和https://www.lintcode.com/problem/topological-sorting 题一样的解法，最后如果有课程入度不为0则表示不能完成所有课程。

AC代码

  1.     public boolean canFinish(int numCourses, int[][] prerequisites) {
  2.         // 存储每个课程的入度（直接用数组更好）
  3.         Map<Integer, Integer> map = new HashMap<>();
  4.         // 存储每个课程的后置课程
  5.         Map<Integer, Set<Integer>> dict = new HashMap<>();
  6.         // 获取每个课程的入度和其后置课程
  7.         for (int[] arr : prerequisites) {
  8.             int x = arr[0];
  9.             int y = arr[1];
  10.             if (!dict.containsKey(y)) {
  11.                 Set<Integer> set = new HashSet<>();
  12.                 dict.put(y, set);
  13.             }
  14.             // 数据中有重复的边。。需要去重
  15.             if (dict.get(y).contains(x)) {
  16.                 continue;
  17.             }
  18.             if (!map.containsKey(x)) {
  19.                 map.put(x, 0);
  20.             }
  21.             map.put(x, map.get(x) + 1);
  22.             if (!map.containsKey(y)) { map.put(y, 0); }
  23.             dict.get(y).add(x);
  24.         }
  25.         // 宽搜队列，入度为0的课程首先加入队列
  26.         Deque<Integer> deque = new ArrayDeque<>();
  27.         for (Integer course : map.keySet()) {
  28.             if (map.get(course) == 0) {
  29.                 deque.add(course);
  30.             }
  31.         }
  33.         // 简单宽搜过程，当一个课程入度为0了加入队列
  34.         while (!deque.isEmpty()) {
  35.             int course = deque.removeFirst();
  36.             // 取出的课程从map中删除，当map中没有课程了时表明所有课程都可以被选上
  37.             map.remove(course);
  38.             if (!dict.containsKey(course)) {
  39.                 continue;
  40.             }
  41.             for (Integer x : dict.get(course)) {
  42.                 map.put(x, map.get(x) - 1);
  43.                 if (map.get(x) == 0) {
  44.                     deque.add(x);
  45.                 }
  46.             }
  47.         }
  48.         // 返回答案
  49.         return map.size() == 0;
  50.     }

LintCode 618：搜索图中节点

https://www.lintcode.com/problem/search-graph-nodes

描述

给定一张 无向图，一个 节点 以及一个 目标值，返回距离这个节点最近 且 值为目标值的节点，如果不能找到则返回 NULL。
在给出的参数中, 我们用 map 来存节点的值
保证答案唯一

样例

  1. 输入:
  2. {1,2,3,4#2,1,3#3,1,2#4,1,5#5,4}
  3. [3,4,5,50,50]
  4. 1
  5. 50
  6. 输出:
  7. 4
  8. 解释:
  9. 2------3  5
  10.  \     |  | 
  11.   \    |  |
  12.    \   |  |
  13.     \  |  |
  14.       1 --4
  15. Give a node 1, target is 50
  17. there a hash named values which is [3,4,10,50,50], represent:
  18. Value of node 1 is 3
  19. Value of node 2 is 4
  20. Value of node 3 is 10
  21. Value of node 4 is 50
  22. Value of node 5 is 50
  24. Return node 4

解题思路

标准的宽搜题，每次从节点扩展它能到达的节点，为target直接返回节点，不是加入宽搜队列。

AC代码

  1. public UndirectedGraphNode searchNode(ArrayList<UndirectedGraphNode> graph,
  2.                                       Map<UndirectedGraphNode, Integer> values,
  3.                                       UndirectedGraphNode node,
  4.                                       int target) {
  5.     // 出发点的value便是target直接返回
  6.     if (values.get(node) == target) {
  7.         return node;
  8.     }
  9.     // 宽搜队列
  10.     Deque<UndirectedGraphNode> deque = new ArrayDeque<>();
  11.     deque.add(node);    
  12.     // 记录已经走过的节点
  13.     Set<Integer> set = new HashSet<>();
  14.     while (!deque.isEmpty()) {
  15.         // 取出节点
  16.         UndirectedGraphNode unode = deque.removeFirst();
  17.         set.add(unode.label);
  18.         // 拓展
  19.         for (UndirectedGraphNode node1 : unode.neighbors) {
  20.             if (values.get(node1) == target) {
  21.                 return node1;
  22.             }
  23.             if (!set.contains(node1.label)) {
  24.                 deque.add(node1);
  25.             }
  26.         }
  27.     }
  28.     return null;
  29. }

LintCode 605：序列重构

https://www.lintcode.com/problem/sequence-reconstruction

描述

判断是否序列 org 能唯一地由 seqs重构得出. org是一个由从1到n的正整数排列而成的序列，1 \leq n \leq 10^41≤n≤104。 重构表示组合成seqs的一个最短的父序列 (意思是，一个最短的序列使得所有 seqs里的序列都是它的子序列).
判断是否有且仅有一个能从 seqs重构出来的序列，并且这个序列是org。

样例

  1. 输入:org = [1,2,3], seqs = [[1,2],[1,3]]
  2. 输出: false
  3. 解释:
  4. [1,2,3] 并不是唯一可以被重构出的序列，还可以重构出 [1,3,2]
  6. 输入: org = [1,2,3], seqs = [[1,2],[1,3],[2,3]]
  7. 输出: true
  8. 解释:
  9. 序列 [1,2], [1,3], 和 [2,3] 可以唯一重构出 [1,2,3].
  11. 输入:org = [4,1,5,2,6,3], seqs = [[5,2,6,3],[4,1,5,2]]
  12. 输出:true

解题思路

拓扑排序
观看题目可以想象 seqs 的一个序列可以构成一个顺序，所有序列加起来就能构成一个拓扑排序。
而 org 要是唯一的序列，那么seqs只能 构成一个拓扑排序，如果有多的拓扑排序那便不能唯一。

AC代码

写的比较垃圾。。。。

  1. public boolean sequenceReconstruction(int[] org, int[][] seqs) {
  3.     // 边界条件
  4.     if (org.length < 1) { return true;}
  5.     // 存储拓扑顺序
  6.     Map<Integer, List<Integer>> map = new HashMap<>();
  7.     // 存储每个点的入度
  8.     int[] in = new int[org.length + 1];
  9.     // 预处理，有不在org序列中的数或者seqs长度不够org可以直接返回false。
  10.     int length = 0;
  11.     for (int[] arr : seqs) {
  12.         for (int i = 1; i < arr.length; i++) {
  13.             int x = arr[i - 1], y = arr[i];
  14.             if (y > org.length) {
  15.                 return false;
  16.             }
  17.             if (!map.containsKey(x)) {
  18.                 map.put(x, new ArrayList<>());
  19.             }
  20.             // 存储顺序和入度
  21.             map.get(x).add(y);
  22.             in[y]++;
  23.         }
  24.         // 记录seqs长度
  25.         length += arr.length;
  26.         if (arr.length > 0 && arr[0] > org.length) {
  27.             return false;
  28.         }
  29.     }
  30.     //seqs长度不够org可以直接返回false
  31.     if (length < org.length) {
  32.         return false;
  33.     }
  35.     // 宽搜队列，按找org序列顺序进出队列。
  36.     Deque<Integer> deque = new ArrayDeque<>();
  37.     int index = 0;
  38.     deque.add(org[index]);
  40.     while (!deque.isEmpty()) {
  41.         int x = deque.removeFirst();
  42.         index++;
  43.         // index 等于 org.length表明org序列已经走完且唯一返回true
  44.         if (index == org.length) {
  45.             return true;
  46.         }
  47.         // x 没有扩展了，而org还没结束，返回false
  48.         if (!map.containsKey(x)) {
  49.             return false;
  50.         }
  51.         int next = org[index];
  52.         for (Integer y : map.get(x)) {
  53.             in[y]--;
  54.             // 不是 org序列的下一个元素入度为 0 代表拓扑顺序不唯一，返回false
  55.             if (in[y] == 0 && y != next) {
  56.                 return false;
  57.             }
  58.         }
  59.         // 序列的下一个不为0代表序列不成功，返回false
  60.         if (in[next] != 0) {
  61.             return false;
  62.         }
  63.         deque.add(next);
  64.     }
  65.     return false;
  66. }

LintCode 598：僵尸矩阵

https://www.lintcode.com/problem/zombie-in-matrix

描述

给一个二维网格，每一个格子都有一个值，2 代表墙，1 代表僵尸，0 代表人类(数字 0, 1, 2)。僵尸每天可以将上下左右最接近的人类感染成僵尸，但不能穿墙。将所有人类感染为僵尸需要多久，如果不能感染所有人则返回 -1。

样例

  1. 输入:
  2. [[0,1,2,0,0],
  3.  [1,0,0,2,1],
  4.  [0,1,0,0,0]]
  5. 输出:
  6. 2
  8. 输入:
  9. [[0,0,0],
  10.  [0,0,0],
  11.  [0,0,1]]
  12. 输出:
  13. 4

解题思路

简单宽搜题，首先将僵尸加入宽搜队列，然后每步将队列的僵尸都去感染附件的人类，已经传播过的僵尸设为2。避免重复感染。
最后还有0表示不能感染所有人，否则返回宽搜了多少次。

AC代码

  1. public class Solution {
  3.     public int zombie(int[][] grid) {
  4.         // 宽搜队列
  5.         Deque<Point> deque = new ArrayDeque<>();
  6.         // 预处理，将初始僵尸加入宽搜队列
  7.         int n = grid.length, m = grid[0].length;
  8.         int count = 0;
  9.         for (int i = 0; i < n; i++) {
  10.             for (int j = 0; j < m; j++) {
  11.                 if (grid[i][j] == 0) {
  12.                     count++;
  13.                 } else if (grid[i][j] == 1) {
  14.                     Point point = new Point(i, j);
  15.                     deque.add(point);
  16.                     // 已经传播过的僵尸设为2
  17.                     grid[i][j] = 2;
  18.                 }
  19.             }
  20.         }
  21.         // 方便计算上下左右
  22.         int[] a = {0, 0, 1, -1};
  23.         int[] b = {1, -1, 0, 0};
  25.         int day = 0;
  26.         while (!deque.isEmpty()) {
  27.             day++;
  28.             int size = deque.size();
  29.             for (int i = 0; i < size; i++) {
  30.                 Point point = deque.removeFirst();
  31.                 for (int j = 0; j < 4; j++) {
  32.                     int x = point.x + a[j];
  33.                     int y = point.y + b[j];
  34.                     if (x >= n || x < 0 || y >= m || y < 0 || grid[x][y] == 2) {
  35.                         continue;
  36.                     }
  37.                     count--;
  38.                     grid[x][y] = 2;
  39.                     deque.add(new Point(x, y));
  40.                 }
  41.             }
  42.             if (count == 0) {
  43.                 return day;
  44.             }
  45.         }
  47.         return count > 0 ? -1 : day;
  48.     }
  49. }
  51. class Point {
  52.     int x;
  53.     int y;
  55.     Point(int x, int y) {
  56.         this.x = x;
  57.         this.y = y;
  58.     }
  59. }

LintCode 178：图是否是树

https://www.lintcode.com/problem/graph-valid-tree

描述

给出 n 个节点，标号分别从 0 到 n - 1 并且给出一个 无向 边的列表 (给出每条边的两个顶点), 写一个函数去判断这张｀无向｀图是否是一棵树
你可以假设我们不会给出重复的边在边的列表当中. 无向边　[0, 1] 和 [1, 0]　是同一条边， 因此他们不会同时出现在我们给你的边的列表当中。

样例

  1. 输入: n = 5 edges = [[0, 1], [0, 2], [0, 3], [1, 4]]
  2. 输出: true.
  4. 输入: n = 5 edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]
  5. 输出: false.

解题思路

BFS
一棵n个节点的树只有n-1条边，当一个图有n-1条边且没有环时便是一棵树。
对输入预处理存储图的关系后，随便从一个节点宽搜，最后队列能走过n个点便是没有环的图，也就是树。
并查集
用并查集合并相连的点，遍历每条边，合并前判断两个节点是否属于同一个集合，属于同一个集合表明有环，不是树；不是同一个集合则合并。
最后如果所有点都在一个集合中，则说明这个图联通且无环，是一棵树。

AC代码

  1. public boolean validTree(int n, int[][] edges) {
  2.     // 不是n-1条边便不是一棵树。
  3.     if (n == 0 || edges.length != n - 1) {
  4.         return false;
  5.     }
  7.     Map<Integer, Set<Integer>> map = new HashMap<>();
  8.     Set<Integer> set = new HashSet<>();
  9.     Deque<Integer> deque = new ArrayDeque<>();
  11.     for (int[] arr : edges) {
  12.         int x = arr[0], y = arr[1];
  13.         if (!map.containsKey(x)) {map.put(x, new HashSet<>());}
  14.         if (!map.containsKey(y)) {map.put(y, new HashSet<>());}
  15.         map.get(x).add(y);
  16.         map.get(y).add(x);
  17.     }
  18.     // 标准宽搜过程，走过的节点都加入set中
  19.     deque.add(0);
  20.     while (!deque.isEmpty()) {
  21.         int x = deque.removeFirst();
  22.         set.add(x);
  23.         if (!map.containsKey(x)) {
  24.             continue;
  25.         }
  26.         for (Integer next : map.get(x)) {
  27.             if (!set.contains(next)) {
  28.                 set.add(next);
  29.                 deque.add(next);
  30.             }
  31.         }
  32.     }
  33.     // 宽搜没有走完n个节点表明有环，不是树
  34.     return set.size() == n;      
  35. }

LintCode 892：外星人字典

https://www.lintcode.com/problem/alien-dictionary

描述

有一种新的使用拉丁字母的外来语言。但是，你不知道字母之间的顺序。你会从词典中收到一个非空的单词列表，其中的单词在这种新语言的规则下按字典顺序排序。请推导出这种语言的字母顺序。

  1. 你可以假设所有的字母都是小写。
  2. 如果a是b的前缀且b出现在a之前，那么这个顺序是无效的。
  3. 如果顺序是无效的，则返回空字符串。
  4. 这里可能有多个有效的字母顺序，返回以正常字典顺序看来最小的。

    样例

    ```java 输入：[“wrt”,”wrf”,”er”,”ett”,”rftt”] 输出：”wertf” 解释： 从 “wrt”和”wrf” ,我们可以得到 ‘t’<’f’ 从 “wrt”和”er” ,我们可以得到’w’<’e’ 从 “er”和”ett” ,我们可以得到 get ‘r’<’t’ 从 “ett”和”rftt” ,我们可以得到 ‘e’<’r’ 所以返回 “wertf”

输入：[“z”,”x”] 输出：”zx” 解释： 从 “z” 和 “x”，我们可以得到 ‘z’ < ‘x’ 所以返回”zx” 

  1. <a name="TdKQJ"></a>
  2. #### 解题思路
  3. 拓扑排序。每两个单词之间可以确定一个顺序，这样就可以得到拓扑排序的一个指向。例如 "wrt"和"wrf"，就可以得到 t -> f。<br />两个单词中的第一个相同位置不同字母可以确定出一个指向。<br />得到所有指向后便可整理出一个拓扑顺序，判断是否可以排出一个字典顺序（有环便没有）。
  4. <a name="Oe5BG"></a>
  5. #### AC代码
  6. ```java
  7. // 九章
  8. public String alienOrder(String[] words) {
  9.     // 先构造拓扑排序的每一条边
  10.     Map<Character, Set<Character>> graph = constructGraph(words);
  11.     if (graph == null) {
  12.         return "";
  13.     }
  14.     // 宽搜找寻拓扑顺序
  15.     return topologicalSorting(graph);
  16. }
  18. // 建图，找出拓扑排序中的每一条边，也就是字母的顺序
  19. private Map<Character, Set<Character>> constructGraph(String[] words) {
  20.     Map<Character, Set<Character>> graph = new HashMap<>();
  21.     // 先给每个字母初始化
  22.     for (int i = 0; i < words.length; i++) {
  23.         for (int j = 0; j < words[i].length(); j++) {
  24.             char c = words[i].charAt(j);
  25.             if (!graph.containsKey(c)) {
  26.                 graph.put(c, new HashSet<>());
  27.             }
  28.         }
  29.     }
  31.     for (int i = 0; i < words.length - 1; i++) {
  32.         int index = 0;
  33.         while (index < words[i].length() && index < words[i + 1].length()) {
  34.             // 找到第一个字母不相同的位置，建立边
  35.             if (words[i].charAt(index) != words[i + 1].charAt(index)) {
  36.                 graph.get(words[i].charAt(index)).add(words[i + 1].charAt(index));
  37.                 break;
  38.             }
  39.             index++;
  40.         }
  41.         // 如果长单词前缀是短单词，并且短单词还排在长单词后面，表明无解。
  42.         if (index == Math.min(words[i].length(), words[i + 1].length())) {
  43.             if (words[i].length() > words[i + 1].length()) {
  44.                 return null;
  45.             }
  46.         }
  47.     }
  49.     return graph;
  50. }
  52. // 获取每个字母的入度，同之前的拓扑排序一样
  53. private Map<Character, Integer> getIndegree(Map<Character, Set<Character>> graph) {
  54.     Map<Character, Integer> indegree = new HashMap<>();
  55.     for (Character u : graph.keySet()) {
  56.         indegree.put(u, 0);
  57.     }
  59.     for (Character u : graph.keySet()) {
  60.         for (Character v : graph.get(u)) {
  61.             indegree.put(v, indegree.get(v) + 1);
  62.         }
  63.     }
  65.     return indegree;
  66. }
  68. private String topologicalSorting(Map<Character, Set<Character>> graph) {
  69.     Map<Character, Integer> indgree = getIndegree(graph);
  70.     // 优先队列，因为要返回正常字典顺序看起来最小的
  71.     Queue<Character> queue = new PriorityQueue<>();
  72.     // 将入度为0的单词都加入队列中
  73.     for (Character u : indgree.keySet()) {
  74.         if (indgree.get(u) == 0) {
  75.             queue.offer(u);
  76.         }
  77.     }
  78.     // 标准宽搜过程
  79.     StringBuilder sb = new StringBuilder();
  80.     while (!queue.isEmpty()) {
  81.         Character head = queue.poll();
  82.         sb.append(head);
  83.         for (Character neighbor : graph.get(head)) {
  84.             indgree.put(neighbor, indgree.get(neighbor) - 1);
  85.             if (indgree.get(neighbor) == 0) {
  86.                 queue.offer(neighbor);
  87.             }
  88.         }
  89.     }
  90.     // 表明有环
  91.     if (sb.length() != indgree.size()) {
  92.         return "";
  93.     }
  95.     return sb.toString();
  96. }