谷歌Foobar的挑战3 - 找到接入代码

Question

找到接入代码

写一个函数答案（L），其采用的正整数●一个列表和计算的（LST“幸运三元组”的数量[I] ，lst [j]，lst [k]）其中i < j < k。 l的长度在2和2000之间（含）。 l的元素在1和999999之间（包括1和999999）。答案符合一个有符号的32位整数。有些列表是故意生成的，没有任何访问代码来诋毁间谍，所以如果找不到三元组，则返回0.

例如，[1,2,3,4,5,6]具有三元组： [1,2,4]，[1,2,6]，[1,3,6]，总共得出答案3。

测试用例

输入： （INT表）L = [1，1,1] 输出： （INT）1个

输入： （INT表）L = [1， 2，3，4，5，6] 输出： （INT）3

我尝试

from itertools import combinations 

def answer(l): 
    if len(l) < 3: 
     return 0 
    found = 0 
    for val in combinations(l,3): 
     # Ordering Check 
     if (val[0] <= val[1] <= val[2]) != True: 
      continue 
     # Answer Size Check against size of signed integer 32 bit 
     if int(val[0].__str__() + val[1].__str__() + val[2].__str__()) > 2147483647: 
      continue 
     # Division Check 
     if (val[1] % val[1] != 0) or (val[2] % val[1] != 0): 
      continue 
     # Increment 'found' variable by one 
     found += 1 
    return found 

Answer 1

这是一个解决方案，我的头顶部有O（n^2）时间和O（n）空间复杂度。我认为有一个更好的解决方案（可能使用动态编程），但是这种方法不能生成所有组合。

public static int foobar(int[] arr) 
{ 
    int noOfCombinations = 0; 
    int[] noOfDoubles = new int[arr.length]; 

    // Count lucky doubles for each item in the array, except the first and last items 
    for(int i = 1; i < arr.length-1; ++i) 
    { 
     for(int j = 0; j < i; ++j) 
     { 
      if(arr[i] % arr[j] == 0) 
       ++noOfDoubles[i]; 
     } 
    } 

    // Count lucky triples 
    for(int i = 2; i < arr.length; i++) 
    { 
     for(int j = 1; j < i; ++j) 
     { 
      if(arr[i] % arr[j] == 0) 
       noOfCombinations += noOfDoubles[j]; 
     } 
    } 

    return noOfCombinations; 
} 

Answer 2

事情是：你让图书馆的方法组合为你做所有的“真正的”工作。

当然：通常这就是要走的路。你做不是想要重新发明轮子时，有一个现有的库函数，给你你所需要的。您目前的代码非常简洁，并且很好阅读（除非您应该打电话给您的列表，以及“列表”，但不是“l”）。

但是这种情况是不同的：显然，这个程序的大部分执行时间都会在这个调用中发生。似乎谷歌认为无论这个电话正在做什么..可以做得更快。

所以，你的答案是：你实际上想重新发明轮子，通过重写你的代码的方式是更好比它现在正在做的！第一个出发点可能是查看组合的源代码，以了解该调用是否正在做您在上下文中不需要的事情。

猜测：该呼叫创建很多是不理想的排列。全部是浪费了时间。你想退一步考虑如何从你的输入建立那些幸运的三倍而不是创造一吨不那么幸运的三倍！

Answer 3

我试着在python中实现它。它通过测试的速度不够快，但运行速度比uoyilmaz的解决方案移植到python快50倍。造成这种情况的代码如下：

#!/usr/bin/env python2.7 

from bisect import insort_left 
from itertools import combinations 


def answer_1(l): 
    """My own solution.""" 
    indices = {} 
    setdefault_ = indices.setdefault 
    for i, x in enumerate(l): 
     setdefault_(x, []).append(i) 

    out = 0 
    highest_value = max(l) 
    for i, x in enumerate(l): 
     multiples = [] 
     for m in xrange(1, int(highest_value/x) + 1): 
      if x * m in indices: 
       for j in indices[x * m]: 
        if i < j: 
         insort_left(multiples, (j, x * m)) 

     if multiples: 
      multiples = [m[1] for m in multiples] 
      for pair in combinations(multiples, 2): 
       out += pair[1] % pair[0] == 0 

    return out 


