Facebook Menlo Part University Day

求问第四题如何better than O(N^2) ?

同问怎么做better than O(N^2) ? 是要把所有的integer建Trie，然后再比较吗？ 这样应该会better than(n^2) ..

xpli521 发表于 2016-10-28 07:59
同问怎么做better than O(N^2) ? 是要把所有的integer建Trie，然后再比较吗？ 这样应该会better than(n^2)  ...

hamming distance就是l1-norm，按位做，然后把64位distance加起来就行了

楼主是在职跳槽吗，要manager的ref，我刚工作一年，只有现在的manager。。。无法弄啊

spiritrhy 发表于 2016-10-28 13:58
楼主是在职跳槽吗，要manager的ref，我刚工作一年，只有现在的manager。。。无法弄啊

我是new grad。。给的是以前实习的manager。

alfredaria 发表于 2016-10-28 07:23
我当时问能否改原来的matrix，答曰可以，所以就不需要额外空间了吧。我的做法是用两个ArrayList队列维护 ...

谢谢lz 字数子数组

xpli521 发表于 2016-10-28 07:59
同问怎么做better than O(N^2) ? 是要把所有的integer建Trie，然后再比较吗？ 这样应该会better than(n^2)  ...

每位０的个数和１的个数相乘　求和
public static int hammingDistanceSum(int[] nums, int k) {
          int len = nums.length;
                int[] countOfOnes = new int[32];//统计每位的1的个数总和
                for (int i = 0; i < len; i++) {
                        for (int j = 0; j < 32; j++) {
                                countOfOnes[j] += (nums[i] >> j) & 1;//64大小的话，这里会挪过了
                        }
                }
                int sum = 0;
                for (int count: countOfOnes) {
                        sum += count * (len - count);//0的个数 X 1的个数
                }
                return sum;
    }  

alfredaria 发表于 2016-10-28 07:23
我当时问能否改原来的matrix，答曰可以，所以就不需要额外空间了吧。我的做法是用两个ArrayList队列维护 ...

求教楼主一个情况呀
O X O O
O X O O
K X K O
像这个情况的话 应该输出哪些点最远呢？ 因为被分成两个部分 （0， 0）点对于（2， 2）的knight距离是无限远。楼主的算法好像对于这个情况会输出 （0， 0） （0，2）（0，3）？

jfree811 发表于 2016-10-29 08:04
求教楼主一个情况呀
O X O O
O X O O

应该是输出(0, 3)吧，我觉得是输出到任意一个knight的最短距离最大的点

pawprinter 发表于 2016-10-29 08:31
应该是输出(0, 3)吧，我觉得是输出到任意一个knight的最短距离最大的点

这道题应该是LC叁药企 应该是所有的Knight