【每日一题20220808】求最小的加总值

兴趣爱好交流 每日一题
1

:mage:‍ 给定一个正整数数组 X，它的元素将通过对它们运行以下操作根据需要多次进行转换：

if X[i] > X[j] then X[i] = X[i] - X[j]

当无法进行更多转换时，返回其总和（“最小可能总和”）。

例如，输入 X = [6, 9, 21] 的元素的连续变换详述如下：

X_1 = [6, 9, 12] # -> X_1[2] = X[2] - X[1] = 21 - 9
X_2 = [6, 9, 6]  # -> X_2[2] = X_1[2] - X_1[0] = 12 - 6
X_3 = [6, 3, 6]  # -> X_3[1] = X_2[1] - X_2[0] = 9 - 6
X_4 = [6, 3, 3]  # -> X_4[2] = X_3[2] - X_3[1] = 6 - 3
X_5 = [3, 3, 3]  # -> X_5[1] = X_4[0] - X_4[1] = 6 - 3

返回的输出是最终转换的总和（此处为 9）。

例子

solution([6, 9, 21]) #-> 9

解决步骤：

[6, 9, 12] #-> X[2] = 21 - 9
[6, 9, 6] #-> X[2] = 12 - 6
[6, 3, 6] #-> X[1] = 9 - 6
[6, 3, 3] #-> X[2] = 6 - 3
[3, 3, 3] #-> X[1] = 6 - 3

题目难度：一般
题目来源：https://www.codewars.com/kata/52f677797c461daaf7000740


def solution(a: list) -> int:
    # your code here

assert solution([9]) == 9
assert solution([6, 9, 21]) == 9
assert solution([1, 21, 55]) == 3
assert solution([1, 21, 55, 5, 58, 55, 887, 845521, 8784, 124, 589, 21, 878, 124, 889]) == 15
assert solution([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29,30]) == 30

补充说明：

有性能测试由非常大的数字和大小至少 30000 的数组组成。请编写一个有效的算法来防止超时。

2 
def solution(a: list) -> int:
    a.sort(reverse=True)
    a_len = len(a)
    min_num = a[-1]
    if min_num == 1:
        return a_len
    if a_len == 1:
        return min_num
    while len(a) > 1:
        for i in range(0, len(a) - 1):
            a[i] = abs(a[i] - a[i + 1])
            a_min = min(a)
            if min_num > a_min and a_min != 0:
                min_num = a_min
        a.pop(-1)
        if min_num == 1:
            return a_len
    return a_len*min_num
3 
def solution(a: list) -> int:
    # for x,y in enumerate(a):
    new_list = []
    count = 0
    while len(a) != 1 :
        if a[-1] > a[-2]:
            a[-1] = a[-1] - a[-2]
        elif a[-1] < a[-2]:
            a[-2] = a[-2] - a[-1]
        else:
            new_list.append(a[-1])
            a.pop(-1)
    else:
        # print(sum(new_list)+a[0])
        return(sum(new_list)+a[0])
5 
def solution(n:list) -> int:
    a=max(n)
    b=min(n)
    while a-b >0:
        c=a-b
        n.append(c)
        n.remove(a)
        a,b=max(n),min(n)
    return b * len(n)
6 
def solution(a: list) -> int:
    if len(a)==1:
        return sum(a)
    else:
        while a.count(a[0])!=len(a):
            a.sort(reverse=False)
            for i in range(len(a)-1,0,-1):
                if a[i]>a[i-1]:
                    a[i]=a[i]-a[i-1]
                    print(a)
                    break
        return sum(a)

assert solution([9]) == 9
assert solution([6, 9, 21]) == 9
assert solution([1, 21, 55]) == 3
assert solution([1, 21, 55, 5, 58, 55, 887, 845521, 8784, 124, 589, 21, 878, 124, 889]) == 15
assert solution([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29,30]) == 30
7 
def solution(a: list) -> int:
    if len(a)==1:
        return sum(a)
    else:
        while a.count(a[0])!=len(a):
            a.sort(reverse=False)
            for i in range(len(a)-1,0,-1):
                if a[i]>a[i-1]:
                    a[i]=a[i]-a[i-1]
                    break
        return sum(a)

assert solution([9]) == 9
assert solution([6, 9, 21]) == 9
assert solution([1, 21, 55]) == 3
assert solution([1, 21, 55, 5, 58, 55, 887, 845521, 8784, 124, 589, 21, 878, 124, 889]) == 15
assert solution([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29,30]) == 30