文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

對(duì)于給定的整數(shù) n, 如果 n 的 k（k>=2）進(jìn)制數(shù)的所有數(shù)位全為1，則稱 k（k>=2）是 n 的一個(gè)好進(jìn)制。

以字符串的形式給出 n, 以字符串的形式返回 n 的 最小 好進(jìn)制。

示例 1： 輸入："13" 輸出："3" 解釋：13 的 3 進(jìn)制是 111。示例 2： 輸入："4681" 輸出："8" 解釋：4681 的 8 進(jìn)制是 11111。示例 3： 輸入："1000000000000000000" 輸出："999999999999999999" 解釋：1000000000000000000 的 999999999999999999 進(jìn)制是 11。提示： n的取值范圍是 [3, 10^18]。 輸入總是有效且沒有前導(dǎo) 0。

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/smallest-good-base
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

• 數(shù)字 n 假設(shè)為 2 進(jìn)制，它最多有多少位是可以求出來的，進(jìn)制越大，位數(shù)越少
• 從最多可能的位數(shù)開始遍歷
• 每種位數(shù) bit 的情況下，二分查找進(jìn)制 k，使得 bit 位 k 進(jìn)制 111…的數(shù)等于 n，即找到
• 由于 bit 是從大到小，即進(jìn)制是小到大的，找到一個(gè)解就是最小好進(jìn)制

class Solution { public:string smallestGoodBase(string n) {long long num = stoll(n);int bit = floor(log(num) / log(2))+1;for( ; bit >= 2; --bit){ //枚舉有多少位數(shù)long long l = 2, r = num-1, mid;while(l <= r){mid = l+((r-l)>>1); // 進(jìn)制 midint flag = ok(num, mid, bit);if(flag == 0)return to_string(mid);else if(flag == 1)//進(jìn)制太大， 位數(shù)超了 nr = mid-1;else // 進(jìn)制太小，位數(shù)不夠 nl = mid+1;}}return "";}int ok(long long num, long long k, int bit){long long ans = 0;for(int i = 0; i < bit; ++i){if(ans > ceil((num-1)/k)) // ans*k+1 > num， 進(jìn)制太大了return 1;ans = ans*k+1;}if(ans == num)return 0;//找到了return -1;//進(jìn)制太小了} };

12 ms 6 MB C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長(zhǎng)按或掃碼關(guān)注我的公眾號(hào)（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 483. 最小好进制（二分查找）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。