Pocket Gems OA

https://www.1point3acres.com/bbs/forum.php?mod=attachment&aid=Mjc5OTkzfDQ1N2QwOTNjMTY1OTJjZGFmODRjODBhY2M4MmQwODJlfD

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

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

on find。但是就是有一个test case过不了，请大神帮看看bug出在哪里了。

1. public static int maxDifference(int[] a, int[] b, int nodes) {
   
2.    Map<Integer, List<Integer>> map = new HashMap<>();
   
3.    int result = Integer.MIN_VALUE;
   
4.    int[] father = new int[nodes + 1];
   
5.    for (int i = 0; i < father.length; i++) {
   
6.       father[i] = i;
   
7.    }
   
8.    for (int i = 0; i < a.length; i++) {
   
9.       union(a[i], b[i], father);
   
10.    }
    
11.    for (int i = 1; i < father.length; i++) {
    
12.       result = Math.max(result, i - father[i]);
    
13.    }
    
14.    return result;
    
15.    }
    
16.    
    
17.    public static int find(int x, int[] father) {
    
18.    if (father[x] == x) {
    
19.       return x;
    
20.    }
    
21.    father[x] = find(father[x], father);
    
22.    return father[x];
    
23.    }
    
24.    
    
25.    public static void union(int a, int b, int[] father) {
    
26.    int root_a = find(a, father);
    
27.    int root_b = find(b, father);
    
28.    if (root_a != root_b) {
    
29.       if (root_a >= root_b) {
    
30.          father[root_a] = root_b;
    
31.       } else {
    
32.          father[root_b] = root_a;
    
33.       }
    
34.    }
    
35.    }

复制代码

原贴题没有上传正确。题来了！

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

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

请问楼主是challenge 4 嘛？

vilatto 发表于 2017-9-22 04:28
请问楼主是challenge 4 嘛？

challenge 3

基本思路没问题，只有一个点的时候输出是Integer.MIN_VALUE;
有可能是这里的问题

补充内容 (2017-9-22 08:21):
两种方法改进 1）result 初始为0，2）11行代码从0开始查

windmsvy 发表于 2017-9-22 08:20
基本思路没问题，只有一个点的时候输出是Integer.MIN_VALUE;
有可能是这里的问题

感谢提供参考！

感觉从0开始不对吧？因为0在father里面是个dummy node。。

vilatto 发表于 2017-9-22 04:28
请问楼主是challenge 4 嘛？

我是challenge 4.不同的代号是什么关系啊？

楼主您好！谢谢你的分享。
OA需要自己写stdin 和 stdout吗？还是像leetcode一样？

太阳与石 发表于 2017-9-25 05:29
楼主您好！谢谢你的分享。
OA需要自己写stdin 和 stdout吗？还是像leetcode一样？

不需要的，接口写好了的