首页 > itarticle > palindrome

palindrome

admin 11月 13, 2020 0

Palindrome

LC 564. Find the Closest Palindrome

Given an integer n, find the closest integer (not including itself), which is a palindrome.

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

Example 1:

Input: “123”
Output: “121”

  • Idea: two kinds of solution
    • the result has the same length as the input string
      • get first half of the string, if the length of string is odd, then the first half should include the middle letter. -> reverse the first half of the string(this time we should exclude the middle letter if the string has one). -> link them
      • example : string 23456 -> first half : 234 -> reverse : 32 -> link 23432
    • the result has the different length with the input string
      • there are only 4 cases
      • example: input 999 -> len = 3 -> 10^3 - 1 = 999, 10^3 + 1 = 1001, 10^2-1 = 99, 10^2 + 1 = 101
  • Corner cases
    • length = 1: return the number - 1
    • the result set should not include the input
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
 
void (vector<long>& res, string halfn, int len){
   long halfnl = stol(halfn);
   vector<string> halfs = {to_string(halfnl), to_string(halfnl-1), to_string(halfnl+1)};
   for(string half : halfs){
       string h = half;
       if(len % 2 != 0)
           half.pop_back();
       reverse(half.begin(), half.end());
       res.push_back(stol(h+half));
   }
}


string nearestPalindromic(string n) {
   int len = (int)n.length();
   if(len == 1)
       return to_string(stoi(n)-1);
   vector<long> res = {(long)(pow(10, len) - 1), (long)(pow(10, len) + 1), (long)(pow(10, len-1) - 1), (long)(pow(10, len-1) + 1)};
   int halflen = (len + 1) / 2;
   string halfn = n.substr(0, halflen);
   getOtherPalindrom(res, halfn, len);

   long diff = INT_MAX;
   long nl = stol(n);
   long ret;
   for(long r : res){
       if(r == nl)
           continue;
       if(abs(r-nl) < diff){
           diff = abs(r-nl);
           ret = r;
       } else if(abs(r-nl) == diff){
           if(r < ret)
               ret = r;
       }
   }
   return to_string(ret);
}
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能