了解三元组计数 HackerRank

Question

我一直在研究这个挑战：Count Triplets，经过大量的努力，我的算法并没有适用于每个测试用例。

由于在讨论中，我看到了一段代码并试图找出代码的真正功能，但我仍然无法理解这段代码是如何工作的。

解决方案：

from collections import defaultdict

arr = [1,3,9,9,27,81]
r = 3
v2 = defaultdict(int)
v3 = defaultdict(int)
count = 0
for k in arr:
    count += v3[k]
    v3[k*r] += v2[k]
    v2[k*r] += 1
print(count)

上面的代码完美地适用于每个测试用例。我已经测试的值k，v2，v3理解，但还是不知道如何代码工作，以便与计数三胞胎顺利。我也无法在梦中想到那个解决方案。我想知道人们如何如此聪明地制定出这个解决方案。尽管如此，如果我能得到正确的解释，我会很高兴。谢谢

k,v2,v3 的输出

from collections import defaultdict

arr = [1,3,9,9,27,81]
r = 3
v2 = defaultdict(int)
v3 = defaultdict(int)
count = 0
for k in arr:
    count += v3[k]
    v3[k*r] += v2[k]
    v2[k*r] += 1
    print(k, count, v2, v3)

输出

1 0 defaultdict(<class 'int'>, {1: 0, 3: 1}) defaultdict(<class 'int'>, {1: 0, 3: 0})                                                  
3 0 defaultdict(<class 'int'>, {1: 0, 3: 1, 9: 1}) defaultdict(<class 'int'>, {1: 0, 3: 0, 9: 1})                                      
9 1 defaultdict(<class 'int'>, {27: 1, 1: 0, 3: 1, 9: 1}) defaultdict(<class 'int'>, {27: 1, 1: 0, 3: 0, 9: 1})                        
9 2 defaultdict(<class 'int'>, {27: 2, 1: 0, 3: 1, 9: 1}) defaultdict(<class 'int'>, {27: 2, 1: 0, 3: 0, 9: 1})                        
27 4 defaultdict(<class 'int'>, {27: 2, 1: 0, 3: 1, 81: 1, 9: 1}) defaultdict(<class 'int'>, {27: 2, 1: 0, 3: 0, 81: 2, 9: 1})         
81 6 defaultdict(<class 'int'>, {1: 0, 3: 1, 243: 1, 81: 1, 9: 1, 27: 2}) defaultdict(<class 'int'>, {1: 0, 3: 0, 243: 1, 81: 2, 9: 1, 
27: 2})

Answer 1

1.问题

该函数有两个参数，即：

• arr：整数数组
• r：整数，公比

所以，输入可以是这样的

arr: [1, 2, 2, 4]
r: 2

目标是返回形成几何级数的三元组的计数。

2、如何解决

要解决它有多种方法。例如，来自SagunB根据RobertsN 的评论

• 可以在 O(n) -> 单次传递数据中完成
• 不需要除法，只需要 R 的单次乘法
• 使用map(C++)或dict(Java,Python)是必须的->可以是无序映射(节省O(logN))
• 当读取一个值时尝试向前思考 -> 这个值稍后会形成三元组的一部分吗？
• 无需将 (R == 1) 视为极端情况

from collections import Counter

# Complete the countTriplets function below.
def countTriplets(arr, r):
    r2 = Counter()
    r3 = Counter()
    count = 0
    
    for v in arr:
        if v in r3:
            count += r3[v]
        
        if v in r2:
            r3[v*r] += r2[v]
        
        r2[v*r] += 1

    return count

或者像你说的

from collections import defaultdict

# Complete the countTriplets function below.
def countTriplets(arr, r):
    v2 = defaultdict(int)
    v3 = defaultdict(int)
    count = 0
    for k in arr:
        count += v3[k]
        v3[k*r] += v2[k]
        v2[k*r] += 1
    return count

3. 最终结果

这两个案例都将通过HackerRank目前所有的 13 个测试案例

4. 案件说明

RobertsN 的评论几乎解释了您的代码（与您的代码非常相似）。不过，为了更好地理解代码的工作原理，只需打印 count、v2 和 v3 发生的情况即可。

假设你有作为输入

4 2
1 2 2 4

预期输出是

2

另外，我们知道根据定义，v2 和 v3 看起来都像

defaultdict(<class 'int'>, {})

