483. Smallest Good Base

mikasa 发布于2019-08-19 10:45 / 1902人阅读

摘要：题目链接，但是不是结果，而是幂。方法特别巧妙，另外求幂的和还可以优化用快速幂来求。知道幂之后，根据逼近法，可以得到，幂的最大值是，当然这个是的时候。注意求不能直接用因为里面和的转换过程中会丢失信息，所以要用乘来做。

483. Smallest Good Base

题目链接：https://leetcode.com/problems...

enumerate，但是不是结果，而是幂。方法特别巧妙，另外求幂的和还可以优化用快速幂来求。知道幂之后，根据逼近法，可以得到base：k = logm(n) = (long) (pow(n, 1/m)) = (long) (log(n) / log(m))，幂的最大值是min(log2(n), 64)，当然这个是m>1的时候。注意求pow(base, m)不能直接用pow因为java里面double和long的转换过程中会丢失信息，所以要用乘来做。
参考这个博客：
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;
    }
}

另外题目标签是binary search，应该是对k的取值可以用binary search来找。

云服务器 GPU云服务器 Smallest Good good域名 BASE

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/76401.html

一些做着玩的题

摘要：这是我在平时有时间的时候做的一些算法上的题目想看更新请移步这里题目描述解法这个问题当时拿到的时候是完全没有思路的，后面上网查询了一下这个题目，知道了使用斐波那契数列就能够解这道题目，，，当然百度作业帮上面也有相应的解法，套路就是题目为一这是我在平时有时间的时候做的一些算法上的题目想看更新请移步这里题目： Climbing Stairs 描述 You are climbing a ...

cheukyin 2019-08-20 13:57 评论0 收藏0
怎么用多模型数据库为复杂数据建模？--航空舰队实例

摘要： 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...

tianhang 2019-08-20 17:47 评论0 收藏0
怎么用多模型数据库为复杂数据建模？--航空舰队实例

摘要： 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...

xingqiba 2019-06-28 15:52 评论0 收藏0
【译】JavaScript最全编码规范

摘要：在中已经澄清分号恩，这也是规范一部分阅读更多类型分配强制转换执行强制类型转换的语句。对于整型值大于位的进行位运算将导致不可预见的行为。在范围内使用进行对象查询译文出处类型基本类型：访问基本类型时，应该直接操作类型值 string number boolean null undefined javascriptvar foo = 1; var bar = foo; bar ...

afishhhhh 2019-08-21 10:30 评论0 收藏0