leetcode279：完全平方数

题目链接

leetcode

题目描述

给你一个整数 n ，返回和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方。换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

C++ 代码

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;

/*
    状态表示：
        f[i] 表示平方数组成和为 i 完全平方数的最少数量。
    状态计算：
        对于每个 i，枚举 j
        f[i] = min(f[i], f[i - j * j] + 1)，其中 1 <= j <= i
    初始化：
        f[0] = 0，答案 f[n]

    时间复杂度：O(n*sqrt(n))
        近似上界，得到 S = O(n*sqrt(n))
    空间复杂度：O(n)
        需要额外 O(n) 的空间存储状态。
*/
class Solution {
public:
    int numSquares(int n) {
        vector<int> f(n + 1, n);
        f[0] = 0;
        for (int i = 1; i <= n; i ++) {
            for (int j = 1; j * j <= i; j ++) {
                f[i] = min(f[i], f[i - j * j] + 1);
            }
        }

        return f[n];
    }
};

/*
    数学

    1.拉格朗日四平方和定理，可知答案必定为 1, 2, 3, 4 中的一个。
    2.勒让德三平方和定理，可知当 n = 4a(8b+7) 时，n 不能写成 3 个数的平方和。
    3.根据以上定理去枚举，判断出答案是否为 1, 2, 3，若都不是则答案为 4。

    时间复杂度：O(sqrt(n)+logn)
        判断答案是否为 1 或 3，时间复杂度为 O(1)，
        枚举答案是否为 2，时间复杂度为 O(sqrt(n))，
        判断答案是否为 4，时间复杂度为 O(logn)，
        故总时间复杂度为 O(sqrt(n) + logn)。
*/
class Solution_2 {
public:
    int numSquares(int n) {
        // case: 答案为 1
        if (checkPerfectSquare(n)) return 1;

        // case: 答案为 2，枚举 
        for (int i = 1; i <= n / i; i ++) {
            if (checkPerfectSquare(n - i * i)) return 2;
        }

        // case: 答案为 4，勒让德三平方和定理
        if (checkAnswer4(n)) return 4;
        return 3;
    }

    // 判断是否为完全平方数
    bool checkPerfectSquare(int x) {
        int r = sqrt(x);
        return r * r == x;
    }

    // 判断是否能表示为 4k*(8b+7)
    bool checkAnswer4(int x) {
        while (x % 4 == 0) x /= 4;
        return x % 8 == 7;
    }
};

int main() {
    Solution solution;
    vector<int> test_case = {12, 13};

    for (int& num : test_case) {
        cout << "Input: " << num << endl;
        cout << "Output: " << solution.numSquares(num) << endl;
    }

    return 0;
}

Golang 代码

package main

import (
	"fmt"
	"math"
)

/*
   动态规划：
       使用一个数组 dp，其中 dp[i] 表示将 i 表示为完全平方数之和的最少数量。
       初始化 dp[0] = 0，因为 0 的最少数量为 0。
       对于每个 i，遍历所有可能的完全平方数 square，更新 dp[i] 为 dp[i-square] + 1 的最小值。
   边界条件：
       如果 n 是完全平方数，直接返回 1。

   时间复杂度：O(n*sqrt(n))
       动态规划的时间复杂度为 O(n*sqrt(n))，其中 n 是目标值，sqrt(n) 是完全平方数的数量。
   空间复杂度：O(n)
       使用了一个大小为 n+1 的数组 dp，空间复杂度为 O(n)。
*/
// numSquares 返回将正整数 n 表示为若干个完全平方数之和的最少数量
func numSquares(n int) int {
    // 动态规划数组，dp[i] 表示将 i 表示为完全平方数之和的最少数量
	dp := make([]int, n+1)
	for i := range dp {
		dp[i] = math.MaxInt32
	}
	dp[0] = 0 // 0 的最少数量为 0

	// 遍历所有可能的完全平方数
	for i := 1; i * i <= n; i ++ {
		square := i * i
		for j := square; j <= n; j ++ {
			dp[j] = min(dp[j], dp[j-square]+1)
		}
	}

	return dp[n]
}

func main() {
	// 测试用例
	testCases := []struct {
		n        int
		expected int
	}{
		{
			n:        12,
			expected: 3,
		},
		{
			n:        13,
			expected: 2,
		},
	}

	for i, tc := range testCases {
		result := numSquares(tc.n)
		fmt.Printf("Test Case %d, Input: n = %d\n", i+1, tc.n)
		if result == tc.expected {
			fmt.Printf("Test Case %d, Output: %d, PASS\n", i+1, result)
		} else {
			fmt.Printf("Test Case %d, Output: %d, FAIL (Expected: %d)\n", i+1, result, tc.expected)
		}
	}
}