「力扣」第 279 题:完全平方式


「力扣」第 279 题:完全平方式

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

示例 1:

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

示例 2:

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

Java 代码:

import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.Queue;


public class Solution {

    public int numSquares(int n) {
        // 是否访问过
        boolean[] visited = new boolean[n + 1];

        Queue<Integer> queue = new LinkedList<>();
        queue.add(n);
        int step = 1;
        while (!queue.isEmpty()) {

            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int head = queue.poll();
                for (int k = 1; k * k <= head; k++) {
                    if (k * k == head) {
                        return step;
                    }

                    int next = head - k * k;
                    if (!visited[next]) {
                        queue.offer(next);
                        visited[next] = true;
                    }
                }
            }
            step ++;
        }

        // 正常情况下是不会走到这句的
        throw new IllegalArgumentException("参数错误");
    }

    public static void main(String[] args) {
        int n = 7168;
        Solution s = new Solution();
        int numSquares = s.numSquares(n);
        System.out.println(numSquares);
    }
}

Python 代码:

class Solution:
    def numSquares(self, n: int) -> int:

        if n == 1:
            return 1
        if n ** 0.5 == int(n ** 0.5):
            return 1

        # 加法因子的候选集
        square_set = set()

        for i in range(1, n // 2 + 1):
            square = i * i
            if square <= n:
                square_set.add(square)
            else:
                break
        depth = 1
        non_leaf_node = [n]
        while len(non_leaf_node) != 0:
            depth += 1
            current_plus_factor = []
            for element in non_leaf_node:
                for s in square_set:
                    if element - s in square_set:
                        return depth
                    else:
                        current_plus_factor.append(element - s)
            non_leaf_node = current_plus_factor


if __name__ == '__main__':
    s = Solution()
    res = s.numSquares(4)
    print('结果', res)

Python 代码:

class Solution:
    def numSquares(self, n: int) -> int:
        marked = [False for _ in range(n)]
        queue = [(0, n)]
        while queue:
            level, top = queue.pop(0)
            level += 1
            start = 1
            while True:
                residue = top - start * start
                if residue == 0:
                    return level
                elif residue < 0:
                    break
                else:
                    if not marked[residue]:
                        queue.append((level, residue))
                        marked[residue] = True
                start += 1


if __name__ == '__main__':
    s = Solution()
    res = s.numSquares(4)
    print('结果', res)

Python 代码:

from collections import deque

# 不知道用数组好还是用哈希表去重好

class Solution:
    def numSquares(self, n: int) -> int:
        square_root = int(n ** 0.5)
        # print(square_root)

        squares = [num ** 2 for num in range(1, square_root + 1)]
        # print(squares)

        queue = deque()
        queue.append((1, n))
        s = set()
        s.add(n)

        while queue:
            # print(queue)
            level, top = queue.popleft()
            for num in squares:
                residue = top - num
                if residue < 0:
                    break
                if residue == 0:
                    return level
                if residue not in s:
                    queue.append((level + 1, residue))
                    s.add(residue)


if __name__ == '__main__':
    n = 19
    solution = Solution()
    res = solution.numSquares(n)
    print(res)

方法二:动态规划

Java 代码:

import java.util.Arrays;

class Solution {

    // 说明 dp[0] = 0; 的合理性
    // 表达式 1 + dp[i - j * j] = 1 ,表示它自己就是一个完全平方式,所以结果是 1

    public int numSquares(int n) {
        // 0 要占用一个位置
        int[] dp = new int[n + 1];

        // 赋初值,设置成为 4 是数学定理保证
        Arrays.fill(dp, 4);
        // 该值被参考,设置成 0
        dp[0] = 0;

        // 一个一个求,自底向上
        for (int i = 1; i <= n; i++) {
            for (int k = 0; k * k <= i; k++) {
                dp[i] = Math.min(dp[i], dp[i - k * k] + 1);
            }
        }
        return dp[n];
    }

    public static void main(String[] args) {
        int n = 7168;
        Solution solution = new Solution();
        int numSquares = solution.numSquares(n);
        System.out.println(numSquares);
    }
}

(本节完)


文章作者: liweiwei1419
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 liweiwei1419 !
评论
 上一篇
特别好用的二分查找法模板(第 2 版) 特别好用的二分查找法模板(第 2 版)
特别好用的二分查找法模板(第 2 版) 特点: 1、讲算法思想,也讲细节; 2、把细节的地方理解清楚,就不难了,二分法可以轻松掌握。 一、点击视频快速理解 「力扣」第 1095 题:山脉数组中查找目标值 题解 (特别推荐,这道题我花了很长
下一篇 
「力扣」第 207 题:课程表 「力扣」第 207 题:课程表
「力扣」第 207 题:课程表 链接:207. 课程表; 题解地址:拓扑排序 + 深度优先遍历(Python 代码、Java 代码)。 现在你总共有 n 门课需要选,记为 0 到 n-1。 在选修某些课程之前需要一些先修课程。 例如,想
  目录