Question

564. Find the Closest Palindrome

中文文档

Description

Given a string n representing an integer, return _the closest integer (not including itself), which is a palindrome_. If there is a tie, return _the smaller one_.

The closest is defined as the absolute difference minimized between two integers.

 

Example 1:

Input: n = "123"
Output: "121"

Example 2:

Input: n = "1"
Output: "0"
Explanation: 0 and 2 are the closest palindromes but we return the smallest which is 0.

 

Constraints:

• 1 <= n.length <= 18
• n consists of only digits.
• n does not have leading zeros.
• n is representing an integer in the range [1, 1018 - 1].

Solutions

Solution 1

class Solution:
  def nearestPalindromic(self, n: str) -> str:
    x = int(n)
    l = len(n)
    res = {10 ** (l - 1) - 1, 10**l + 1}
    left = int(n[: (l + 1) >> 1])
    for i in range(left - 1, left + 2):
      j = i if l % 2 == 0 else i // 10
      while j:
        i = i * 10 + j % 10
        j //= 10
      res.add(i)
    res.discard(x)

    ans = -1
    for t in res:
      if (
        ans == -1
        or abs(t - x) < abs(ans - x)
        or (abs(t - x) == abs(ans - x) and t < ans)
      ):
        ans = t
    return str(ans)

class Solution {
  public String nearestPalindromic(String n) {
    long x = Long.parseLong(n);
    long ans = -1;
    for (long t : get(n)) {
      if (ans == -1 || Math.abs(t - x) < Math.abs(ans - x)
        || (Math.abs(t - x) == Math.abs(ans - x) && t < ans)) {
        ans = t;
      }
    }
    return Long.toString(ans);
  }

  private Set<Long> get(String n) {
    int l = n.length();
    Set<Long> res = new HashSet<>();
    res.add((long) Math.pow(10, l - 1) - 1);
    res.add((long) Math.pow(10, l) + 1);
    long left = Long.parseLong(n.substring(0, (l + 1) / 2));
    for (long i = left - 1; i <= left + 1; ++i) {
      StringBuilder sb = new StringBuilder();
      sb.append(i);
      sb.append(new StringBuilder(i + "").reverse().substring(l & 1));
      res.add(Long.parseLong(sb.toString()));
    }
    res.remove(Long.parseLong(n));
    return res;
  }
}

class Solution {
public:
  string nearestPalindromic(string n) {
    long x = stol(n);
    long ans = -1;
    for (long t : get(n))
      if (ans == -1 || abs(t - x) < abs(ans - x) || (abs(t - x) == abs(ans - x) && t < ans))
        ans = t;
    return to_string(ans);
  }

  unordered_set<long> get(string& n) {
    int l = n.size();
    unordered_set<long> res;
    res.insert((long) pow(10, l - 1) - 1);
    res.insert((long) pow(10, l) + 1);
    long left = stol(n.substr(0, (l + 1) / 2));
    for (long i = left - 1; i <= left + 1; ++i) {
      string prefix = to_string(i);
      string t = prefix + string(prefix.rbegin() + (l & 1), prefix.rend());
      res.insert(stol(t));
    }
    res.erase(stol(n));
    return res;
  }
};

func nearestPalindromic(n string) string {
  l := len(n)
  res := []int{int(math.Pow10(l-1)) - 1, int(math.Pow10(l)) + 1}
  left, _ := strconv.Atoi(n[:(l+1)/2])
  for _, x := range []int{left - 1, left, left + 1} {
    y := x
    if l&1 == 1 {
      y /= 10
    }
    for ; y > 0; y /= 10 {
      x = x*10 + y%10
    }
    res = append(res, x)
  }
  ans := -1
  x, _ := strconv.Atoi(n)
  for _, t := range res {
    if t != x {
      if ans == -1 || abs(t-x) < abs(ans-x) || abs(t-x) == abs(ans-x) && t < ans {
        ans = t
      }
    }
  }
  return strconv.Itoa(ans)
}

func abs(x int) int {
  if x < 0 {
    return -x
  }
  return x
}