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