巨硬OTS面经

孤舟 发表于 2018-3-11 11:45
这种方法显然有bug,比如必须加当前油能到达的所有站的油才能到达目的地或者接下来的加油站，那么如果只记 ...

直接搜索吧

fernando 发表于 2018-3-13 11:01
greedy 貌似可以做？
我跟朋友讨论了下，用 BFS 做比较 稳妥？

多谢Lz 能说说bfs什么思路吗？ ：）

1. public static int findMinStop(int g, int d, int[][] gasStations) {
   
2.         if (g >= d) return 0;
   
3.         if (gasStations == null || gasStations.length == 0) return -1;
   
4.         for (int i = 0; i < gasStations.length; i++) {
   
5.             gasStations[i][0] = d - gasStations[i][0];
   
6.         }
   
7.         int[] maxReach = new int[gasStations.length + 1];
   
8.         maxReach[0] = g;
   
9.         Arrays.sort(gasStations, new Comparator<int[]>() {
   
10.             @Override
    
11.             public int compare(int[] o1, int[] o2) {
    
12.                 return o1[0] - o2[0];
    
13.             }
    
14.         });
    
15.         int res = 0;
    
16.         HashSet<Integer> visited = new HashSet<>();
    
17.         while (res < maxReach.length - 1 && maxReach[res] < d) {
    
18.             maxReach[res + 1] = maxReach[res] + findLargestWithOutRepeat(gasStations, visited, maxReach[res]);
    
19.             res++;
    
20.         }
    
21.         System.out.println(visited);
    
22.         return maxReach[res] < d ? -1 : res;
    
23.     }
    
24. 
    
25.     //O(N)
    
26.     private static int findLargestWithOutRepeat(int[][] gasStations, Set<Integer> visited, int maxDis) {
    
27.         int max = 0;
    
28.         int maxIndex = -1;
    
29.         for (int i = 0; i < gasStations.length; i++) {
    
30.             if (gasStations[i][0] > maxDis) {
    
31.                 break;
    
32.             }
    
33.             if (visited.contains(i)) continue;
    
34.             if (gasStations[i][1] > max) {
    
35.                 max = gasStations[i][1];
    
36.                 maxIndex = i;
    
37.             }
    
38.         }
    
39.         visited.add(maxIndex);
    
40.         return max;
    
41.     }
    
42. 
    
43.     public static void main(String[] args) {
    
44.         int[][] test =  {{24,10},{25, 1},{26,12}};
    
45.         System.out.println(findMinStop(10, 34, test));
    
46.     }

复制代码

草草写了一下 抛砖引玉 希望同学能贡献标答

LUOLUOLNSH 发表于 2018-3-25 08:02
多谢Lz 能说说bfs什么思路吗？ ：）

先对加油站排序，就是离起点越近的越靠前这样子。然后可以新建一个类，比如叫Node，里面有一些variables，比如 current 加油站，就是自己，然后还有一个 priority queue，里面存当前加油站能到达的 加油站，比如说像PriorityQueue<Node> 这样子。
然后就是一层层遍历，同时更新 stops 这个 varaible，一旦发现能到达 终点（可以把终点看作是特殊的加油站），然后就返回 stops 这个variable。
大概是这样。具体细节不太记得。我回头再想想 尽量回复你。

taoli0515 发表于 2018-3-29 13:12
草草写了一下 抛砖引玉 希望同学能贡献标答

虽然不知道题目本来是怎么样的，但是假如加油站在反方向，这个不用考虑目前位置的解法就不好用了。

g = 5, d = 20;
{{15,5},{10,5},{5,5},{30,100}};

fernando 发表于 2018-5-25 01:15
当时linkedin上找的我。我发联系方式发你了。你可以问问看。每个月都有一次 hiring event。注册方式，如 ...

谢谢楼主

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

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

pengsy89 发表于 2018-5-28 04:23
**** 本内容被作者隐藏 ****

前几天看九章，他们出了个贪心的解法。。。

pengsy89 发表于 2018-5-28 04:23
**** 本内容被作者隐藏 ****

嗯 这题后来九章出了个 贪心的解法

fernando 发表于 2018-5-28 16:02
嗯 这题后来九章出了个 贪心的解法

嗯嗯，看到了，that's useful.