[每天两道题]坚持找到工作为止

207. Course Schedule 210. Course Schedule II
拓扑排序，拓扑排序是非常重要的图论的写法，之前就没有太理解，现在更加深刻了一些。
dfs写法可能对我比较好理解。

我认为拓扑排序主要难度在于编程技巧……
每一个节点一共有三个状态，状态1，未读取，状态2，正在读取，状态3， 已经读取。
默认都是未读取的状态。
我们从入度为0的节点开始，
先把它标记为状态2， 然后遍历它的邻居。
若是它没有邻居，就把它标记为已读取。再继续找下一个入读为零的节点重新开始。。
若是它有邻居，就递归进去。
当所有邻居都遍历完成，我们就把当前节点标记未状态3已读取。

递归的返回条件有两个，一个是遇到状态3，那么我们直接返回。另一个是遇到状态2， 此时说明有环。

这就是总体的逻辑，但是问题在于如何编程。
我看了看最简单的写法是定义一个int[] visit = new int[numCourses];
visit[i] = 0 状态 1 未读取
visit[i] = -1 状态2 在读取
visit[i] = 1 状态3 已读取

每次进入递归先判断visit的值，然后根据值返回或继续。若是visit[i] = 0，我们就先让它为 -1，再遍历邻居，再设置为1。

所以代码就是

1. class Solution {
   
2.     List<Integer> rs = new ArrayList<>();
   
3.     public int[] findOrder(int numCourses, int[][] prerequisites) {
   
4.         if( prerequisites.length == 0){
   
5.             int[] res = new int[numCourses];
   
6.             for(int i = 0; i < numCourses; i++) {
   
7.                res[i] = i;
   
8.             }
   
9.             return res;
   
10.         }
    
11.         Map<Integer, List<Integer>> map = new HashMap<>();
    
12.         
    
13.         for(int[] a : prerequisites) {
    
14.             List<Integer> l = map.getOrDefault(a[0], new ArrayList<>());
    
15.             l.add(a[1]);
    
16.             map.put(a[0], l);
    
17.         }
    
18.         int[] visit = new int[numCourses];
    
19.         for(int i = 0; i < numCourses; i++) {
    
20.             if(!helper(i, visit, map)) return new int[0];
    
21.         }
    
22.         
    
23.         int[] res = new int[numCourses];
    
24.         for(int i = 0; i < rs.size(); i++) {
    
25.             res[i] = rs.get(i);
    
26.         }
    
27.         return res;
    
28.     }
    
29.    
    
30.     private boolean helper(int node, int[] visit, Map<Integer, List<Integer>> map) {
    
31.         if(visit[node] > 0) {
    
32.             return true;
    
33.         }
    
34.         if(visit[node] < 0){
    
35.             return false;
    
36.         }
    
37.         
    
38.         visit[node] = -1;
    
39.         
    
40.         if(map.containsKey(node)) {
    
41.             List<Integer> nei = map.get(node);
    
42.             for(int next : nei) {
    
43.                 if(!helper(next, visit, map)) return false;
    
44.             }
    
45.         }
    
46.         
    
47.         visit[node] = 1;
    
48.         rs.add(node);
    
49.         return true;
    
50.     }
    
51. }

复制代码

209. Minimum Size Subarray Sum

1. class Solution {
   
2.     public int minSubArrayLen(int target, int[] nums) {
   
3.         int rs = Integer.MAX_VALUE;
   
4.         int sum = 0;
   
5.         int l = 0;
   
6.         for(int i = 0; i < nums.length; i++) {
   
7.             sum += nums[i];
   
8.             while(sum >= target ) {
   
9.                 rs = Math.min(rs, i - l + 1);
   
10.                 sum -= nums[l];
    
11.                 l++;
    
12.             }
    
13.         }
    
14.         return rs == Integer.MAX_VALUE ? 0 : rs;
    
15.     }
    
16. }

复制代码

208. Implement Trie (Prefix Tree)

1. class Trie {
   
2. 
   
3.     Node root;
   
4.     public Trie() {
   
5.         root = new Node();
   
6.     }
   
7.    
   
8.     public void insert(String word) {
   
9.         Node curr = root;
   
10.         for(char c : word.toCharArray()) {
    
11.             curr.add(c);
    
12.             curr = curr.find(c);
    
13.         }
    
14.         curr.isWord = true;
    
15.     }
    
16.    
    
17.     public boolean search(String word) {
    
18.         Node curr = root;
    
19.         for(char c : word.toCharArray()) {
    
20.             curr = curr.find(c);
    
21.             if(curr == null) return false;
    
22.         }
    
23.         return curr.isWord;
    
24.     }
    
25.    
    
26.     public boolean startsWith(String prefix) {
    
27.         Node curr = root;
    
28.         for(char c : prefix.toCharArray()) {
    
29.             curr = curr.find(c);
    
30.             if(curr == null) return false;
    
31.         }
    
32.         return true;
    
33.     }
    
34. }
    
35. 
    
36. class Node{
    
37.     char c;
    
38.     Map<Character, Node> next;
    
39.     boolean isWord;
    
40.    
    
41.     public Node() {
    
42.         next = new HashMap<>();
    
43.         isWord = false;
    
44.     }
    
45.    
    
46.     public Node(char c) {
    
47.         this.c = c;
    
48.         next = new HashMap<>();
    
49.         isWord = false;
    
50.     }
    
51.    
    
52.     public void add(char c) {
    
53.         if(find(c) == null){
    
54.           next.put(c, new Node(c));  
    
55.         }
    
56.     }
    
57.    
    
58.     public Node find(char c) {
    
59.         if(next.containsKey(c)) return next.get(c);
    
60.         return null;
    
61.     }
    
62. }

复制代码