Quora OA 介于版里资源少，最近又有人问我，来补个面经，攒个人品

1. import java.util.*;
   
2. public class QuoraStackingBox {
   
3.         public static void main(String[] args){
   
4. //                Scanner scan = new Scanner(System.in);
   
5. //        int n = 0;
   
6. //        if(scan.hasNextInt()){
   
7. //            n = scan.nextInt();
   
8. //        }
   
9. //        int[][] input = new int[n][2];
   
10. //        for(int i = 0; i < n; i++){
    
11. //            if(scan.hasNextInt()){
    
12. //                input[i][0] = scan.nextInt();
    
13. //            }
    
14. //            if(scan.hasNextInt()){
    
15. //                input[i][1] = scan.nextInt();
    
16. //            }
    
17. //        }
    
18. //        System.out.println("");
    
19.                 QuoraStackingBox solution = new QuoraStackingBox();
    
20.                 int[][] input = new int[][]{{9,4}, {6,9}, {6,9}, {6,4}, {1,1}};//{2,5},{3,3},{6,6},{7,8}};//,{1,10},{1,1},{1,1},{1,1}};
    
21. //                int[][] input = null;
    
22. //                int[][] input = new int[][]{};
    
23. //                System.out.println(solution.stackingBox(input));
    
24. //                test constructDirectedGraph()  PASS!
    
25. //                int[][] res = solution.constructDirectedGraph(input);
    
26. //                for(int i = 0; i < res.length; i++){
    
27. //                        for(int j = 0; j < res.length; j++){
    
28. //                                System.out.print(res[i][j]);
    
29. //                        }
    
30. //                        System.out.println();
    
31. //                }
    
32.                 System.out.println(solution.stackingBox(input));
    
33.                
    
34.         }
    
35.         public int stackingBox(int[][] box){
    
36.                 if(box == null || box.length == 0){
    
37.                         return 0;
    
38.                 }
    
39.                 int[][] graph = constructDirectedGraph(box);
    
40.                 int s = graph.length - 2;
    
41.                 int t = graph.length - 1;
    
42.                 return fordFulkerson(graph, s, t);
    
43.         }
    
44.        
    
45.         //bfs all vertices, if there is a path from source "s" to sink "t" in the residual graph
    
46.         //return true; Also the function fills "parentPath[]" to store the path
    
47.         public boolean bfs(int graph[][], int s, int t, int[] parentPath){
    
48.                 //visited array to used to mark the vertices that has been visited
    
49.                 //if visited: true, else: false
    
50.                 boolean[] visited = new boolean[graph.length];
    
51.                 //create a queue, enqueue source vertex and mark it as visited
    
52.                 Deque<Integer> queue = new LinkedList<Integer>();
    
53.                 queue.offer(s);
    
54.         visited[s] = true;
    
55.         parentPath[s]=-1;
    
56.         //Standard BFS Loop
    
57.                 while(!queue.isEmpty()){
    
58.                         int curr = queue.poll();
    
59.                         for(int i = 0; i < graph.length; i++){
    
60.                                 if(visited[i] || graph[curr][i] == 0){
    
61.                                         continue;
    
62.                                 }
    
63.                                 queue.offer(i);
    
64.                                 parentPath[i] = curr;
    
65.                                 visited[i] = true;
    
66.                         }
    
67.                 }
    
68.                 //if sink "t" has been visited, which means we have reached "t" in
    
69.                 //BFS starting from source, then we return true; else, return false.
    
70.                 return visited[t] == true;
    
71.         }
    
72.         //Ford Fulkerson algorithm to find Max Flow
    
73.         //return the maximum flow value from s to t in the given graph
    
74.         int fordFulkerson(int[][] graph, int s, int t)
    
75.     {
    
76.                 int[][] residualGraph = new int[graph.length][graph.length];
    
77.                 for(int i = 0; i < graph.length; i++){
    
78.                         for(int j = 0; j < graph.length; j++){
    
79.                                 residualGraph[i][j] = graph[i][j];
    
80.                         }
    
81.                 }
    
82.                 int maxFlow = 0;
    
83.                 int parentPath[] = new int[graph.length];
    
84.                 //test
    
85.                
    
86.                 while(bfs(residualGraph, s, t, parentPath)){
    
87.                         //Find minimum residual capacity(min_capacity) of the edges along the path filled by BFS
    
88.                         //min_capacity is also the max_Flow on this path
    
89.                         int min_capacity = Integer.MAX_VALUE;
    
90.                         int v = t;
    
91.                         while(parentPath[v] != s){
    
92.                                 int u = parentPath[v];
    
93.                                 min_capacity = Math.min(min_capacity, residualGraph[u][v]);
    
94.                                 v = u;
    
95.                         }
    
96.                         //update Residual Graph
    
97.                         int vv = t;
    
98.                         while(parentPath[vv] != s){
    
99.                                 int u = parentPath[vv];
    
100.                                 residualGraph[u][vv] -=  min_capacity;
     
101.                                 residualGraph[vv][u] +=  min_capacity;
     
102.                                 vv = u;
     
103.                         }
     
104.                         //add path flow to overall flow
     
105.                         maxFlow += min_capacity;
     
106.                 }
     
107.                 //return overall flow/ Max Flow
     
108.                 return maxFlow;
     
109.     }
     
110.        
     
111.         public int[][] constructDirectedGraph(int[][] box){
     
112.                 //box.length is the number of box
     
113.                 //graph[i][j] means the capacity from i to j: could be used to check "if it has out-going arrow"
     
114.                 int[][] graph = new int[box.length][box.length];
     
115.                 //counterGraph[i][j] means the capacity from j to i: : could be used to check "if it has in-going arrow"
     
116.                 int[][] counterGraph = new int[box.length][box.length];
     
117.                 for(int i = 0; i < box.length; i++){
     
118.                         for(int j = 0; j < box.length; j++){
     
119.                                 //Then j is bigger than i, j=>i
     
120.                                 //no need to judge whether it should point to himself
     
121.                                 if(j == i){
     
122.                                         continue;
     
123.                                 }
     
124.                                 if(box[j][0] < box[i][0] && box[j][1] < box[i][1]){
     
125.                                         counterGraph[i][j] = 1;
     
126.                                 }
     
127.                                 if(box[j][0] > box[i][0] && box[j][1] > box[i][1]){
     
128.                                         graph[i][j] = 1;
     
129.                                 }
     
130.                         }
     
131.                 }
     
132.                 //add s and t: s: superGraph[box.length]  || t: superGraph[box.length + 1]
     
133.                 //superGraph[i][j] means the capacity from i to j
     
134.                 int[][] superGraph = new int[box.length + 2][box.length + 2];
     
135.                 for(int i = 0; i < box.length; i++){
     
136.                         boolean nothingEnter = true;//nothingEnter
     
137.                         boolean nothingOut = true;//nothingOut
     
138.                         for(int j = 0; j < box.length; j++){
     
139.                                 if(graph[i][j] > 0){
     
140.                                         nothingOut = false;//it could reach others, so it can not be t
     
141.                                 }
     
142.                                 if(counterGraph[i][j] > 0){
     
143.                                         nothingEnter = false;//it can be reached by others, so it can not be s
     
144.                                 }
     
145.                         }
     
146.                        
     
147.                         if(nothingEnter && nothingOut){
     
148.                                 superGraph[superGraph.length - 2][i] = 1;
     
149.                                 superGraph[i][superGraph.length - 1] = 1;
     
150.                                 continue;
     
151.                         }
     
152.                         //it should be connected by source "s"
     
153.                        
     
154.                         if(nothingEnter){
     
155.                                 superGraph[superGraph.length - 2][i] = 1;
     
156.                         }
     
157.                         //it should be connected by sink "t"
     
158.                         if(nothingOut){
     
159.                                 superGraph[i][superGraph.length - 1] = 1000000;
     
160.                         }
     
161.                        
     
162.                 }
     
163.                 //copy original graph/content(the graph without source "s" and sink "t")
     
164.                 //to superGraph(the graph with source "s" and sink "t"), return it
     
165.                 for(int i = 0; i < graph.length; i++){
     
166.                         for(int j = 0; j < graph.length; j++){
     
167.                                 superGraph[i][j] = graph[i][j];
     
168.                         }
     
169.                 }
     
170.                 return superGraph;
     
171.         }
     
172. }

复制代码

这道题 看不懂大家要去学一下最大流  里面涉及到 构造有向图，BFS，fordFulkerson 等  自学一下吧，我注释已经写得非常详细了

格格笑 发表于 2016-11-21 01:32
编译不过？这是不可能的……等我起床再check一下吧……

testcase 1/2。。。。。。

首先非常感谢楼主的分享， 但是{2,5},{3,3},{6,6},{7,8} testcase 楼主的代码给出的答案是3个 但是目测 可以 2个 所以感觉楼主代码有问题~

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

最近做了这道题，用greedy做可以优化到O(nlogn)