谷歌onsite

fropen 发表于 2018-8-23 10:59
第三轮，不搜索，怎么做？输入是  int[][] grid, int[][] querys？

输入是List<Flower> flowers, int[] query (一次一个query)
不搜索的话直接对每个花花可以算出它在query点的芳香值啊

流星无痕 发表于 2018-8-23 12:34
对 就是这么平凡的设定哈哈哈

如果走直线，不就是判读一下  1）终点是否在这条线上；2）线的中间有没有其它车挡住？

第一题是sliding puzzle, 利口上的题吧

edu 发表于 2018-8-23 13:24
如果走直线，不就是判读一下  1）终点是否在这条线上；2）线的中间有没有其它车挡住？

其他的车也可以走的！

流星无痕 发表于 2018-8-23 12:36
输入是List flowers, int[] query (一次一个query)
不搜索的话直接对每个花花可以算出它在query点的芳香 ...

这个题，我的想法是 1）对花花按芳香值从大到小排序；2）（按从大到小的顺序）计算花花在每个grid的芳香值；3）计算grid芳香值是以每个花为中心，向外BFS，一旦发现grid已有芳香值已经大于这朵搜索花在这个grid的芳香值，就停止搜索。

wuyifu00 发表于 2018-8-23 13:47
第一题是sliding puzzle, 利口上的题吧

差不多，只不过汽车比起puzzle是有长度的，原理一样 都是建图用搜索来做。还有就是最后的状态只要判断给定的车车在那里就行了

edu 发表于 2018-8-23 13:51
这个题，我的想法是 1）对花花按芳香值从大到小排序；2）（按从大到小的顺序）计算花花在每个grid的芳香 ...

不用搜索啊。直接使用公式Math.max(0, S - R * (Math.abs(xf - xq) + Math.abs(yf - yq))) 就好了 其中S是这朵花的原始香气，R是减弱速率，Math.abs(xf - xq) + Math.abs(yf - yq)这是曼哈顿距离。对于每朵花更新整个board每次取max就好了！Ta-da!

流星无痕 发表于 2018-8-23 14:04
不用搜索啊。直接使用公式Math.max(0, S - R * (Math.abs(xf - xq) + Math.abs(yf - yq))) 就好了 其中S ...

这样做的时间复杂度是：O(花的数量 * 网格数量）。但从花出发的搜索算法，时间复杂度要小于这个，因为对于每朵花，不用搜索全部网格。我认为。

感谢楼主分享，楼主几年经验呢，没有design题？

请问楼主在哪个site面的？