0279 完全平方数

你好啊，我是蓝莓，今天是每日一题的第 58 天。

题目描述

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4

示例 2：

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

提示：

1 <= n <= 104

实现

思路

这是一个中等难度的题目
解决这个问题可以采用图的广度优先搜索的方法
图的顶点是当前剩余还需要拼凑的数值
图的边是完全平方数的平方
经过一条边，就相当于让顶点的值减去了一个完全平方数的平方从而来到了一个新的顶点
因此，广度优先搜索的层数的深度，就是我们要求的值

C++ 代码实现

/ 图的广度优先搜索
// 看遍历到第几层的时候能够遍历到节点 0
class Solution {
public:
    int numSquares(int n) {
        // v, step
        queue<pair<int, int>> q;
        vector<bool> visted(n+1, false);
        q.push( make_pair(n, 0) );

        while( !q.empty() ) {
            pair<int, int> v = q.front();
            q.pop();

            int num = v.first;
            int step = v.second;

            if( num == 0 ) {
                return step;
            }

            for( int i = 1 ; num - i*i >= 0 ; i++ ) {
                int next = num - i*i;
                if( visted[next] == false) {
                    q.push( make_pair(next, step+1) );
                    visted[next] = true;
                }
            }
        }

        return -1;
    }
};

C++ 代码实现优化

// 优化：提前算法的结束步骤
class Solution {
public:
    int numSquares(int n) {
        // v, step
        queue<pair<int, int>> q;
        vector<bool> visted(n+1, false);
        q.push( make_pair(n, 0) );

        while( !q.empty() ) {
            pair<int, int> v = q.front();
            q.pop();

            int num = v.first;
            int step = v.second;



            for( int i = 1 ; ; i++ ) {
                int next = num - i*i;
                if( next < 0 ) {
                    break;
                }

                if( visted[next] == false) {
                    
                    // 提前返回的步骤
                    if( next == 0 ) {
                        return step+1;
                    }

                    q.push( make_pair(next, step+1) );
                    visted[next] = true;
                }
            }
        }

        return -1;
    }
};