Leetcode-279-完全平方数

Leecode-279-完全平方数

题目描述

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

示例 1:

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

示例 2:

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

方法一：动态规划

算法思路：

• 首先初始化长度是 n + 1 的 数组dp,初始化的数组每个位置都为0
• 状态定义：dp[i] 表示每个数最少由多少个完全平方数相加而成
  • 如dp[2] = 2 = 1+1
• 对数组进行遍历，下标为i的每次先更新为最差的结果dp[i] = i = 1+1+1+1 .....(i个)
  • 动态转移方程dp[i] = Math.min(dp[i],dp[i - j*j] + 1)
  • i 表示当前数字 , j 表示之前算过的完全平方数字
  • i - j* j作为循环退出的条件，因为我们没必要每个数都遍历，如12 = 1+11 12 = 4+8 12 = 9+3 我们只需要得到3,8,11谁的解最优，那么12的解就是它+1 即可

举个例子：n = 5

1. 初始化

2. i = 1

3. i = 2

4. i = 3

5. i = 4

5. i = 5

// 动态规划:空间换时间

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];

        // dp[0] = 0;

        for (int i = 1; i <= n; i++) {
            // 最坏的情况下是每个数= +1+1+1 .... i次
            dp[i] = i;
            // 我们没必要1到N+1中的每一个数都去观察（i - j * j）
            for (int j = 1; i - j * j >= 0; j++) {
                // 动态转移方程
                // 本题的思路就是，对每一个N，观察1到N-1中，谁的解最小，那么N的解就是它+1.
                dp[i] = Math.min(dp[i],dp[i - j * j] + 1);
            }
        }
        return dp[n];
    }
}

复杂度分析

• 时间复杂度：O(n * sqrt(n))
• 空间复杂度：O(n)

方法二： BFS (广度优先搜索)

算法思路：

• 顺序遍历每一行，所以当节点差出现0时，此时一定是最短的路径。
• 如绿色所示，若此时节点为0，表示根节点可以由路径上的平方数{1,1,9}构成，返回此时的路径长度3，后续不在执行。
• 如红色所示，若节点值在之前已经出现，则不需要再计算，一定不会是最短路径，最短路径还未出现。

另外再谈一谈BFS的套路：（三要素）

• 一个队列（LinkedList进行出队入队操作）
• 一个集合（HashSet记录出现的元素）
• 一个level （变量：记录当前进入了哪一层）

class Solution {
    public int numSquares(int n) {
        // 1. 队列
        LinkedList<Integer> queue = new LinkedList<>();
        // 2. 已访问的集合
        HashSet<Integer> visited = new HashSet<>();

        // 队列和集合都加入首节点
        queue.offer(n);
        visited.add(n);
        int level = 0;  // 记录当前访问的层数

        while (!queue.isEmpty()){
            level++;
            int len = queue.size();

            for (int i = 0; i < len; i++) {
                int cur = queue.poll();
                for (int j = 1; j*j <= cur; j++) {
                    int tmp = cur - j*j;
                    // 找到了最短路径（图中绿色圈圈）
                    if (tmp == 0){
                        return level;
                    }
                    // 剪枝（对应图中红色圈圈）
                    if (!visited.contains(tmp)){
                        queue.offer(tmp);
                    }
                    // 加入set中为了减枝操作
                    visited.add(tmp);
                }
            }
        }
        return level;
    }
}

复杂度分析来自Leetcode官方

打赏