谷歌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; 
}