10.11狗狗onsite

发一个第三题的代码，思路如下：
BFS + DFS，
BFS 第i层，表示最少reverse i edges可以到达的node
DFS 表示以当前点， 按正常path遍历的到的点，
BFS 每次expand都expand直接指向该点node  的所有点 所能到达的点。
时间复杂度是O(E + V);

代码如下：

1.         static class Node{
   
2.                 int key;
   
3.                 Set<Node> to;
   
4.                 Set<Node> from;
   
5.                 public Node(){
   
6.                         to = new HashSet<>();
   
7.                         from = new HashSet<>();
   
8.                 }
   
9.         }
   
10.        
    
11.         public int minReverse(Node source, Node end){
    
12.                 Set<Node> visited = new HashSet<>();
    
13.                
    
14.                 Deque<Node> que = new ArrayDeque<>();
    
15.                
    
16.                 que.offer(source);
    
17.                
    
18.                 if(DFS(que, source, visited, end)) return 0;
    
19.                
    
20.                 int time = 1;
    
21.                 while(!que.isEmpty()){
    
22.                         int size = que.size();
    
23.                         for(int i = 0; i < size; i++){
    
24.                                 Node temp = que.poll();
    
25.                                 for(Node node : temp.from){
    
26.                                         if(DFS(que, node, visited, end)) return time;
    
27.                                 }
    
28.                         }
    
29.                         time++;
    
30.                 }
    
31.                 return -1;
    
32.         }
    
33.        
    
34.         private boolean DFS(Deque<Node> que, Node node, Set<Node> visited, Node end){
    
35.                 if(node == end) return true;
    
36.                
    
37.                 if(visited.contains(node)) return false;
    
38.                
    
39.                 que.offer(node);
    
40.                 visited.add(node);
    
41.                
    
42.                 for(Node next : node.to){
    
43.                         if(DFS(que, next, visited, end)) return true;
    
44.                 }
    
45.                
    
46.                 return false;
    
47.         }

复制代码

打了个注释， 供君参考

1. static class Node{
   
2.                 int key;
   
3.                 Set<Node> to;
   
4.                 Set<Node> from;
   
5.                 public Node(){
   
6.                         to = new HashSet<>();
   
7.                         from = new HashSet<>();
   
8.                 }
   
9.         }
   
10.        
    
11.         public int minReverse(Node source, Node end){
    
12.                 Set<Node> visited = new HashSet<>();
    
13.                
    
14.                 Deque<Node> que = new ArrayDeque<>();
    
15.                
    
16.                 // init the que with nodes that can achieve with 0 reverse
    
17.                 if(DFS(que, source, visited, end)) return 0;
    
18.                
    
19.                 int time = 1;
    
20.                 while(!que.isEmpty()){
    
21.                         int size = que.size();
    
22.                         // for all the node in next layer
    
23.                         for(int i = 0; i < size; i++){
    
24.                                 Node temp = que.poll();
    
25.                                 // only reverse one edge
    
26.                                 for(Node node : temp.from){
    
27.                                         // if find the end node, return the current the layer
    
28.                                         if(DFS(que, node, visited, end)) return time;
    
29.                                 }
    
30.                         }
    
31.                         // use one more reverse edges
    
32.                         time++;
    
33.                 }
    
34.                 return -1;
    
35.         }
    
36.        
    
37.         private boolean DFS(Deque<Node> que, Node node, Set<Node> visited, Node end){
    
38.                 // find end
    
39.                 if(node == end) return true;
    
40.                 // already visited
    
41.                 if(visited.contains(node)) return false;
    
42.                
    
43.                 // add to next layer
    
44.                 que.offer(node);
    
45.                
    
46.                 // make it visited
    
47.                 visited.add(node);
    
48.                
    
49.                 // visited all the node it can achieve without reverse an edge
    
50.                 for(Node next : node.to){
    
51.                         if(DFS(que, next, visited, end)) return true;
    
52.                 }
    
53.                
    
54.                 // not find end
    
55.                 return false;
    
56.         }

复制代码

哇 请问怎么明年继续啊 祝offer

byfwh 发表于 2018-10-16 08:57
哇 请问怎么明年继续啊 祝offer

意思是挂了就来年再战呗.....

求问什么叫做corner rectangle?

hongtunbaobao 发表于 2018-10-16 11:43
求问什么叫做corner rectangle?

四个点组成的  不需要填充

請問第四輪樓主什麼思路呢？

请问楼主第四题是用最暴力的方法做吗？