0

我正在为一个问题编写一个解决方案，其中代码将在给定列表 a 的列表中找到毕达哥拉斯三元组的数量。但是，当我将代码提交给自动评分器时，在某些测试用例中我的代码会失败，但我不知道出了什么问题。请帮我指出我的错误......

def Q3(a):
    lst = [i ** 2 for i in a]
    lst.sort()
    ans = 0

    for x in lst:
        for y in lst:
            if (x + y) in lst:
                ans += 1

    return ans // 2

“勾股三元组”是勾股定理的整数解，例如，32+42=52。给定一个正整数列表，找出毕达哥拉斯三元组的数量。如果至少一个整数不同，则两个毕达哥拉斯三元组不同。

执行

· 实现一个函数 Q3(A)，其中 A 是一个正整数列表。列表 A 的大小最大为 250。

· 列表 A 中没有重复项

· 此函数返回毕达哥拉斯三元组的数量。

样本

· Q3( [3,4,6,5] ) = 1

· Q3( [4,5,6] ) = 0

4

3 回答 3

1

简单但不是非常有效的解决方案是在下面的 3 个嵌套 for 循环中循环遍历范围内的数字列表（例如，我从 1 到 100 取了数字）。但是对于 100 个元素会慢一些，它需要 100^3 次操作

triplets = []
for base in range(1,101):
    for height in range(1,101):
        for hypotenuse in range(1,101):
            # check if forms a triplet

            if hypotenuse**2 == base**2 + height**2:
                triplets.append(base, height, hypotenuse)

通过计算每个底边和高度组合的斜边，然后检查斜边是否是整数，可以稍微提高效率（有更好的解决方案）

    triplets = []
    for base in range(1,101):
        for height in range(1,101):
            hypotenuse = math.sqrt(base**2 + height**2)
            # check if hypotenuse is integer by ramiander division by 1                    
            if hypotenuse%1==0:
                triplets.append(base, height, hypotenuse)  
                 

# the above solution written a list comprehension
a = range(1,101)
[(i,j,math.sqrt(i*i+j*j)) for i in a for j in a if math.sqrt(i*i+j*j)%1==0]

如果您认为 (3,4,5) 和 (3,5,4) 不同，请使用集合而不是列表，最后得到 len(triplets_set)

于 2021-04-12T04:01:26.070 回答
-1

鉴于您现在通过编辑添加到您的问题中的输入的限制，我认为您的实现在逻辑上没有任何问题。您的代码可能无法通过的唯一类型的测试用例必须与性能相关，因为您正在使用最慢的解决方案之一，即使用 3 个嵌套循环迭代整个列表范围（in运算符本身是通过循环实现的） ）。

由于列表已排序并且我们想要x < y < z，我们应该y从开始x + 1并z从开始y + 1。并且由于给定一个x， 的值x取决于 的值y，对于每个给定的值，y我们可以递增z直到z * z < x * x + y * y不再成立，如果z * z == x * x + y * y此时，我们找到了一个毕达哥拉斯三元组。这允许y并仅z扫描上述值x一次，因此将时间复杂度从 O(n^3) 降低到 O(n^2)，当列表的大小为 250 时，速度提高了大约 40 倍：

def Q3(a):
    lst = [i * i for i in sorted(a)]
    ans = 0
    for x in range(len(lst) - 2):
        y = x + 1
        z = y + 1
        while z < len(lst):
            while z < len(lst) and lst[z] < lst[x] + lst[y]:
                z += 1
            if z < len(lst) and lst[z] == lst[x] + lst[y]:
                ans += 1
            y += 1
    return ans
于 2018-10-17T08:31:10.023 回答
-1

问题 1：假设您的输入是

[3,4,5,5,5]

尽管您的问题有些不清楚，但我的假设是这应该算作三个毕达哥拉斯三元组，每个都使用三个 5 之一。

你的函数只会返回 1。

问题 2：正如 Sayse 指出的那样，您的“三元组”可能会尝试使用相同的数字两次。

您最好使用itertools.combinations从正方形列表中获取不同的组合，并计算出现了多少合适的三元组。

from itertools import combinations

def Q3(a):
    squares = [i**2 for i in a]
    squares.sort()
    ans = 0

    for x,y,z in combinations(squares, 3):
        if x + y == z:
            ans += 1

    return ans
于 2018-10-17T07:47:27.887 回答