資訊專欄INFORMATION COLUMN
摘要：題目鏈接，但是不是結(jié)果，而是冪。方法特別巧妙，另外求冪的和還可以優(yōu)化用快速冪來求。知道冪之后，根據(jù)逼近法，可以得到，冪的最大值是，當(dāng)然這個是的時候。注意求不能直接用因為里面和的轉(zhuǎn)換過程中會丟失信息，所以要用乘來做。
483. Smallest Good Base
題目鏈接：https://leetcode.com/problems...
enumerate，但是不是結(jié)果，而是冪。方法特別巧妙，另外求冪的和還可以優(yōu)化用快速冪來求。知道冪之后，根據(jù)逼近法，可以得到base：k = logm(n) = (long) (pow(n, 1/m)) = (long) (log(n) / log(m))，冪的最大值是min(log2(n), 64)，當(dāng)然這個是m>1的時候。注意求pow(base, m)不能直接用pow因為java里面double和long的轉(zhuǎn)換過程中會丟失信息，所以要用乘來做。
參考這個博客：
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;
}
}
另外題目標(biāo)簽是binary search，應(yīng)該是對k的取值可以用binary search來找。
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/76401.html
摘要： 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...
摘要： 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...
摘要：在中已經(jīng)澄清分號恩，這也是規(guī)范一部分閱讀更多類型分配強制轉(zhuǎn)換執(zhí)行強制類型轉(zhuǎn)換的語句。對于整型值大于位的進行位運算將導(dǎo)致不可預(yù)見的行為。在范圍內(nèi)使用進行對象查詢譯文出處 類型 基本類型：訪問基本類型時，應(yīng)該直接操作類型值 string number boolean null undefined javascriptvar foo = 1; var bar = foo; bar ...
閱讀 2588·2019-08-30 10:53
閱讀 3191·2019-08-29 16:20
閱讀 2947·2019-08-29 15:35
閱讀 1769·2019-08-29 12:24
閱讀 2876·2019-08-28 18:19
閱讀 1851·2019-08-23 18:07
閱讀 2331·2019-08-23 15:31
閱讀 1168·2019-08-23 14:05
