LeetCode 483. 最小好进制--数学分析+二分

  1. 最小好进制

对于给定的整数 n, 如果n的k(k>=2)进制数的所有数位全为1,则称 k(k>=2)是 n 的一个好进制。

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

示例 1:

输入:“13”
输出:“3”
解释:13 的 3 进制是 111。

示例 2:

输入:“4681”
输出:“8”
解释:4681 的 8 进制是 11111。

示例 3:

输入:“1000000000000000000”
输出:“999999999999999999”
解释:1000000000000000000 的 999999999999999999 进制是 11。

提示:

n的取值范围是 [3, 10^18]。
输入总是有效且没有前导 0。

题解:

因为考虑到大数运算,这里为了方便直接用python编写代码,现在考虑下代码,给定一个数字n,并且基底为x,那么有:
n=x ^ k+x ^ (k-1)+x ^ (k-2)+…+x ^ 1+x ^ 0
于是n=(x ^ (k+1)-1)/(x-1);
n是已经知道的,现在寻找存在的正整数x和k使得上述等式成立,于是我们想到传统的方法,一个元素遍历去对另外一个元素二分找答案,那么就无非对x从2到n-1遍历,每次遍历然后对k二分找是否存在,或者反过来对k遍历,针对每个k去二分找x这个答案。那么问题明确了,用哪种方案呢?因为n最多为1e18,遍历x的话肯定超时,所以不能这样,但是去遍历k就可以,因为k为指数,我们考虑最小的基底2,那么2的k次方大于1e18,k最多为60,然后遍历的过程中二分的时间复杂度为logn,所以最终的时间复杂度为60logn就不会超时了。

AC代码

class Solution:
    def smallestGoodBase(self, n: str) -> str:
        def fun(k,n):
            l=int(pow(n+1,1.0/(k+1)))
            if l==1:
                l+=1
            r=int(pow(n*(l*l)+1,1.0/(k+1)))
            fin=-1
            while l<=r:
                mid=int((l+r)/2)
                res=(mid**(k+1)-1)//(mid-1)
                if res>=n:
                    r=mid-1
                    fin=mid
                else:
                    l=mid+1
            if  abs((pow(fin,k+1)-1)//(fin-1)-n)<=1e-8:
                return int(fin)
            else:
                return -1
        N=int(n)
        k=int(math.log(N,2))#以2为底,4的对数
        ans=N-1
        for i in range(k,1,-1):
            #print(i)
            res=fun(i,N)
            if res!=-1:
                ans=res
                break
        return str(ans)

LeetCode 483. 最小好进制--数学分析+二分

上一篇:计算机网络学习之TCP3次握手,4次挥手及http协议学习


下一篇:网络协议和配置IP地址