美文网首页
279. Perfect Squares

279. Perfect Squares

作者: codingXue | 来源:发表于2016-09-17 09:02 被阅读23次

    问题描述

    Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.
    For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

    问题分析

    Lagrange 四平方定理: 任何一个正整数都可以表示成不超过四个整数的平方之和。
    如果知道这个定理,就可以首先将答案限定在[1, 4]区间中,证明见链接。
    但还需确定具体的解。有如下两条规则:

    • 如果n可以被4整除,那么n/4和n是可以用相同个完全平方数表示的。
    • 如果n可表示为4a(8b+7),那么n可表示为4个完全平方数之和。

    但是我没有找到上面两条规则的证明……

    在运用完上面两条规则后,再判断是1还是2,剩下的是3。

    AC代码

    数论方法:Runtime: 39 ms

    class Solution(object):
        def numSquares(self, n):
            """
            :type n: int
            :rtype: int
            """
            while n % 4 == 0:
                n /= 4
            if n % 8 == 7:
                return 4
            a = 0
            while a * a <= n:
                b = int((n - a * a) ** 0.5)
                if a * a + b * b == n:
                    return 1 if a == 0 else 2
                a += 1
            return 3
    

    动规方法:Runtime: 189 ms
    动规需要注意:将规划数组作为一个类变量,每次增长它才能AC,如果每次重新计算规划数组,则TLE,参考了Discuss内容.

    class Solution(object):
        d = [0]
        def numSquares(self, n):
            """
            :type n: int
            :rtype: int
            """
            for i in  range(len(self.d), n+1):
                m = i
                j = 1
                while j * j <= i:
                    if j * j == i:
                        m = 1
                        break
                    if self.d[i-j*j] + 1 < m:
                        m = self.d[i-j*j] + 1
                    j += 1
                self.d.append(m)
    
            return self.d[n]
    

    相关文章

      网友评论

          本文标题:279. Perfect Squares

          本文链接:https://www.haomeiwen.com/subject/nzriettx.html