环己三烯的冬眠舱

天天网抑云，偶尔读点书。

0%

每日Hard - Day 10

发表于 更新于

Tags

日期 2022年10月8日
是否独立完成 否
涉及算法 二分查找

题面

LeetCode 483. 最小好进制

以字符串的形式给出 n , 以字符串的形式返回 n 的最小 好进制 。

如果 n 的 k(k>=2) 进制数的所有数位全为1，则称 k(k>=2) 是 n 的一个 好进制 。

示例 1：

1
2
3
输入：n = "13"
输出："3"
解释：13 的 3 进制是 111。

示例 2：

1
2
3
输入：n = "4681"
输出："8"
解释：4681 的 8 进制是 11111。

示例 3：

1
2
3
输入：n = "1000000000000000000"
输出："999999999999999999"
解释：1000000000000000000 的 999999999999999999 进制是 11。

题解

又是一道经典的“不看题解不会做，一看题解恍然大悟”的题。由于数据的范围是[3,1e18]，在64位以内，我们可以从大到小（位数越多，进制越小）枚举全是1的二进制位数，然后再二分k进制的所有可能性，就可以快速找到最小的好进制。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
private:
    unsigned long long str2ull(string& s) {
        unsigned long long res = 0;
        for (char c : s) {
            res *= 10;
            res += c - '0';
        }
        return res;
    }
public:
    string smallestGoodBase(string n) {
        unsigned long long num = str2ull(n);
        for (int i = 64; i >= 2; i--) {
            unsigned long long l = 2;
            unsigned long long r = num;
            while (l < r) {
                unsigned long long mid = l + ((r - l) >> 1);
                unsigned long long temp = 0;
                for (int j = 0; j < i; j++) {
                    if ((log(temp) + log(mid)) / log(2) >= 64) {
                        temp = num + 1;
                        break;
                    }
                    else temp = temp * mid + 1;
                }
                if (temp > num) r = mid;
                else if (temp < num) l = mid + 1;
                else return to_string(mid);
            }
        }
        return "";
    }
};

里面涉及了一个新学的小技巧：如果一个unsigned long long已经溢出过了，那么必然是不符合答案的，应该直接退出计算然后继续二分下一个答案。那么怎么判断temp和mid相乘后是否溢出过呢？只要这两个数分别对2取对数（即二进制的最高位在哪一位），只要取完对数相加后大于或等于64，就意味着已经溢出并自动取模过了。

有的没的

没事听点歌（RADWIMPS - グランドエスケープ （《天气之子》插曲））

整点二次元！