<ul id="m0mgq"></ul>

<strike id="m0mgq"></strike>

483. Smallest Good Base

mikasa 發布于2019-08-19 10:45 / 1898人閱讀

摘要：題目鏈接，但是不是結果，而是冪。方法特別巧妙，另外求冪的和還可以優化用快速冪來求。知道冪之后，根據逼近法，可以得到，冪的最大值是，當然這個是的時候。注意求不能直接用因為里面和的轉換過程中會丟失信息，所以要用乘來做。

483. Smallest Good Base

題目鏈接：https://leetcode.com/problems...

enumerate，但是不是結果，而是冪。方法特別巧妙，另外求冪的和還可以優化用快速冪來求。知道冪之后，根據逼近法，可以得到base：k = logm(n) = (long) (pow(n, 1/m)) = (long) (log(n) / log(m))，冪的最大值是min(log2(n), 64)，當然這個是m>1的時候。注意求pow(base, m)不能直接用pow因為java里面double和long的轉換過程中會丟失信息，所以要用乘來做。
參考這個博客：
http://bookshadow.com/weblog/...

public class Solution {
    public String smallestGoodBase(String n) {
        long num = Long.valueOf(n);
        
        for(int m = Math.min((int) (Math.pow(num, 0.5)), 64); m > 1; m--) {
            // k = logm(num)
            long k = (long) Math.pow(num, 1.0 / m);
            if(isGoodBase(num, k, m)) return String.valueOf(k);
        }
        return String.valueOf(num - 1);
    }
    
    private boolean isGoodBase(long num, long base, int m) {
        long sum = num;
        long val = 1;
        // calculate k^0, k^1,  ..., k^m
        for(int i = 0; i <= m; i++) {
            sum -= val;
            val *= base;
        }
        return sum == 0;
    }
}

另外題目標簽是binary search，應該是對k的取值可以用binary search來找。

GPU云服務器云服務器 Smallest Good good域名 BASE

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/76401.html

一些做著玩的題

摘要：這是我在平時有時間的時候做的一些算法上的題目想看更新請移步這里題目描述解法這個問題當時拿到的時候是完全沒有思路的，后面上網查詢了一下這個題目，知道了使用斐波那契數列就能夠解這道題目，，，當然百度作業幫上面也有相應的解法，套路就是題目為一這是我在平時有時間的時候做的一些算法上的題目想看更新請移步這里題目： Climbing Stairs 描述 You are climbing a ...

cheukyin 2019-08-20 13:57 評論0 收藏0
怎么用多模型數據庫為復雜數據建模？--航空艦隊實例

摘要： Editor’s note: Full disclosure — the author is a developer and software architect at ArangoDB GmbH, which leads the development of the open source multi-model database ArangoDB. In recent years...

tianhang 2019-08-20 17:47 評論0 收藏0
怎么用多模型數據庫為復雜數據建模？--航空艦隊實例

摘要： Editor’s note: Full disclosure — the author is a developer and software architect at ArangoDB GmbH, which leads the development of the open source multi-model database ArangoDB. In recent years...

xingqiba 2019-06-28 15:52 評論0 收藏0
【譯】JavaScript最全編碼規范

摘要：在中已經澄清分號恩，這也是規范一部分閱讀更多類型分配強制轉換執行強制類型轉換的語句。對于整型值大于位的進行位運算將導致不可預見的行為。在范圍內使用進行對象查詢譯文出處類型基本類型：訪問基本類型時，應該直接操作類型值 string number boolean null undefined javascriptvar foo = 1; var bar = foo; bar ...

afishhhhh 2019-08-21 10:30 評論0 收藏0