这使得 for 循环有待理解。运算符 += 可能会引起一些混乱，但我已经在另一个答案中解决了这个问题。

所以，现在要了解其余部分，我们可以将循环更改为

for k in arr:
    print(f"Looping...")
    print(f"k: {k}")
    print(f"v3_before_count: {v3}")
    count += v3[k]
    print(f"count: {count}")
    print(f"k*r: {k*r}")
    print(f"v3_before: {v3}")
    v3[k*r] += v2[k]
    print(f"v3[k*r]: {v3[k*r]}")
    print(f"v2[k]: {v2[k]}")
    print(f"v3_after: {v3}")
    print(f"v2_before: {v2}")
    v2[k*r] += 1
    print(f"v2_after: {v2}")
    print(f"v2[k*r]: {v2[k*r]}")

会让你看到

Looping...
k: 1
v3_before_count: defaultdict(<class 'int'>, {})
count: 0
k*r: 2
v3_before: defaultdict(<class 'int'>, {1: 0})
v2_before_v3: defaultdict(<class 'int'>, {1: 0})
v3[k*r]: 0
v2[k]: 0
v3_after: defaultdict(<class 'int'>, {1: 0, 2: 0})
v2_before: defaultdict(<class 'int'>, {1: 0})
v2_after: defaultdict(<class 'int'>, {1: 0, 2: 1})
v2[k*r]: 1
Looping...
k: 2
v3_before_count: defaultdict(<class 'int'>, {1: 0, 2: 0})
count: 0
k*r: 4
v3_before: defaultdict(<class 'int'>, {1: 0, 2: 0})
v2_before_v3: defaultdict(<class 'int'>, {1: 0, 2: 0})
v3[k*r]: 1
v2[k]: 1
v3_after: defaultdict(<class 'int'>, {1: 0, 2: 0, 4: 1})
v2_before: defaultdict(<class 'int'>, {1: 0, 2: 1})
v2_after: defaultdict(<class 'int'>, {1: 0, 2: 1, 4: 1})
v2[k*r]: 1
Looping...
k: 2
v3_before_count: defaultdict(<class 'int'>, {1: 0, 2: 0, 4: 1})
count: 0
k*r: 4
v3_before: defaultdict(<class 'int'>, {1: 0, 2: 0, 4: 1})
v2_before_v3: defaultdict(<class 'int'>, {1: 0, 2: 0, 4: 1})
v3[k*r]: 2
v2[k]: 1
v3_after: defaultdict(<class 'int'>, {1: 0, 2: 0, 4: 2})
v2_before: defaultdict(<class 'int'>, {1: 0, 2: 1, 4: 1})
v2_after: defaultdict(<class 'int'>, {1: 0, 2: 1, 4: 2})
v2[k*r]: 2
Looping...
k: 4
v3_before_count: defaultdict(<class 'int'>, {1: 0, 2: 0, 4: 2})
count: 2
k*r: 8
v3_before: defaultdict(<class 'int'>, {1: 0, 2: 0, 4: 2})
v2_before_v3: defaultdict(<class 'int'>, {1: 0, 2: 0, 4: 2})
v3[k*r]: 2
v2[k]: 2
v3_after: defaultdict(<class 'int'>, {1: 0, 2: 0, 4: 2, 8: 2})
v2_before: defaultdict(<class 'int'>, {1: 0, 2: 1, 4: 2})
v2_after: defaultdict(<class 'int'>, {1: 0, 2: 1, 4: 2, 8: 1})
v2[k*r]: 1

并提取所需的插图。从中我们可以观察到什么？

• count 在最后一个循环中从 0 增加到 2。
• k 遍历 arr 的所有值 - 所以它将是 1、2、2 和 4。
• 在初始循环中，v3_before_count 为 {}，v3_before 为 {1:0}
• ETC。

这个过程很可能会产生问题，回答这些问题会让你更容易理解它。

Answer 2

因此，代码在遍历数组时会跟踪潜在的对和三元组。

For each value in the array:
    // Increment count by the number of triplets that end with k
    count += v3[k]
    // Increment the number of potential triplets that will end with k*r
    v3[k*r] += v2[k]
    // Increment the number of potential pairs that end with k*r
    v2[k*r] += 1  

任何给定 k 的三元组数量是我们迄今为止遇到的任何给定 k/r 的对的数量。请注意，在整个循环中，v3[k] 和 v2[k] 通常为零，直到它们达到我们在上一次迭代中预测的 k*r 值。