求解"完美平方数需要的n最少问题"代码

Question

"""
完美平方数需要的n最小
问题：给定一个正整数n,找到若干完全平方数，使得他们和为n且需要的完全平方数最小
数学思路：
四平方和定理：每个正整数都可以表示为至多4个正整数的平方和。故该题答案为1，2，3或4.
该数 n 若能整除4，则 n /= 4，结果不影响。【化简】
如果一个数除以8余7的话，那么肯定是由4个完全平方数组成。return 4
将其拆为两个平方数之和，如果拆成功了那么就会返回1或2，因为其中一个平方数可能为0，故判断拆的两个数是否为正整数
"""

class Solution:
    def ssr(self, n): #1.为什么定义对象不写__init__？
        while n % 4 == 0:
            n //= 4 # 这段是个什么意思，放这里干啥？到处查都没查到//=(注意//和=之间无空格）的含义，也不明白这里加在这里干啥？
        if n % 8 == 7:
            return 4
        for i in range(n + 1):
            temp = i * i
            if temp <= n:
                if int((n - temp) ** 0.5) ** 2 + temp == n:
                    return 1 + (0 if temp == 0 else 1)
            else:
                break
        return 3


if __name__ == '__main__':
    n = 12
    print("初始值:",n)
    solution = Solution()
    print("结果:", solution.ssr(n))

Answer 1

n // = 4

n = n // 4

表示n除以4的结果向下取整

python对类和对象，self，init的理解（内含实例解释）: https://blog.csdn.net/m0_51078229/article/details/111500368