完全平方数


题目描述

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

示例1

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

示例2

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

分析

  1. 采用队列BFS,第一次(相当于第一层),依次对分别对root减去1,4,9… (减数要小于root)
  2. 判断减完后的结果是否为0,如果不是,加入队列中。如果是,则返回层数。
  3. 取出队列中的元素,进行再一轮(层)减法,然后判断。重复步骤二,直到结束。
  4. 画图类似与一个多叉树。

参考代码

class Solution {
public:
    int numSquares(int n) {
       queue <int> q ;
      vector<bool> exit(n,false) ;
      int temp = n ;
       for(int i = 0 ,j = 1 ;  j*j <= temp ;++i ,++j)
       {
       	  	if(temp - j*j == 0)
    	    {
    			return 1 ;
    	    }
       		q.push(temp-j*j);
       		exit[temp-j*j] = true ;	
       }

       int step = 1 ;
       while(!q.empty())
       {
       	  int len = q.size();
          for(int i = 0 ; i < len ; ++i)
          	{
          		int num = q.front();
                q.pop();
          		for(int i = 0 , j = 1 ; j*j  <= num ; ++i,++j)
          		{
          			if(num - j*j == 0)
          			{
          				return ++step;
          			}
          			// 避免队列里有重复数字
          			if(exit[num-j*j] == false)  {q.push(num-j*j);}
          		}
          	}
          	++step;
       }
       return step;
    }
};

文章作者: 瑾年
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 瑾年 !
 上一篇
0-1矩阵 0-1矩阵
题目描述给定一个由 0 和 1 组成的矩阵,找出每个元素到最近的 0 的距离。
下一篇 
打开键盘的锁 打开键盘的锁
题目描述 你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字: ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ 。每个拨轮可以自由旋转:例如把 ‘9’ 变为 ‘0’,’0’ 变为 ‘9
  目录