📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
回复: 19
跳转到指定楼层
上一主题 下一主题
收起左侧

请教巫师这道题

全局:

2017(4-6月) 码农类General 硕士 全职@airbnb - 网上海投 - 技术电面  | | Other | 在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
There are 10 wizards, 0-9, you are given a list that each entry is a list of wi
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
ans-serif">请问这道店面题目有大神能给讲下么。。。。没太懂


上一篇:黑车公司, 全栈
下一篇:Affirm
全局:
写了下代码
  1. public class Wizard {

  2.     static class Num {
  3.         int dis;
  4.         int val;

  5.         public Num(int d, int v) {
  6.             this.dis = d;
  7.             this.val = v;
  8.         }
  9.     }

  10.     public static int getMinCost(List<List<Integer>> list) {
  11.         HashSet<Integer> visited = new HashSet<>();
  12.         PriorityQueue<Num> pq = new PriorityQueue<>(new Comparator<Num>() {
  13.             public int compare(Num n1, Num n2) {
  14.                 return n1.dis - n2.dis;
  15.             }
  16.         });

  17.         for (int i : list.get(0)) {
  18.             pq.add(new Num(i * i, i));
  19.         }
  20.         visited.add(0);
  21.         while (!pq.isEmpty()) {
  22.             Num num = pq.poll();
  23.             visited.add(num.val);
  24.             if (num.val == 9) {
  25.                 return num.dis;
  26.             }
  27.             for (int i : list.get(num.val)) {
  28.                 if (!visited.contains(i)) {
  29.                     pq.add(new Num(num.dis + (i - num.val) * (i - num.val), i));
  30.                 }
  31.             }
  32.         }

  33.         return Integer.MAX_VALUE;
  34.     }

  35.     public static void main(String[] args) {
  36.         List<List<Integer>> list = new ArrayList<>();
  37.         list.add(Arrays.asList(1, 4, 9));
  38.         list.add(Arrays.asList(2));
  39.         list.add(Arrays.asList(3));
  40.         list.add(Arrays.asList(2));
  41.         list.add(Arrays.asList(5));
  42.         list.add(Arrays.asList(6));
  43.         list.add(Arrays.asList(7));
  44.         list.add(Arrays.asList(8));
  45.         list.add(Arrays.asList(9));
  46.         System.out.println(getMinCost(list));
  47.     }
  48. }
复制代码

评分

参与人数 1大米 +3 收起 理由
四代目火影 + 3 Dijkstra的简明implementation吧?

查看全部评分

回复

使用道具 举报

全局:
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. }
复制代码

评分

参与人数 1大米 +5 收起 理由
鸽子 + 5 很有用的信息!

查看全部评分

回复

使用道具 举报

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

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

使用道具 举报

🔗
f1371342385 2017-4-29 13:22:31 | 只看该作者
全局:
这应该是一个在有向图里面找最短路径,dijkstra算法
回复

使用道具 举报

🔗
byrlhb 2017-4-30 03:58:50 | 只看该作者
全局:
抽象一下,典型的djstra问题
回复

使用道具 举报

🔗
f1371342385 2017-5-19 14:21:40 | 只看该作者
全局:
cartmanstart 发表于 2017-5-19 13:26
dijkstra对这道题有些浪费,因为这道题不用二次更新cost。
要是面试官要求比较高的话,要求你不许用Dijkst ...

求问 如果不允许用Dijkstra 那该用啥?难道用bfs?
回复

使用道具 举报

🔗
cartmanstart 2017-5-19 14:39:48 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
Starforge 2017-5-19 16:58:26 | 只看该作者
全局:
如果保证wizard认识关系双向的话,最优路径不会回头,一个简单dp就可以了,线性复杂度。
不保证的话,选一种最短路算法实现,顺手就行。 Dijkstra m*log(n).
楼上的bfs算法会退化,别的先不说,一个点在队列里出现两次是没有意义的。(补上了还是会退化。)
回复

使用道具 举报

🔗
f1371342385 2017-5-20 04:00:24 | 只看该作者
全局:

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

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

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表