C#版[击败100%的提交] - Leetcode 279. 完全平方数 - 题解

C#版 - Leetcode 279. 完全平方数 - 题解

Leetcode 279. Perfect Squares

在线提交: https://leetcode.com/problems/perfect-squares/

题目描述

给定正整数 n，找到若干个完全平方数(比如 1, 4, 9, 16, …)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

示例 1:

输入: n = 12
输出: 3 
解释: 12 = 4 + 4 + 4.

示例 2:

输入: n = 13
输出: 2
解释: 13 = 4 + 9.

• 题目难度：中等
• 通过次数：1K
• 提交次数：2.7K
• 贡献者：jianchao.li.fighter
• 相关话题 广度优先搜索 数学 动态规划 相似题目 计数质数 丑数 II

思路：

首先由四平方和定理(拉格朗日定理) - Wikipedia： 每个正整数都可以表示为至多4个正整数的平方和。 如果把0包括进去，就正好可以表示为4个数的平方和。

比如： 5=02+02+12+225=02+02+12+225 = 0^2 + 0^2 + 1^2 + 2^2, 7=12+12+12+227=12+12+12+227 = 1^2 + 1^2 + 1^2 + 2^2 (穷举可知7只有这种唯一的展开形式).

根据题意不考虑0，那拿去0后，一个数最后能分成的完全平方数的个数可能是1, 2, 3, 4.

然后，有一个容易得出的结论： 4⋅n=(2⋅a)2+(2⋅b)2+(2⋅c)2+(2⋅d)2⇔4k⋅n=(2k⋅a)2+(2k⋅b)2+(2k⋅c)2+(2k⋅d)2⇔n=a2+b2+c2+d2(a,b,c,d,k,n∈Z+)4⋅n=(2⋅a)2+(2⋅b)2+(2⋅c)2+(2⋅d)2⇔4k⋅n=(2k⋅a)2+(2k⋅b)2+(2k⋅c)2+(2k⋅d)2⇔n=a2+b2+c2+d2(a,b,c,d,k,n∈Z+)4 \cdot n = (2\cdot a)^2 + (2\cdot b)^2 + (2\cdot c)^2 + (2\cdot d)^2 \; \Leftrightarrow \; 4^k \cdot n = (2^k \cdot a)^2 + (2^k \cdot b)^2 + (2^k \cdot c)^2 + (2^k \cdot d)^2 \; \Leftrightarrow \; n = a^2 + b^2 + c^2 + d^2 \;(a, b, c, d, k, n \in Z_+)

另外根据同余的性质以及x2≡(−x)2x2≡(−x)2x^2 \equiv (-x)^2可知： x2≡(−x)2⇔x2≡(−x)2(mod8)x2≡(−x)2⇔x2≡(−x)2(mod8)x^2\equiv (-x)^2 \; \Leftrightarrow \; x^2\equiv (-x)^2\pmod 8

假如一个数n可表示为 8⋅k+78⋅k+78\cdot k +7, 则 n=x2≡(−x)2(mod8)=7n=x2≡(−x)2(mod8)=7n = x^2\equiv (-x)^2\pmod 8 = 7，而 02=0,12=1,22=402=0,12=1,22=40^2 = 0, 1^2 = 1, 2^2 = 4, 由于7具有唯一展开形式 7=12+12+12+227=12+12+12+227 = 1^2 + 1^2 + 1^2 + 2^2 (对应于代码中的path 1)，故此时数n一定只能展开为4个数的平方和.

对于输入的正整数n，首先对n迭代，使n=n4n=n4n = \frac{n}{ 4}, 直到 ⌊n/4⌋⌊n/4⌋\lfloor n/4 \rfloor == 0, 剩余的情形(从小到大)如下： n=8⋅k→02+02+02+02+8=02+02+22+22n=8⋅k→02+02+02+02+8=02+02+22+22n = 8\cdot k \quad \; \; \rightarrow 0^2 + 0^2 + 0^2 + 0^2 + 8 = 0^2 + 0^2 + 2^2 + 2^2 (会据实际情况转换为后面的6种情况之一，因而最后的路径为 path 3, path 2 or path 4).

n=8⋅k+1→02+02+02+12n=8⋅k+1→02+02+02+12n = 8\cdot k +1 \rightarrow 0^2 + 0^2 + 0^2 + 1^2 (path 2) n=8⋅k+2→02+02+12+12n=8⋅k+2→02+02+12+12n = 8\cdot k +2 \rightarrow 0^2 + 0^2 + 1^2 + 1^2 (path 3) n=8⋅k+3→02+12+12+12n=8⋅k+3→02+12+12+12n = 8\cdot k +3 \rightarrow 0^2 + 1^2 + 1^2 + 1^2 (path 4) n=8⋅k+4→02+02+02+22n=8⋅k+4→02+02+02+22n = 8\cdot k +4 \rightarrow 0^2 + 0^2 + 0^2 + 2^2 (path 2) n=8⋅k+5→02+02+12+22n=8⋅k+5→02+02+12+22n = 8\cdot k +5 \rightarrow 0^2 + 0^2 + 1^2 + 2^2 (path 3) n=8⋅k+6→02+12+12+22n=8⋅k+6→02+12+12+22n = 8\cdot k +6 \rightarrow 0^2 + 1^2 + 1^2 + 2^2 (path 4)

故已AC代码如下：

public class Solution
{
    public int NumSquares(int n)  // 已知 n>0
    {
        while (n % 4 == 0)
            n /= 4;

        if (n % 8 == 7)
            return 4;   // (path 1)

        for (int i = 0; i * i <= n; i++)
        {
            int r = (int)Math.Sqrt(n - i * i);
            if (i * i + r * r == n)
            {
                if (i == 0 || r == 0)
                    return 1;           // (path 2)

                return 2;   // (path 3)
            }
        }

        return 3;   // (path 4)
    }
}

Rank:

You are here! Your runtime beats 100.00% of csharp submissions.