05 August 2008
k 镜像数字的和
一个 k 镜像数字 指的是一个在十进制和 k 进制下从前往后读和从后往前读都一样的 没有前导 0 的 正 整数。
比方说，9 是一个 2 镜像数字。9 在十进制下为 9 ，二进制下为 1001 ，两者从前往后读和从后往前读都一样。 相反地，4 不是一个 2 镜像数字。4 在二进制下为 100 ，从前往后和从后往前读不相同。 给你进制 k 和一个数字 n ，请你返回 k 镜像数字中 最小 的 n 个数 之和 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
示例 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 。
迭代获取下一个对称10进制数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution {
// 得到比 str 大的下一个 10 进制对称的数字，例如 1->2, 4->5, 9->11
public String next(String str) {
int len = str.length();
StringBuilder sb = new StringBuilder();
// 将 str 截断一半，然后 + 1 最后把另一半缺失的数字补齐即可
long num = Long.parseLong(str.substring(0, (len + 1) / 2));
// 发生进位，则表示下一个数字的位数是 len + 1 位， 比如 99 下一个对称数字 101 就发生了进位
if (Long.toString(num + 1).length() != Long.toString(num).length()) {
for (int i = 0; i <= len; i++) {
if (i == 0 || i == len) {
sb.append(1);
} else {
sb.append(0);
}
}
} else {
sb.append(num + 1);
for (int i = (len + 1) / 2; i < len; i++) {
sb.append(sb.charAt(len - 1 - i));
}
}
return sb.toString();
}
public long kMirror(int k, int n) {
long result = 0;
String str = "1";
while (n > 0) {
long i = Long.parseLong(str);
if (symmetry(Long.toString(i, k))) {
result += i;
n--;
}
str = next(str);
}
return result;
}
// 检查字符串是对称
public boolean symmetry(String str) {
int n = str.length();
int s = 0, e = n - 1;
while (s < e) {
if (str.charAt(s) != str.charAt(e)) return false;
s++;
e--;
}
return true;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution {
// Long.toString(int n, int k) 获取数字n的k进制的字符串
// 于是问题的关键在于怎么快速的找到下一个回文数
public long kMirror(int k, int n) {
long res = 0;
String start = "1";
while(n != 0) {
Long cur = Long.parseLong(start);
if(isPaddle(Long.toString(cur, k))) {
res += cur;
n--;
}
start = nextPaddle(start);
}
return res;
}
// 找到比s大的第一个回文数
// 想法是把当前的数给截半，比如当前的数是121，那么下一个回文数是131
// 做法就是将121 变成12 将12加1，变成13，再把后面的部分补齐即可
// 对于99的下一个回文数应该是101，具体为将99变成9， 然后加一得到10，然后补全
public String nextPaddle(String s) {
int n = s.length();
StringBuilder sb = new StringBuilder();
// 截取一半，注意substring(int i, int j)截取的是[i, j),所以需要加一
long num = Long.parseLong(s.substring(0, (n + 1) / 2));
// 如果当前是9的话，那么加1的话会产生进位,也就是99的下一个回文数为101
if(Long.toString(num + 1).length() != Long.toString(num).length()) {
for(int i = 0; i <= n; i++) {
if(i == 0 || i == n) {
sb.append('1');
}else {
sb.append('0');
}
}
}else {//不发生进位的话，形如121变成131
sb.append(num + 1);
for(int i = (n + 1)/2; i < n; i++){
sb.append(sb.charAt(n - 1 - i));
}
}
return sb.toString();
}
// 判断是否是回文数
public boolean isPaddle(String x) {
int n = x.length();
for(int i = 0; i < n / 2; i++) {
if(x.charAt(i) != x.charAt(n - i - 1)) {
return false;
}
}
return true;
}
}