狗去onsite

woderegou 发表于 2018-4-30 04:42
看了你这个例子我就知道我的行不通了，然后我觉得你这个好像也不行，比如这个例子：
00000000
11100110 ...

我昨天后来想了一下，应该是分别从起点和终点出发，找沿着路线的厚度为1的墙，然后挨个去掉试试。
感觉就是贪心算法。想不到有其他规律

感谢楼主分享，对第四题有点疑问： 那么第四题的输入变量是什么？ 这里给的file path 是做什么？ 是有api能取出file content吗？ 那么这个题是不是先处理file content，读出user id 以及他发言的次数，然后做top K？ 这题有对file的更详细的说明吗？ 还有第一题，那个第二问是跟第一问的平均值没有什么关系对吗？

第三题followup应该是dijkstra的思路吧？
heap里push进{i,j,steps,walls}.
bfs过程中每次只push进 走到下一个点number of break walls <= 1的点，
最后poll出来的点能到destination就直接返回那个step

1. public static int shortest(int[][] M, int[] start, int[] end){
   
2.                 int m = M.length;
   
3.                 int n = M[0].length;
   
4.                 Integer[][] dist = new Integer[m][n];
   
5.                 PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> (a[2] - b[2]));
   
6.                 heap.offer(new int[]{start[0], start[1], 0, 0});
   
7.                 int[][] dirs = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
   
8.                 while(!heap.isEmpty()){
   
9.                         int[] cur = heap.poll();
   
10.                         int i = cur[0];
    
11.                         int j = cur[1];
    
12.                         int steps = cur[2];
    
13.                         int walls = cur[3];
    
14.                         dist[i][j] = steps;
    
15.                         if(i == end[0] && j == end[1]){
    
16.                                 return steps;
    
17.                         }
    
18.                         for(int[] dir : dirs){
    
19.                                 int ni = i + dir[0];
    
20.                                 int nj = j + dir[1];
    
21.                                 if(ni >= 0 && ni < m && nj >= 0 && nj < n && dist[ni][nj] == null && (walls + M[ni][nj] <= 1)){
    
22.                                         int nwalls = walls + M[ni][nj];
    
23.                                         heap.offer(new int[]{ni, nj, steps + 1, nwalls});
    
24.                                 }
    
25.                         }
    
26.                 }
    
27.                 return -1;
    
28.         }

复制代码

是的 但是要解释清楚用PQ的time complexity

我觉得Dijkstra很对啊！