970-強整數

Rindia 發布于2019-08-16 14:11 / 651人閱讀

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

前言

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;
                }
            }
        }

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/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