def answer_2(l): 
    """@uoyilmaz's solution ported from Java.""" 
    out = 0 
    pair_counts = [0] * len(l) 
    for i in xrange(1, len(l) - 1): 
     for j in xrange(i): 
      if l[i] % l[j] == 0: 
       pair_counts[i] += 1 

    for i in xrange(2, len(l)): 
     for j in xrange(1, i): 
      if l[i] % l[j] == 0: 
       out += pair_counts[j] 

    return out 


answer = answer_1 

# ----------------------------------------------------------------------------- 

_SEED = 1.23 


def benchmark(sample_count): 
    from random import seed, randint 
    import timeit 
    clock = timeit.default_timer 

    seed(_SEED) 
    samples = [[randint(1, 999999) for _ in xrange(randint(2, 2000))] 
       for _ in xrange(sample_count)] 

    start = clock() 
    for sample in samples: 
     answer(sample) 

    end = clock() 
    print("%.4f s elapsed for %d samples." % (end - start, sample_count)) 


def test(): 
    # Provided test cases. 
    assert(answer([1, 1, 1]) == 1) 
    assert(answer([1, 2, 3, 4, 5, 6]) == 3) 

    # Custom test cases. 
    assert(answer([1]) == 0) 
    assert(answer([1, 2]) == 0) 
    assert(answer([2, 4]) == 0) 
    assert(answer([1, 1, 1, 1]) == 4) 
    assert(answer([1, 1, 1, 1, 1]) == 10) 
    assert(answer([1, 1, 1, 1, 1, 1]) == 20) 
    assert(answer([1, 1, 1, 1, 1, 1, 1]) == 35) 
    assert(answer([1, 1, 2]) == 1) 
    assert(answer([1, 1, 2, 2]) == 4) 
    assert(answer([1, 1, 2, 2, 2]) == 10) 
    assert(answer([1, 1, 2, 2, 2, 3]) == 11) 
    assert(answer([1, 2, 4, 8, 16]) == 10) 
    assert(answer([2, 4, 5, 9, 12, 34, 45]) == 1) 
    assert(answer([2, 2, 2, 2, 4, 4, 5, 6, 8, 8, 8]) == 90) 
    assert(answer([2, 4, 8]) == 1) 
    assert(answer([2, 4, 8, 16]) == 4) 
    assert(answer([3, 4, 2, 7]) == 0) 
    assert(answer([6, 5, 4, 3, 2, 1]) == 0) 
    assert(answer([4, 7, 14]) == 0) 
    assert(answer([4, 21, 7, 14, 8, 56, 56, 42]) == 9) 
    assert(answer([4, 21, 7, 14, 56, 8, 56, 4, 42]) == 7) 
    assert(answer([4, 7, 14, 8, 21, 56, 42]) == 4) 
    assert(answer([4, 8, 4, 16]) == 2) 


def main(): 
    test() 
    benchmark(100) 


if __name__ == '__main__': 
    main() 

现在，如果任何人有关于如何进一步加快这一个想法，我很开放的建议。

Answer 4

我其实只是收到foo.bar这个问题，所以我会更深入地了解我的O(n^2)解决方案。

我选择输入模型为有向图，其中图中的每个node是索引i到输入阵列和从u到v存在如果u可以通过v分割的边缘。

一旦我建立了有向图，它是一个在所有出边从每个邻居每个节点总结的问题。正确性在于，当存在长度为3的在构建的图形的路径的存在triplet的事实。

Node -> Neighbor -> # of ougoing edges = # of triplets starting from Node

注：我使用的输入数组的指数图节点的值，但在这里输入数组值也就够了，因为我们只是计数的边缘。

public static int answer(int[] l) { 
    if (l.length < 3) { 
     return 0; 
    } 

    Map<Integer, Set<Integer>> graph = new HashMap<>(); 
    graph.put(0, Collections.emptySet()); 

    for (int i = 1; i < l.length; i++) { 
     graph.put(i, new HashSet<>()); 
     for (int j = 0; j < i; j++) { 
      if (l[i] % l[j] == 0) { 
       graph.get(i).add(j); 
      } 
     } 
    } 

    int count = 0; 
    for (int node : graph.keySet()) { 
     for (int neighbor : graph.get(node)) { 
      count += graph.get(neighbor).size(); 
     } 
    } 

    return count; 
}