时间戳

首页 > 解决方案 > Python 无法比较最大公约数的值

python - Python 无法比较最大公约数的值

问题描述

我正在尝试解决这个hackerrank问题：

在此处输入图像描述

这是我的尝试：

from fractions import gcd

def connectedCities(numCities, threshold, originCities, destinationCities):
    # Write your code here
    output = []
    
    for i in range(0, len(originCities)):
        if gcd(originCities[i], destinationCities[i]) > threshold:
            output.append(1)
        else:
            output.append(0)
    
    return output

但是对于以下输入：

10
1
4
10
4
3
6
4
3
6
2
9

我的输出是：

Your Output (stdout)
0
1
0
1


Expected Output
1
1
1
1

标签： pythonalgorithmgreatest-common-divisor

解决方案

我绝对不知道这是否好，但它可以解决问题。

from math import gcd

def exists(a, b, t):
    return gcd(a, b) > t

# find goes trough everithing it can
def find(paths, seen, start, end, true, path):
    for i in paths[start]:
        if i in seen or i == true:
            continue
        # creating shortcuts, it may backfire or help performance, it depends
        for j in path:
            paths[i].add(j)
        path.append(i)
        if i == end:
            return True
        seen.add(i)
        if find(paths, seen, i, end, true, path):
            return True
    return False


def solve(nc, t, sc, ec):
    ew = sc + ec

    # create lookup table
    paths = [None] * len(ew)
    for i in range(len(ew)):
        paths[i] = set()

    # fill it
    for i in range(len(ew)):
        for j in range(i+1, len(ew)):
            if exists(ew[i], ew[j], t):
                paths[i].add(j)
                paths[j].add(i)

    # traverse paths to find a values
    res = []
    seen = set()
    path = []
    for i in range(len(sc)):
        if exists(sc[i], ec[i], t) or find(paths, seen, i, i + len(sc), i, path):
            res.append(1)
        else:
            res.append(0)
        seen.clear()
        path.clear()
    return res
            
        

print(solve(10, 1, [4, 10, 4, 3, 6], [4, 3, 6, 2, 9]))

推荐阅读