Google新加坡OA 2020题目汇总

希望楼主继续更新，另外那个分享题目的电报群加不进去。楼主贴的移动的那道题，用最短路径就可以解决了，没太看懂你后面update的方法。我个人喜欢用SPFA算法解决。LC类似题目药散刘罢可以参考。

请问第二题你是如何解决的呢？

yixxxfan 发表于 2020-10-24 15:13
请问第二题你是如何解决的呢？

类似01BFS，可以搜索一下

xiana406 发表于 2020-10-22 19:53
希望楼主继续更新，另外那个分享题目的电报群加不进去。楼主贴的移动的那道题，用最短路径就可以解决了，没 ...

什么电报群？哈哈哈
谢谢分享哈！

DOUMK 发表于 2020-10-24 15:17
什么电报群？哈哈哈
谢谢分享哈！

lc discussion区你搜索singapore评论有一个电报连接。

第二题：priority queue 加 bfs就可以解决了吧。

Hackerearth 还得自己写input output，非常麻烦。

1.     def minCost(grid):
   
2.         m, n = len(grid), len(grid[0])
   
3.         heap = [(0, (0, 0))]
   
4.         visited = set()
   
5.         while heap:
   
6.             cost, (x, y) = heapq.heappop(heap)
   
7.             if x == m - 1 and y == n - 1:
   
8.                 return cost
   
9.             if (x, y) in visited:
   
10.                 continue
    
11.             visited.add((x, y))
    
12.             for idx, i, j in [('R', x, y + 1), ('L', x, y - 1), ('U', x + 1, y), ('D', x - 1, y)]:
    
13.                 if 0 <= i < m and 0 <= j < n and (i, j) not in visited:
    
14.                     heapq.heappush(heap, (cost + (grid[x][y] != idx), (i, j)))

复制代码

min cost的代码