精华内容
下载资源
问答
  • 在10万以内判断一个整数,它加上 100 后是一个完全平方数,再加上 268 又是一个完全平方数,请问该数是多少? 平方数定义:完全平方指用一个整数乘以自己例如1*1,2*2,3*3等,依此类推。若一个数能表示成某个整数的...

    题目

    在10万以内判断一个整数,它加上 100 后是一个完全平方数,再加上 268 又是一个完全平方数,请问该数是多少?

    平方数定义:完全平方指用一个整数乘以自己例如1*12*23*3等,依此类推。若一个数能表示成某个整数的平方的形式,则称这个数为完全平方数。——from百度百科

    以下

    public class PerfectSquare {
        public static void main(String[] args) {
           for (int i = 1; i <=100000 ; i++) {
                int x = (int)Math.sqrt(i+100);
                int y = (int)Math.sqrt(i+268);
                if(x*x==(i+100)&&y*y==(i+268)){
                    System.out.println(i);
                }
            }
        }
    }
    

    一开始我想了一个超级笨的办法……26行;
    最后觉得还是得开方后强制转换。
    强制转换后直接丢掉小数点后的数。

    展开全文
  • 主要介绍了Java计算一个数加上100是完全平方数,加上168还是完全平方数,需要的朋友可以参考下
  • Java实现 LeetCode 279 完全平方数

    万次阅读 多人点赞 2020-03-04 22:06:50
    279. 完全平方数 给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, …)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。 示例 1: 输入: n = 12 输出: 3 解释: 12 = 4 + 4 + 4. 示例 2: 输入: n ...

    279. 完全平方数

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

    示例 1:

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

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

    PS:
    动态规划在数学面前一文不值

    任何正整数都可以拆分成不超过4个数的平方和 —> 答案只可能是1,2,3,4

    如果一个数最少可以拆成4个数的平方和,则这个数还满足 n = (4^a)*(8b+7)
    因此可以先看这个数是否满足上述公式,如果不满足,答案就是1,2,3了

    如果这个数本来就是某个数的平方,那么答案就是1,否则答案就只剩2,3了

    如果答案是2,即n=a2+b2,那么我们可以枚举a,来验证,如果验证通过则答案是2
    只能是3

    class Solution {
        public int numSquares(int n) {
                while(n%4==0)
                {
                    n/=4;
                }
                if(n%8==7)
                    return 4;
            
                int a=0;
                while((a*a)<=n)
                {
                    int b=(int)Math.pow((n-a*a),0.5);
                        if(a*a+b*b==n)
                        {
                            if(a!=0&&b!=0)
                            {
                                return 2;
                            }    
                            
                            else
                            {
                                return 1;
                            }
                        }
                    a++;
                }                 
                return 3;
        }
    }
    

    动态规划:

    class Solution {
          public int numSquares(int n) {
            int[] dp = new int[n+1];
            for(int i = 1; i <= n; i++){
                dp[i] = Integer.MAX_VALUE;
            }
            for(int i = 1; i <= n; i++){
                for(int j = 1; j*j <= i; j++){
                    if(i >= j*j){
                        dp[i] = Math.min(dp[i],dp[i-j*j]+1);
                    }
                }
            }
            return dp[n];
        }
    }
    
    展开全文
  • 完全平方数Java实现

    千次阅读 2019-08-19 19:01:59
    给定一个整数,求由几个完全平方数相加及平方数是多少 例:输入:13 输出:[9 4] 2 13 = 9 + 4 = 3^2 + 2^2 思路如下: 采用队列来遍历层次搜索树,并定义内部类存储key、Sq、step三个值。 1)找到key=0,确定正确...
    • 给定一个整数,求由几个完全平方数相加及平方数是多少
      例:输入:13 输出:[9 4] 2 13 = 9 + 4 = 3^2 + 2^2
      思路如下:
      在这里插入图片描述
      采用队列来遍历层次搜索树,并定义内部类存储key、Sq、step三个值。
      1)找到key=0,确定正确路径:13=9+....。返回9以及最深的树高 2,表示13可以由step个完全平方数组成。
      2)在main函数中将9 add进入ArrayList里,重复获取13-9的最大平方数。
      3)打印结果。
    import java.util.ArrayList;
    import java.util.LinkedList;
    import java.util.Queue;
    
    public class MySqrt {
        /**
         * 定义函数getSqrt 返回整数n的最大开方数的根
         * 例:13 = 9 +4   最大平方数9  返回根号9 = `3`
         * 使用牛顿迭代法求整数n的开方
         * @param n
         * @return
         */
        public static  int getSqrt(int n){
            double X0 = n;
            double Y0;
            Y0= X0*X0 - n;
            while (Math.abs(Y0)>0.0001){
                X0 = X0 - Y0/(2*X0);
                Y0 =  X0*X0 - n;
            }
            return (int) X0;
        }
    
        /**
         * 定义函数getNums 返回整数n中小于n的完全平方数 
         * 13-> [9 4 1]
         * 12->[9 4 1]
         * 4->[1]
         * @param n
         * @return
         */
        public static int[] getNums(int n){
            int size = MySqrt.getSqrt(n);
            int[] nums = new int[size];
            for (int i = 1; i <= size; i++) {
                nums[i-1] = i*i;
            }
            return nums;
        }
    
        /**
         * 定义内部类 
         * key n与完全平方数之差 
         * Sq  完全平方数
         * step 树高
         */
        static class Ele{
            int key ;
            int Sq;
            int step;
            public Ele(int key,int Sq, int step){
                this.key = key;
                this.Sq = Sq;
                this.step = step;
            }
    
            @Override
            public String toString() {
                return this.key+" "+this.Sq+" "+this.step;
            }
        }
    
        /**
         * 方法返回正确路径的最大平方数
         * @param n
         * @return
         */
        public static int getMaxSq(int n){
            int[] nums ;
            int LuJing = 1;
            int finallyNum = 0;
            ArrayList<Ele> arrayList = new ArrayList<>();
            Queue<Ele> queue = new LinkedList<Ele>();
            Ele ele = new Ele(n,0,0);
            arrayList.add(ele);
            while (ele!=null){
                if (ele.key==0){
                    finallyNum = ele.step;
                    break;
                }
                nums = getNums(ele.key);
                for (int i = 0; i <nums.length; i++) {
                    queue.offer(new Ele(ele.key - nums[i],nums[i],ele.step+1));
                }
                ele = queue.poll();
            }
            //System.out.println(ele.toString());
            return ele.Sq;
        }
        public static void main(String[] args) {
            //System.out.println(Arrays.toString(getNums(13)));
            int n = 13;
            int temp = 0;
            ArrayList arrayList = new ArrayList();
            //System.out.println(getMaxSq(n));
            /*
            在找到n的最大平方数之后做差
            之后不断的重复这一过程,直到差为0
             */
            while (n>=0){
                if(n==0){
                    break;
                }
                temp = getMaxSq(n);
                arrayList.add(temp);
                n = n - temp;
            }
            System.out.println(arrayList.toString());
            System.out.println("The MaxSq's size is "+arrayList.size());
        }
    }
    
    

    结果:

    [9, 4]
    The MaxSq's size is 2
    
    Process finished with exit code 0
    
    展开全文
  • 完全平方数(Java)

    2020-11-25 20:31:43
    给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, ...)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。 示例 1: 输入: n = 12 输出: 3 解释: 12 = 4 + 4 + 4 示例 2: 输入: n = 13 输出: 2 ...

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

    示例 1:
    输入: n = 12
    输出: 3
    解释: 12 = 4 + 4 + 4

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


    package com.loo;

    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.HashSet;
    import java.util.Set;

    public class NumberSquares {

        public static void main(String[] args) {
            int n = 13;
            System.out.println(getNumberSquares1(n));
            System.out.println(getNumberSquares2(n));
            System.out.println(getNumberSquares3(n));
            System.out.println(getNumberSquares4(n));
        }
        
        public static int getNumberSquares1(int n) {
            int[] dp = new int[n+1];
            Arrays.fill(dp, Integer.MAX_VALUE);
            dp[0] = 0;
            int max_index = (int)Math.sqrt(n) + 1;
            int[] square_nums = new int[max_index];
            for (int i=1;i<max_index;i++) {
                square_nums[i] = i * i;
            }
            for (int i=1;i<=n;i++) {
                for (int k=1;k<max_index;k++) {
                    if (i - square_nums[k] < 0) {
                        break;
                    }
                    dp[i] = Math.min(dp[i], dp[i-square_nums[k]] + 1);
                }
            }
            return dp[n];
        }
        
        // 贪心枚举
        public static Set<Integer> square_nums = new HashSet<Integer>();
        public static int getNumberSquares2(int n) {
            square_nums.clear();
            for (int i=1;i*i<=n;i++) {
                square_nums.add(i*i);
            }
            int count = 1;
            for (;count<=n;count++) {
                if (isDivided(n , count)) {
                    return count;
                }
            }
            return count;
        }
        
        public static boolean isDivided(int n , int count) {
            if (count == 1) {
                return square_nums.contains(n);
            }
            for (Integer num : square_nums) {
                if (isDivided(n - num , count - 1)) {
                    return true;
                }
            }
            return false;
        }
        
        // 贪心 + BFS(广度优先搜索)
        public static int getNumberSquares3(int n) {
            ArrayList<Integer> square_List = new ArrayList<Integer>();
            for (int i=1;i*i<=n;i++) {
                square_List.add(i*i);
            }
            Set<Integer> queue = new HashSet<Integer>();
            queue.add(n);
            int count = 0;
            while (queue.size()>0) {
                count++;
                Set<Integer> nextQueue = new HashSet<Integer>();
                for (Integer num:queue) {
                    for (Integer square : square_List) {
                        if (num.equals(square)) {
                            return count;
                        } else if (num < square) {
                            break;
                        } else {
                            nextQueue.add(num - square);
                        }
                    }
                }
                queue = nextQueue;
            }
            return count;
        }
        
        // 1. 检查数字 n 的形式是否为 n=4^{k}(8m+7),如果是,则直接返回 4。(前面的k为4的k次方)
        // 2. 否则,进一步检查这个数本身是否是一个完全平方数,或者这个数是否可以分解为两个完全平方数和。
        // 3. 在底部的情况下,这个数可以分解为 3 个平方和,但也可以根据四平方定理,通过加零,把它分解为 4 个平方。但是这里被要求找出最小的平方数
        public static int getNumberSquares4(int n) {
            while (n%4==0) {
                n /= 4;
            }
            if (n%8 == 7) {
                return 4;
            }
            if (isSquare(n)) {
                return 1;
            }
            for (int i=1;i*i<=n;i++) {
                if (isSquare(n - i*i)) {
                    return 2;
                }
            }
            return 3;
        }
        
        public static boolean isSquare(int n) {
            int s = (int)Math.sqrt(n);
            return n == s*s;
        }

    }

    展开全文
  • Java实现完全平方数

    2019-08-20 15:10:41
    完全平方数组 1.完全平方数:9等于3的平方,16等于4的平方,这些都是完全平方数。 2.完全平方数组:[3,6,10]相邻两个数的和是完全平方数的话,这就是完全平方数组。 3+6=9,6+10=16然后[3,6,10]把里面的数进行...
  • java判断一个整数是不是完全平方数

    千次阅读 2019-08-20 18:24:39
    这种方法的思路是把比给出的目标num小的整数都做一次平方运算,如果num等于某一个平方就返回true。这里做了一些优化,及不需要把小于num的全部计算一次,只需要计算小于等于n的就可以。 public static boolean...
  • 版权声明:保留个人权利,可转载,请注明出处... 如程序有不当之处,敬请指正。/* (程序头部注释开始) ... 如程序有不当之处,敬请指正。 * 文件名称: 《一些简单的java编程题(10) ————判断完全平方数》 ...
  • Java算法实例,计算一个数的平方数 Java,一个整数,加上100后是一个完全平方数,加上168又是一个完全平方数,请问该数是多少? 解题思路大致是:在10万以内判断,先将该数加上100后再开方,再将该数加上168后再开方...
  • 高分悬赏:Java语言怎么输出全部1000以内的完全平方数 高分悬赏:Java语言怎么输出全部1000以内的完全平方数
  • 给定一个正整数 num,编写一个函数,如果 num 是一个完全平方数,则返回 True,否则返回 False。 说明:不要使用任何内置的库函数,如 sqrt。 示例 1: 输入:16 输出:True 示例 2: 输入:14 输出:False 来源:...
  • 给定一个正整数 num,编写一个函数,如果 num 是一个完全平方数,则返回 True,否则返回 False。 说明:不要使用任何内置的库函数,如 sqrt。 示例 1: 输入:16 输出:True 示例 2: 输入:14 输出:False ...
  • 给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, ...)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。 示例 1: 输入: n = 12 输出: 3 解释: 12 = 4 + 4 + 4. 示例 2: 输入: n = 13 输出: ...
  • Java查询完全平方数

    2020-05-26 22:20:58
    Target:输入两个正整数a、b,输出a~b的所有完全平方数 例如, 1 = 1 x1 4 = 2 x 2 9 = 3 x 3 16 = 4 x 4 所以 1 4 9 16都是完全平方数 1.创建对象和调用,查找100-1000的完全平方数 package seven; public class ...
  • 完全平方数java

    2021-06-11 11:46:56
    给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, …)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。 给你一个整数 n ,返回和为 n 的完全平方数的 最少数量 。 完全平方数 是一个整数,其值...
  • 平方数之和java

    2021-04-28 09:45:36
    给定一个非负整数 c ,你要判断是否存在两个整数 a 和 b,使得 a2 + b2 = c 。 示例 1: 输入:c = 5 输出:true 解释:1 * 1 + 2 * 2 = 5 示例 2: 输入:c = 3 输出:false 示例 3: 输入:c = 4 ...
  • 公式法 数学技巧:所有的完全平方数都可以被表示成奇数和1+3+5+7+9 …。 public static boolean advancedIsSquare(int num) { if (num ) return false; for (int i = 1; num > 0; i += 2) num -= i; return 0...
  • 给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, …)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。 示例 1: 输入: n = 12 输出: 3 解释: 12 = 4 + 4 + 4. 示例 2: 输入: n = 13 输出: 2 ...
  • 完全平方数 Java

    2021-05-20 17:39:27
    题目链接举个例子13很显然产生了重复子结构这里我们的dp保存的是构成i的最少的个数那么对于每个来说,要么选他本身要么选他本身-他的倍数所以有dp[i]=Math.min(dp[i-j*j]+1,dp[i]);public int numSquares(int n) {...
  • Java实现 LeetCode 367 有效的完全平方数

    万次阅读 多人点赞 2020-03-10 19:30:35
    367. 有效的完全平方数 给定一个正整数 num,编写一个函数,如果 num 是一个完全平方数,则返回 True,否则返回 False。 说明:不要使用任何内置的库函数,如 sqrt。 示例 1: 输入:16 输出:True 示例 2: 输入:...
  • 题目:一个整数,它加上100后是一个完全平方数,再加上168又是一个完全平方数,请问该数是多少? 按题意循环应该从-100开始(整数包括正整数、负整数、零),这样会多一个满足条件的数-99。 但是我看到大部分人解这...
  • <!--题目:一个整数,它加上100后是一个完全平方数,再加上168又是一个完全平方数,请问该数是多少--!>
  • leetcode分类下所有的题解均为作者...给定正整数n,找到若干个完全平方数(比如1, 4, 9, 16, ...)使得它们的和等于n。你需要让组成和的完全平方数的个数最少。 示例1: 输入: n = 12 输出: 3 解释: 12 = 4 + 4 ...
  • 这个用java判断完全平方数,输出yes或者no。⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯求大神不会啊⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯![图片说明](https://img-ask.csdn.net/upload/201603/17/1458176740_530251.png)
  • 给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, …)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。 给你一个整数 n ,返回和为 n 的完全平方数的 最少数量 。 完全平方数 是一个整数,其值...
  • 279. 完全平方数(java)

    2020-06-04 11:29:58
    279. 完全平方数 题目描述 给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, …)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。 示例 1: 输入: n = 12 输出: 3 解释: 12 = 4 + 4 + 4. 示例 2:...
  • 如何用JAVA实现找到100~999的完全平方数(转载自:邵发) //主程序 package fuckthismy; public class helloworld { public static void main(String[] args) { Mymath ex=new Mymath();...
  •  输出大等于n的最小的完全平方数。  若一个数能表示成某个自然数的平方的形式,则称这个数为完全平方数  Tips:注意数据范围 输入格式  一个整数n 输出格式  大等于n的最小的完全平方数 样例输入 71711 样例...
  • 则称这个数为完全平方数 Tips:注意数据范围 输入格式 一个整数n 输出格式 大等于n的最小的完全平方数 样例输入 71711 样例输出 71824 数据规模和约定 n是32位有符号整数 import java.util.Scanner; public class 大...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 11,284
精华内容 4,513
关键字:

java完全平方数

java 订阅