【每日一题20220608】完全平方

:mage:‍ 给定一个正整数n(3<n<109),请编写一个函数,试着找出平方数,让它们的和值刚好等于n,返回这些平方数的个数。如果n本身是平方数则返回1。

【示例】
输入:17
输出:2
解释:17=16+1,其中16是4的平方,1是1的平方,所以能由2个平方数凑齐,因此返回2。

题目难度:中等
题目来源:codewars-Sums of Perfect Squares

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

assert solution(17) == 2
assert solution(19) == 3
assert solution(16) == 1
def solution(n: int) -> int:
    # your code here
    result = []
    num_list = str(pow(n, 0.5)).split('.')
    if int(num_list[1]) == 0:
        return 1
    else:
        square_number = int(num_list[0])
        while 2 <= square_number:
            times = 0
            int_num = n
            while int_num >= 1:
                if int_num == n:
                    times += 1
                    int_num -= square_number ** 2
                else:
                    times += 1
                    int_num -= int(str(pow(int_num, 0.5)).split('.')[0]) ** 2
            result.append(times)
            square_number -= 1
    return min(result)


assert solution(17) == 2
assert solution(19) == 3
assert solution(16) == 1

def solution(n: int) -> int:
    list1 = [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
    if n in list1:
        return 1
    new_list = [1, 2, 3, 1]
    for i in range(5, 109):
        tmp_list = []
        if i in list1:
            tmp = 1
        else:
            for j in range(i // 2):
                tmp = new_list[j] + new_list[i - j - 2]
                tmp_list.append(tmp)
            tmp = min(tmp_list)
        new_list.append(tmp)
    return new_list[n - 1]


assert solution(17) == 2
assert solution(19) == 3
assert solution(20) == 2
def solution(n:int):
for i in range(11,0,-1):
        if i**2<n and n-i**2>2:
            return min([1+solution(n-i**2),1+solution(n-(i-1)**2)])
        elif i**2<n:
            return 1+solution(n-i**2)
        elif i**2==n:
            return 1
assert solution(16)==1
assert solution(17)==2
assert solution(19)==3
assert solution(111)==4
1 Like

使用 Markdown 代码语法:python

谢了

为啥19应该返回3呢,不应该是16+1+1+1总共有4个数吗?

关闭