狗家昂赛

OaPhoneOnsite 发表于 2017-1-27 12:02
user吧？

是每个时间点都从新统计一遍？

请问lz 第五题是怎么做的，我记得之前有人在地里发过这个题，不知道有哪位大神还有链接吗？lz能详细解释一下是怎么做的吗？谢谢啦

bigbearlake 发表于 2017-2-17 16:17
是每个时间点都从新统计一遍？

每个时间点往前24小时之内的

wangbd 发表于 2017-2-19 12:03
请问lz 第五题是怎么做的，我记得之前有人在地里发过这个题，不知道有哪位大神还有链接吗？lz能详细解释一 ...

我用的是类似Insert Interval的思路，感觉不是最优解

请问楼主第一个是把矩阵里面的1改成到0的最短距离吗？

第一题follow up是不是所有的0一起做BFS？

1. 
   
2. from collections import deque
   
3. class Solution(object):
   
4.     # Do BFS for all one's
   
5.     def minDist(self, matrix):
   
6.         def bfs(i, j, matrix):
   
7.             directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
   
8.             queue = deque([(i, j, 0)])
   
9.             visited = set()
   
10.             while queue:
    
11.                 pi, pj, depth = queue.popleft()
    
12.                 for di, dj in directions:
    
13.                     ni, nj = pi + di, pj + dj
    
14.                     if 0 <= ni < len(matrix) and 0 <= nj < len(matrix[0]) and (ni, nj) not in visited:
    
15.                         visited |= {(ni, nj)}
    
16.                         if matrix[ni][nj] == 0:
    
17.                             matrix[i][j] = depth + 1
    
18.                             return
    
19.                         queue.append((ni, nj, depth + 1))
    
20. 
    
21.         for i in range(len(matrix)):
    
22.             for j in range(len(matrix[0])):
    
23.                 if matrix[i][j] == 1:
    
24.                     bfs(i, j, matrix)
    
25.         return matrix
    
26. 
    
27.     def minDistFollowUp(self, matrix):
    
28.         queue = deque([])
    
29.         directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
30.         for i in range(len(matrix)):
    
31.             for j in range(len(matrix[0])):
    
32.                 if matrix[i][j] == 1:
    
33.                     matrix[i][j] = -1
    
34. 
    
35.         for i in range(len(matrix)):
    
36.             for j in range(len(matrix[0])):
    
37.                 if matrix[i][j] == 0:
    
38.                     queue.append((i, j))
    
39. 
    
40.         while queue:
    
41.             i, j = queue.popleft()
    
42.             for di, dj in directions:
    
43.                 ni, nj = i + di, j + dj
    
44.                 if 0 <= ni < len(matrix) and 0 <= nj < len(matrix[0]) and matrix[ni][nj] == -1:
    
45.                     matrix[ni][nj] = matrix[i][j] + 1
    
46.                     queue.append((ni, nj))
    
47.         return matrix
    
48. 
    
49. solver = Solution()
    
50. m = [[0,1,0,0,1], [1,1,1,0,0], [1,1,0,0,1],[0,0,1,0,1]]
    
51. print m
    
52. print solver.minDist(m)
    
53. print solver.minDistFollowUp(m)
    

复制代码

jedihy 发表于 2017-2-22 03:17
请问楼主第一个是把矩阵里面的1改成到0的最短距离吗？

这个应该可以和面试官商量，google的习惯一般是不改变输入

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

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

第三题应该可以用找skyline类似的方法解。先对所有投票按时间排序，然后用24小时的区间（实际上就是两根时间线，skyline只需要一根线来扫描）来扫描投票，记录下投票数最大值变化的时间（最后形成一个按时间排序的数组，每个元素两个成员 <time, ID>）. 给定时间查投票最高的ID就是在这个数组上做binay search。

2.2 是leetcode哪一题啊？ 记得做过，想不起来了。