X

LEETCODE 2081. k 镜像数字的和 解题思路分析

题目大意:

k 镜像数字的和

一个 k 镜像数字 指的是一个在十进制和 k 进制下从前往后读和从后往前读都一样的 没有前导 0 整数。

比方说,9 是一个 2 镜像数字。9 在十进制下为 9 ,二进制下为 1001 ,两者从前往后读和从后往前读都一样。
相反地,4 不是一个 2 镜像数字。4 在二进制下为 100 ,从前往后和从后往前读不相同。

给你进制 k 和一个数字 n ,请你返回 k 镜像数字中 最小n 个数 之和

示例 1:

输入:k = 2, n = 5
输出:25
解释:
最小的 5 个 2 镜像数字和它们的二进制表示如下:
  十进制       二进制
    1          1
    3          11
    5          101
    7          111
    9          1001
它们的和为 1 + 3 + 5 + 7 + 9 = 25 。

示例 2:

输入:k = 3, n = 7
输出:499
解释:
7 个最小的 3 镜像数字和它们的三进制表示如下:
  十进制       三进制
    1          1
    2          2
    4          11
    8          22
    121        11111
    151        12121
    212        21212
它们的和为 1 + 2 + 4 + 8 + 121 + 151 + 212 = 499 。

示例 3:

输入:k = 7, n = 17
输出:20379000
解释:17 个最小的 7 镜像数字分别为:
1, 2, 3, 4, 5, 6, 8, 121, 171, 242, 292, 16561, 65656, 2137312, 4602064, 6597956, 6958596

提示:

  • 2 <= k <= 9
  • 1 <= n <= 30

解题思路分析:

一开始打算直接暴力求解,从十进制的数字1开始向后循环,找到前n个10进制和k进制都是镜像的数字为止,但遗憾TLE超时了。不过仔细想一下,本题我们完全可以在这个暴力算法的基础上稍加优化即可。我们分析一下暴力算法超时的原因,无外乎就是循环次数多过嘛!试想我们从数字1向后循环查找满足条件的n个数字,如果第n个数字是亿级别的话,就代表我们要循环上亿次才行,我在之前的文章有过说明,leetcode大部分的题目尽量在百万次级别范围内解决问题,否则大概率会发生TLE超时问题。那么本题我们该如何优化才好呢?

我们采用暴力算法的核心目的就是找出前N个符合条件的数字,所以我们不如反过来思考,直接先构造出符合条件的十进制数字,然后再从中筛选出符合条件的k进制数字,即可大大缩减循环次数。接下来重点说下如何构造十进制的镜像数字。

基本思路是,对于一个偶数位的数字,要保证他的前n/2位和后n/2对称,而奇数位的数字则是中间位之外的两部分对称。有了这个基础,对于任意位数的数字,我们按顺序循环出他前n/2位的数字,然后,后半部分通过镜像生成,这样就可以手动按顺序构造出所有十进制的镜像数字。比如4位数字,我们循环长度为2的所有数字,即10-99,然后镜像每个数字,10可以构造为1001,25可以构造位2552。再比如要构造5位数字,由于5是奇数,中间位不需要镜像,因此我们先找出所有3位数,即100-999,这时,最后一位(原长度的中间位)不需要镜像,因此123可以构造出12321,而476可以构造出47674。为了保证顺序,我们从1位数字开始构造,接下来是2位,3位数字等等,每构造出一个数字,我们就马上查看其k进制是否也是镜像数字,如果是,将其累加至返回结果。直到找到n个为止。

实现代码:

class Solution {
    public long kMirror(int k, int n) {
        long res=0; // 返回结果
        int length=1; // 从1位数开始
        while(n>0){ // 找到n个满足条件的数字为止
            int hl = length % 2 == 0 ? length / 2 : length / 2 + 1; // 当前数字长度的一半
            // 当前长度一半数字的最大值,
            // 比如长度为5时,一半长度是2,2位数最大是99,这里我们取100
            long max = (int)Math.pow(10, hl);
            long min = (int)Math.pow(10, hl-1); // 当前长度一半数字的最小值
            for(long i=min;i<max;i++){ // 循环范围内的每一个数字
                long num = i; // 备份当前数字
                long mirrorNum = i; // 要构建的镜像数字
                if(length % 2 == 1){ // 如果当前长度是奇数,中间那位上的数字无需镜像
                    num /= 10; // 去除最后一位
                }
                while(num>0){ // 由低到高循环取得每一位,并添加到末尾
                    mirrorNum = mirrorNum * 10 + num % 10; // 将当前最低位添加到数字末尾
                    num /= 10; // 向前进一位
                }
                if(isMirror(mirrorNum, k)){ // 判断当前数字的k进制是否也是镜像数字
                    res+=mirrorNum; // 如果是则累加至返回结果
                    n--; // 个数减一
                    if(n == 0) break; // 个数为0时,已找到全部数字,退出。
                }
            }
            length++;
        }
        return res;
    }
    
    boolean isMirror(long num, int k){
        long n = num;
        long reverse = 0;
        while(n>0){
            reverse = reverse * k + n % k;
            n /=k;
        }
        return reverse == num;
    }
}

本题解法执行时间为879ms。

Runtime: 879 ms, faster than 50.00% of Java online submissions for Sum of k-Mirror Numbers.Memory Usage: 37.8 MB, less than 75.00% of Java online submissions for Sum of k-Mirror Numbers.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-2081-k-镜像数字的和-解题思路分析/
Categories: leetcode
kwantong: