首页
学习
活动
专区
工具
TVP
发布
您找到你想要的搜索结果了吗?
是的
没有找到

完全平方

给定正整数 n,找到若干个完全平方(比如 1, 4, 9, 16, …)使得它们的和等于 n。你需要让组成和的完全平方的个数最少。...队列的这种写法也是很有趣Queue queue = new LinkedList(); 对于这个问题建模: 整个问题转化为一个图论问题,从n到0,每个数字表示一个节点,如果有两个数字x到y相差一个完全平方...四平方定理: 任何一个正整数都可以表示成不超过四个整数的平方之和。 满足四平方和定理的n(这里要满足由四个构成,小于四个不行), 必定满足 n=4a(8b+7) 或者使用动态规划。...下面我们来用bfs解题,以n=13为例,请看下图13开始,第一遍:距离1X1可以到12节点,距离2X2可以到9节点,距离3X3可以到4节点,距离4X4超过13了肯定到不了0节点;第二遍将跨过jXj完全平方能到达的点加入已清空的队列...,再广度遍历,遍历到9节点时,发现有距离是完全平方3X3可以到达0节点。

38010

LeetCode 633.平方之和

平方之和[1] 描述 给定一个非负整数 c ,你要判断是否存在两个整数 a 和 b,使得 a2 + b2 = c 解题思路 判断 c 是否为非负整数,若是,则直接返回 false 利用 Math 包中...sqrt()方法求出小于 c 的平方根的最大整数作为右指针,同时设置左指针从 0 开始; 开始循环,若左指针小于右指针,判断两指针之和与 c 的大小; 若和等于 c,返回 false; 若和小于 c,...* Project : LeetCode * Package : PACKAGE_NAME * Class : SixHundredThirtThree * Desc : 633.平方之和...,并将其强制转换为不大于平方根值的最大整数 int flag = (int) Math.sqrt(c); int i = 0; while (i <= flag){ if ((i*i...平方之和: https://leetcode-cn.com/problems/sum-of-square-numbers/

36410

力扣279——完全平方

原题 给定正整数 n,找到若干个完全平方(比如 1, 4, 9, 16, ...)使得它们的和等于 n。你需要让组成和的完全平方的个数最少。...优化的话,自然就是先算最大的,也就是离 n 最近的且比它小的平方数了。 编码的时候需要注意,一般我们使用队列实现广度优先搜索,因为它是先进先出。...接下来我们来看看代码: import java.util.*; class Solution { public int numSquares(int n) { // 利用队列实现广度优先搜索...动态转移方程为:dp[i] = MIN(dp[i], dp[i - j * j] + 1),i表示当前数字,j*j表示平方 这个思路相当于求出了从1到n所有数字的最小平方的个数。...关键在于第4点,也就是后面的计算可以依赖于前面求出的结果,每一个都找出其所有基于以前求过的,加上1个完全平方后,最小的的平方的个数。

45020

C语言刷题随记 —— 完全平方

题目描述 一个整数,它加上 100 后是一个完全平方,再加上 168 又是一个完全平方,请问该是多少? 2....程序分析 在 10 万以内判断(可以是比100000大的数字),先将该加上 100 后再开方,再将该加上 268 后再开方,如果开方后的结果满足如下条件,即是结果。...思路 遍历10万以内的数字,将每个数字分别加上 100 和 168后开平方,最后计算加上100 和 168 后的两平方,如果一个平方根的平方等于该,这说明此是完全平方。...后开方后的结果*/ y=sqrt(i+268); /*y 为再加上 168 后开方后的结果*/ if(x*x==i+100&&y*y==i+268) /*如果一个平方根的平方等于该...,这说明此是完全平方*/ printf("\n%ld\n",i); } return 0; }

22410
领券