?LeetCode刷題實戰(zhàn)483：最小好進制
Given?an?integer?n?represented?as?a?string,?return?the?smallest?good?base?of?n.
We?call?k?>=?2?a?good?base?of?n,?if?all?digits?of?n?base?k?are?1's.
示例? ? ? ? ? ? ? ? ? ? ? ? ?
示例 1：
輸入："13"
輸出："3"
解釋：13?的 3?進制是 111。
示例 2：
輸入："4681"
輸出："8"
解釋：4681?的 8?進制是 11111。
示例 3：
輸入："1000000000000000000"
輸出："999999999999999999"
解釋：1000000000000000000?的 999999999999999999?進制是 11。
解題
import?java.math.BigInteger;
class?Solution?{
????public?static?String smallestGoodBase(String n)?{
????????//現(xiàn)將字符串解析成long型數(shù)據(jù)
????????long?s = Long.parseLong(n);
????????//對所有可能的指數(shù)n進行遍歷
????????for?(int?max_e = (int) (Math.log(s) / Math.log(2)) + 1; max_e >= 2; max_e--) {
????????????long?low = 2, high = s, mid;
????????????//進行二叉搜索，尋找最小的good base。
????????????while?(low <= high) {
????????????????mid = low + (high - low) / 2;
????????????????//一開始沒有使用BigInteger，會報錯
????????????????BigInteger left = BigInteger.valueOf(mid);
????????????????left = left.pow(max_e).subtract(BigInteger.ONE);
????????????????BigInteger right = BigInteger.valueOf(s).multiply(BigInteger.valueOf(mid).subtract(BigInteger.ONE));
????????????????int?cmr = left.compareTo(right);
????????????????if?(cmr == 0)
????????????????????return?String.valueOf(mid);
????????????????else?if?(cmr > 0)
????????????????????high = mid - 1;
????????????????else
????????????????????low = mid + 1;
????????????}
????????}
????????return?String.valueOf(s - 1);
????}
}