题目

题目地址：https://leetcode-cn.com/problems/perfect-squares/

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

示例1：

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

示例2：

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

答案

基于BFS实现

首先枚举出所有的值，然后利用BFS进行搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
package com.jarome.leetcode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;

public class SolutionNumSquares {

    public int numSquares(int num) {
        List<Integer> sqrtList = new ArrayList<>();
        // 先枚举出所有
        for (int i = 1; i <= num; i++) {
            int sqrt = i * i;
            if (sqrt == num) {
                return 1;
            } else if (sqrt > num) {
                // 已经超过当前数字了就不需要在执行了
                break;
            }
            sqrtList.add(sqrt);
        }
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(num);
        int count = 0;
        while (!queue.isEmpty()) {
            count = count + 1;
            // 避免循环加入队列
            Set<Integer> temp = new HashSet<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Integer poll = queue.poll();
                for (Integer sqrt : sqrtList) {
                    if (poll.equals(sqrt)) {
                        return count;
                    } else if (poll < sqrt) {
                        break;
                    } else {
                        int nextVal = poll - sqrt;
                        if (!temp.contains(nextVal)) {
                            queue.offer(nextVal);
                            temp.add(nextVal);
                        }
                    }
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        SolutionNumSquares sns = new SolutionNumSquares();
        System.out.println(sns.numSquares(12));
    }

}

运行情况：

  • 执行时间：88ms
  • 内存消耗：41.3MB

基于动态规划

待完成

计算公式：num = a * a + b ； b = c * c + d ；以此类推