请教巫师这道题

There are 10 wizards, 0-9, you are given a list that each entry is a list of wizards known by wizard. Define the cost between wizards and wizard

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

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

ans-serif">请问这道店面题目有大神能给讲下么。。。。没太懂

写了下代码

1. public class Wizard {
   
2. 
   
3.     static class Num {
   
4.         int dis;
   
5.         int val;
   
6. 
   
7.         public Num(int d, int v) {
   
8.             this.dis = d;
   
9.             this.val = v;
   
10.         }
    
11.     }
    
12. 
    
13.     public static int getMinCost(List<List<Integer>> list) {
    
14.         HashSet<Integer> visited = new HashSet<>();
    
15.         PriorityQueue<Num> pq = new PriorityQueue<>(new Comparator<Num>() {
    
16.             public int compare(Num n1, Num n2) {
    
17.                 return n1.dis - n2.dis;
    
18.             }
    
19.         });
    
20. 
    
21.         for (int i : list.get(0)) {
    
22.             pq.add(new Num(i * i, i));
    
23.         }
    
24.         visited.add(0);
    
25.         while (!pq.isEmpty()) {
    
26.             Num num = pq.poll();
    
27.             visited.add(num.val);
    
28.             if (num.val == 9) {
    
29.                 return num.dis;
    
30.             }
    
31.             for (int i : list.get(num.val)) {
    
32.                 if (!visited.contains(i)) {
    
33.                     pq.add(new Num(num.dis + (i - num.val) * (i - num.val), i));
    
34.                 }
    
35.             }
    
36.         }
    
37. 
    
38.         return Integer.MAX_VALUE;
    
39.     }
    
40. 
    
41.     public static void main(String[] args) {
    
42.         List<List<Integer>> list = new ArrayList<>();
    
43.         list.add(Arrays.asList(1, 4, 9));
    
44.         list.add(Arrays.asList(2));
    
45.         list.add(Arrays.asList(3));
    
46.         list.add(Arrays.asList(2));
    
47.         list.add(Arrays.asList(5));
    
48.         list.add(Arrays.asList(6));
    
49.         list.add(Arrays.asList(7));
    
50.         list.add(Arrays.asList(8));
    
51.         list.add(Arrays.asList(9));
    
52.         System.out.println(getMinCost(list));
    
53.     }
    
54. }
    

复制代码

BFS代码

1. public class Solution {
   
2.     public class Wizard{
   
3.         int idx, dis;
   
4.         public Wizard(int idx, int dis){this.idx = idx;this.dis = dis;}
   
5.     }
   
6.     public int cost(List<List<Integer>> costList){
   
7.         int n = costList.size();
   
8.         Wizard[] wizards = new Wizard[n];
   
9.         for(int i=0;i<n;i++)
   
10.             wizards[i] = new Wizard(i,i==0?0:Integer.MAX_VALUE);
    
11.         Queue<Wizard> queue = new LinkedList<>();
    
12.         queue.offer(wizards[0]);
    
13.         while(!queue.isEmpty()){
    
14.             Wizard w = queue.poll();
    
15.             for(int i: costList.get(w.idx)){
    
16.                 int newDis = w.dis + (w.idx-i)*(w.idx-i);
    
17.                 if(wizards[i].dis>newDis){
    
18.                     wizards[i].dis = newDis;
    
19.                     queue.offer(wizards[i]);
    
20.                 }
    
21.             }
    
22.         }
    
23.         return wizards[n-1].dis;
    
24.     }
    
25. }

复制代码

dijkstra对这道题有些浪费，因为这道题不用二次更新cost。
要是面试官要求比较高的话，要求你不许用Dijkstra，不许用heap，也是可以做的。

补充内容 (2017-5-19 13:28):
或者换一种问法，时间复杂度要线性，不能E(logV)或者E+V^2

这应该是一个在有向图里面找最短路径，dijkstra算法

抽象一下，典型的djstra问题

cartmanstart 发表于 2017-5-19 13:26
dijkstra对这道题有些浪费，因为这道题不用二次更新cost。
要是面试官要求比较高的话，要求你不许用Dijkst ...

求问 如果不允许用Dijkstra 那该用啥？难道用bfs？

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

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

如果保证wizard认识关系双向的话，最优路径不会回头，一个简单dp就可以了，线性复杂度。
不保证的话，选一种最短路算法实现，顺手就行。 Dijkstra m*log(n).
楼上的bfs算法会退化，别的先不说，一个点在队列里出现两次是没有意义的。（补上了还是会退化。）

cartmanstart 发表于 2017-5-19 15:25
BFS代码

这种有向图的最短路径还是dj算法好点把，但是这一题的确不需要二次更新的

补充内容 (2017-5-20 04:01):
不一定把 比如1想认识9 那么可以通过4 或者 5 认识，中间的值还是不一样把