Caterpillar Method

April 03, 2017

分類標籤:algorithm frontend interview

令 A = [a0, a1, …, an-1], ai > 0,要如何判斷是否存在一組 (p, q),其中 p <= q,使得 sum(ap, ap+1, … aq) = s?我們可以用下面介紹的Caterpillar Method

目錄

Caterpillar Method

front, back分別為毛毛蟲的“頭”和“尾”,當尾端固定時,我們讓頭往前最多伸長至總和不超過s的範圍,然後檢查總和是否剛好為s。如果不是s,則將尾端向前移動並更新總和。

def caterpillar(A, s):
    n = len(A)
    front, total = 0, 0
    for back in xrange(n):
        while front < n and total + A[front] <= s:
            total += A[front]
        if total == s:
            return True

        total -= A[back]

    return False

由於ai > 0,總和只會隨著頭向前伸長而遞增而最多不超過s,而尾端向前時總和必定減少,所以可以保證所有總和可能 >= s的情況都被檢查過了。

Count Triangle

A = [a0, a1, ..., an-1], ai > 0,如何找出數組(x, y, z)的數量,其中 0 <= x < y < z < n,使得數組可以形成三角形的邊長?

解法

先針對邊長由小到大排序,然後對x, y迭代,判斷是否 A[x] + A[y] > A[z]

z為毛毛蟲的“頭“,並讓z遞增直到A[x] + A[y] <= A[z]z - y - 1即為給定x, y能得到的三角形數量。

y遞增為y'的時候,z可以由舊的位置繼續計算,因為A[y'] > A[y] => A[x] + A[y'] > A[z-1],能夠組成三角形的(x, y, z)必定使得(x, y', z)也能組成三角形。

def triangles(A):
    n = len(A)
    result = 0
    A.sort()
    for x in xrange(n):
        z = x + 2
        for y in xrange(x + 1, n):
            while z < n and A[x] + A[y] > A[z]:
                z += 1
            result += z - y - 1

    return result

Reference

Caterpillar Method - Codility


Profile picture

Shubo Chao 軟體工程師,目前大多專注於前端開發