k 镜像数字的和
难度:
标签:
题目描述
A k-mirror number is a positive integer without leading zeros that reads the same both forward and backward in base-10 as well as in base-k.
- For example,
9is a 2-mirror number. The representation of9in base-10 and base-2 are9and1001respectively, which read the same both forward and backward. - On the contrary,
4is not a 2-mirror number. The representation of4in base-2 is100, which does not read the same both forward and backward.
Given the base k and the number n, return the sum of the n smallest k-mirror numbers.
Example 1:
Input: k = 2, n = 5
Output: 25
Explanation:
The 5 smallest 2-mirror numbers and their representations in base-2 are listed as follows:
base-10 base-2
1 1
3 11
5 101
7 111
9 1001
Their sum = 1 + 3 + 5 + 7 + 9 = 25.
Example 2:
Input: k = 3, n = 7
Output: 499
Explanation:
The 7 smallest 3-mirror numbers are and their representations in base-3 are listed as follows:
base-10 base-3
1 1
2 2
4 11
8 22
121 11111
151 12121
212 21212
Their sum = 1 + 2 + 4 + 8 + 121 + 151 + 212 = 499.
Example 3:
Input: k = 7, n = 17 Output: 20379000 Explanation: The 17 smallest 7-mirror numbers are: 1, 2, 3, 4, 5, 6, 8, 121, 171, 242, 292, 16561, 65656, 2137312, 4602064, 6597956, 6958596
Constraints:
2 <= k <= 91 <= n <= 30
代码结果
运行时间: 740 ms, 内存: 139.6 MB
/*
题目思路：
1. 使用流操作来生成数字序列并筛选k镜像数字。
2. 判断一个数字是否是十进制和k进制下的镜像数字。
3. 使用流操作将前n个k镜像数字的和计算出来。
*/
import java.util.stream.IntStream;
public class KMirrorNumbersStream {
// 判断是否是回文数字
public static boolean isPalindrome(String s) {
int left = 0, right = s.length() - 1;
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
// 转换成k进制并判断是否是镜像数字
public static boolean isKMirror(int num, int k) {
String baseK = Integer.toString(num, k);
return isPalindrome(baseK);
}
public static long sumKMirrorNumbers(int k, int n) {
return IntStream.iterate(1, i -> i + 1)
.filter(num -> isPalindrome(String.valueOf(num)) && isKMirror(num, k))
.limit(n)
.asLongStream()
.sum();
}
public static void main(String[] args) {
int k = 2, n = 5;
System.out.println(sumKMirrorNumbers(k, n)); // 输出 25
}
}
解释
方法:
该题解的核心是生成并检验k镜像数字。首先，使用一个递归函数`gen_ans`生成长度为`i`的所有可能的k进制数，这些数的特点是从两边向中间对称。然后，逐个检验这些数是否也是十进制下的镜像数字。如果是，累加它们的十进制值，并计数。当找到足够的k镜像数字时，返回它们的和。
时间复杂度:
O(k^i * d)，其中i是最大的数字长度，d是数字的位数
空间复杂度:
O(k^i)，其中i是最大的数字长度
代码细节讲解
🦆
在递归函数`gen_ans`中，如何确保生成的k进制数确实是对称的？具体的对称构造逻辑是什么？
▷🦆
为什么在检验十进制镜像数字时，需要特别判断生成的k进制数的首位不为'0'？
▷🦆
题解中提到了递归深度为101，这个数字是如何确定的？是否有可能存在更优的深度选择？
▷