564_寻找最近的回文数

难度：困难

题目

给定一个表示整数的字符串 n ，返回与它最近的回文整数（不包括自身）。如果不止一个，返回较小的那个。

“最近的”定义为两个整数差的绝对值最小。

示例

示例一：

输入: n = “123”
输出: “121”

示例二：

输入: n = “1”
输出: “0”
解释: 0 和 2是最近的回文，但我们返回最小的，也就是 0。

提示

  • 1 <= n.length <= 18
  • n 只由数字组成
  • n 不含前导 0
  • n 代表在 [1, 10^18 - 1] 范围内的整数

解题

寻找最近的回文数，最直观的想法就是将字符串的前半段复制到后半段12345 => 12321 ，但是考虑到有的前半段复制过来不一定是最近的回文数，比如 12499 => 12421 12499 =>12521, 很明显 12521 比 12421 离 12499 更近，所以将前半段加一或者减一的结果也考虑进来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
long t = Long.parseLong(n.substring(0,(len+1)/2));
for(long i = t-1; i<=t+1; i++){
  long temp = -1;
  if(len%2==0){
    // 偶数长度的情况
    temp = getNum(i, true);
  }else{
    // 奇数长度的情况
    temp = getNum(i, false);
  }
  if(temp!=curr){
    set.add(temp);
  }
}

将前半段复制到后半段的函数

1
2
3
4
5
6
7
8
9
long getNum(long k, boolean isEven){
  StringBuilder sb = new StringBuilder();
  sb.append(k);
  int index = isEven? sb.length()-1:sb.length()-2;
  while (index>=0){
    sb.append(sb.charAt(index--));
  }
  return Long.parseLong(sb.toString());
}

对于边界值也需要进行处理，如 99999 和 100001 也是回文数，可以单独进行检测

1
2
3
4
int len = n.length();
Set<Long> set = new HashSet<>();
set.add((long)Math.pow(10,len-1)-1);    // 99999
set.add((long)Math.pow(10,len)+1);      // 100001

最终代码

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
public String nearestPalindromic(String n){
  int len = n.length();
  long curr = Long.parseLong(n);
  Set<Long> set = new HashSet<>();
  set.add((long)Math.pow(10,len-1)-1); 
  set.add((long)Math.pow(10,len)+1);  
  long t = Long.parseLong(n.substring(0,(len+1)/2));
  for (long i = t-1; i<= t+1; i++){
    long temp = -1;
    if (len%2==0){
      // 如果为偶数长度
      temp = getNum(i,true);
    }else {
      temp = getNum(i,false);
    }
    if (temp!=curr) set.add(temp);
  }

  long ans = -1;
  for (long i:set){
    if (ans == -1) ans = i;
    else if (Math.abs(i-curr)<Math.abs(ans-curr)) ans = i;
    else if (Math.abs(i-curr)==Math.abs(ans-curr)&& i<ans) ans = i;
  }
  return String.valueOf(ans);
}

long getNum(long k, boolean isEven){
  StringBuilder sb = new StringBuilder();
  sb.append(k);
  int index = isEven? sb.length()-1:sb.length()-2;
  while (index>=0){
    sb.append(sb.charAt(index--));
  }
  return Long.parseLong(sb.toString());
}