970-强整数

Rindia 发布于2019-08-16 14:11 / 438人阅读

摘要：前言的强整数给定两个非负整数和，如果某一整数等于，其中整数且，那么我们认为该整数是一个强整数。返回值小于或等于的所有强整数组成的列表。

前言

Weekly Contest 118的强整数：

给定两个非负整数 x 和 y，如果某一整数等于 x^i + y^j，其中整数 i >= 0 且 j >= 0，那么我们认为该整数是一个强整数。
返回值小于或等于 bound 的所有强整数组成的列表。
你可以按任何顺序返回答案。在你的回答中，每个值最多出现一次。
示例1：
输入：x = 2, y = 3, bound = 10
输出：[2,3,4,5,7,9,10]
解释： 
2 = 2^0 + 3^0
3 = 2^1 + 3^0
4 = 2^0 + 3^1
5 = 2^1 + 3^1
7 = 2^2 + 3^1
9 = 2^3 + 3^0
10 = 2^0 + 3^2
示例2：
输入：x = 3, y = 5, bound = 15
输出：[2,4,6,8,10,14]
提示：

1 <= x <= 100
1 <= y <= 100
0 <= bound <= 10^6

解题思路

本题只需要找出正整数中满足x^i + y^j且<=bound的数即可，所以只需要用两重for循环找出满足条件的数字即可。

注意事项：

循环中会出现重复的值，例如

输入：x = 2, y = 3, bound = 10
输出：[2,3,4,5,7,9,10]
解释： 
2 = 2^0 + 3^0
3 = 2^1 + 3^0
4 = 2^0 + 3^1
5 = 2^1 + 3^1
5 = 2^2 + 3^0
7 = 2^2 + 3^1
9 = 2^3 + 3^0
10 = 2^0 + 3^2

其中重复的情况为

5 = 2^1 + 3^1
5 = 2^2 + 3^0

可以选择先使用Set进行结果去重

执行超时的情况，例如输入：x = 1, y = 3, bound = 100。所以可以选择循环次数为bound(x^bound>bound恒成立)，而不是Integer.MAX_VALUE。

实现代码

    /**
     * 970. 强整数
     * @param x
     * @param y
     * @param bound
     * @return
     */
    public List powerfulIntegers(int x, int y, int bound) {
        //选择使用Set是因为结果中会出现重复值
        Set set = new HashSet<>();
        //循环次数为bound，而不是Integer.MAX_VALUE，防止执行超时
        for (int i = 0; i < bound; i++) {
            int tmp1 = (int) Math.pow(x, i);
            //如果第一个数就大于bound，直接中断循环，防止执行超时
            if (tmp1 > bound) {
                break;
            }
            //循环次数为bound，而不是Integer.MAX_VALUE，防止执行超时
            for (int j = 0; j < bound; j++) {
                int tmp2 = (int) (Math.pow(y, j));
                int tmp = tmp1 + tmp2;
                //判断是否超出bound
                if (tmp <= bound) {
                    set.add(tmp);
                } else {//超出bound直接中断循环，因为后续的数字都会超出bound
                    break;
                }
            }
        }

idc机房托管服务器托管 java 整数除整数 3强强：强签名?

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/72831.html

一些前端算法詳解 --- (不定时更新)

摘要：也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因於年提出而得名。前言因為比较随心所欲,所以我不按难度分享算法,所以你们会看到有时候顺序有变化,因為我发表的时候会按照难度修改下位置,尽量让你们看的时候能从简单开始,以后每次更新都加个更新时间好了,让你们知道我进度.新增计时函数直观对比效率并且因為资料比较杂,很多都是我个人理解说法,如果有发...

Baaaan 2019-08-26 10:35 评论0 收藏0
你对Number一无所知

摘要：表示正数，表示负数。是一个无符号整数，因为长度是位，取值范围是。浮点数具体数值的实际表示。例如对于单精度浮点数，指数部分实际最小值是，对应的尾数部分从一直到，相邻两小浮点数之间的距离都是而与最近的浮点数即最小的非规约数也是。二进制表示小数例如用二进制表示 0.8125 0.8125 0.8125*2 = 1.625 取整为 1 0.625*2=1.25 取整为 1 0.25*2=0...

Hanks10100 2019-08-22 15:15 评论0 收藏0
JavaScript值介绍

摘要：的数字类型是基于标准实现的，该标准也被称为浮点数使用的是双精度即位进制由于数字值可以使用对象进行封装，因此数字值可以调用中的方法。数组和其他语言不同，在JavaScript中，数组可以拥有不同值类型,可以使字符串，数字，对象，还可以是数组(多维数组就是这样形成的). 声明数组后，可以直接通过索引的方式进行赋值: var arr = []; arr.length; //0 ...

hsluoyz 2019-08-20 15:21 评论0 收藏0
通俗的方式理解动态类型，静态类型；强类型，弱类型

摘要：不允许隐式转换的是强类型，允许隐式转换的是弱类型。拿一段代码举例在使用调用函数的时候会先生成一个类模板运行时生成，执行的时候会生成类模板，执行的时候会生成类模板。 0 x 01 引言今天和一个朋友讨论 C++ 是强类型还是弱类型的时候，他告诉我 C++ 是强类型的，他和我说因为 C++ 在写的时候需要 int，float 等等关键字去定义变量，因此 C++ 是强类型的，我告诉他 C+...

周国辉 2019-08-22 13:40 评论0 收藏0
java学习笔记 - 基本数据类型、直接量和变量

摘要：数据类型结构图基本数据类型布尔值数值类型定点类型字符字节短整数整数长整数浮点类型单精度浮点数双精度浮点数引用数据类型类或枚举或接口数组基本数据类型由上图可知，基本数据类型只有种。变量的变量一般有四个基本属性变量名数据类型储存单元变量值。数据类型结构图基本数据类型布尔值 (true / false) 数值类型定点类型字符 char 字节 byte 短整数 shor...

jlanglang 2019-08-14 17:01 评论0 收藏0