970-強整數(shù)

Rindia 發(fā)布于2019-08-16 14:11 / 729人閱讀

摘要：前言的強整數(shù)給定兩個非負整數(shù)和，如果某一整數(shù)等于，其中整數(shù)且，那么我們認為該整數(shù)是一個強整數(shù)。返回值小于或等于的所有強整數(shù)組成的列表。

前言

Weekly Contest 118的強整數(shù)：

給定兩個非負整數(shù) x 和 y，如果某一整數(shù)等于 x^i + y^j，其中整數(shù) i >= 0 且 j >= 0，那么我們認為該整數(shù)是一個強整數(shù)。
返回值小于或等于 bound 的所有強整數(shù)組成的列表。
你可以按任何順序返回答案。在你的回答中，每個值最多出現(xiàn)一次。
示例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

解題思路

本題只需要找出正整數(shù)中滿足x^i + y^j且<=bound的數(shù)即可，所以只需要用兩重for循環(huán)找出滿足條件的數(shù)字即可。

注意事項：

循環(huán)中會出現(xiàn)重復的值，例如

輸入：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進行結果去重

執(zhí)行超時的情況，例如輸入：x = 1, y = 3, bound = 100。所以可以選擇循環(huán)次數(shù)為bound(x^bound>bound恒成立)，而不是Integer.MAX_VALUE。

實現(xiàn)代碼

    /**
     * 970. 強整數(shù)
     * @param x
     * @param y
     * @param bound
     * @return
     */
    public List powerfulIntegers(int x, int y, int bound) {
        //選擇使用Set是因為結果中會出現(xiàn)重復值
        Set set = new HashSet<>();
        //循環(huán)次數(shù)為bound，而不是Integer.MAX_VALUE，防止執(zhí)行超時
        for (int i = 0; i < bound; i++) {
            int tmp1 = (int) Math.pow(x, i);
            //如果第一個數(shù)就大于bound，直接中斷循環(huán)，防止執(zhí)行超時
            if (tmp1 > bound) {
                break;
            }
            //循環(huán)次數(shù)為bound，而不是Integer.MAX_VALUE，防止執(zhí)行超時
            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直接中斷循環(huán)，因為后續(xù)的數(shù)字都會超出bound
                    break;
                }
            }
        }

文章版權歸作者所有，未經(jīng)允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉載請注明本文地址：http://www.ezyhdfw.cn/yun/72831.html

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

摘要：也稱縮小增量排序，是直接插入排序算法的一種更高效的改進版本。希爾排序是非穩(wěn)定排序算法。該方法因於年提出而得名。前言因為比較隨心所欲,所以我不按難度分享算法,所以你們會看到有時候順序有變化,因為我發(fā)表的時候會按照難度修改下位置,盡量讓你們看的時候能從簡單開始,以后每次更新都加個更新時間好了,讓你們知道我進度.新增計時函數(shù)直觀對比效率并且因為資料比較雜,很多都是我個人理解說法,如果有發(fā)...

Baaaan 2019-08-26 10:35 評論0 收藏0
你對Number一無所知

摘要：表示正數(shù)，表示負數(shù)。是一個無符號整數(shù)，因為長度是位，取值范圍是。浮點數(shù)具體數(shù)值的實際表示。例如對于單精度浮點數(shù)，指數(shù)部分實際最小值是，對應的尾數(shù)部分從一直到，相鄰兩小浮點數(shù)之間的距離都是而與最近的浮點數(shù)即最小的非規(guī)約數(shù)也是。二進制表示小數(shù) 例如用二進制表示 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值介紹

摘要：的數(shù)字類型是基于標準實現(xiàn)的，該標準也被稱為浮點數(shù)使用的是雙精度即位進制由于數(shù)字值可以使用對象進行封裝，因此數(shù)字值可以調(diào)用中的方法。數(shù)組和其他語言不同，在JavaScript中，數(shù)組可以擁有不同值類型,可以使字符串，數(shù)字，對象，還可以是數(shù)組(多維數(shù)組就是這樣形成的). 聲明數(shù)組后，可以直接通過索引的方式進行賦值: var arr = []; arr.length; //0 ...

hsluoyz 2019-08-20 15:21 評論0 收藏0
通俗的方式理解動態(tài)類型，靜態(tài)類型；強類型，弱類型

摘要：不允許隱式轉換的是強類型，允許隱式轉換的是弱類型。拿一段代碼舉例在使用調(diào)用函數(shù)的時候會先生成一個類模板運行時生成，執(zhí)行的時候會生成類模板，執(zhí)行的時候會生成類模板。 0 x 01 引言今天和一個朋友討論 C++ 是強類型還是弱類型的時候，他告訴我 C++ 是強類型的，他和我說因為 C++ 在寫的時候需要 int，float 等等關鍵字去定義變量，因此 C++ 是強類型的，我告訴他 C+...

周國輝 2019-08-22 13:40 評論0 收藏0
java學習筆記 - 基本數(shù)據(jù)類型、直接量和變量

摘要：數(shù)據(jù)類型結構圖基本數(shù)據(jù)類型布爾值數(shù)值類型定點類型字符字節(jié)短整數(shù)整數(shù)長整數(shù)浮點類型單精度浮點數(shù)雙精度浮點數(shù)引用數(shù)據(jù)類型類或枚舉或接口數(shù)組基本數(shù)據(jù)類型由上圖可知，基本數(shù)據(jù)類型只有種。變量的變量一般有四個基本屬性變量名數(shù)據(jù)類型儲存單元變量值。數(shù)據(jù)類型結構圖基本數(shù)據(jù)類型布爾值 (true / false) 數(shù)值類型定點類型字符 char 字節(jié) byte 短整數(shù) shor...

jlanglang 2019-08-14 17:01 評論0 收藏0