Tìm Palindrome gần nhất trong C ++

Giả sử chúng ta có một số n, chúng ta phải lấy số gần nhất là palindrome. Vì vậy, palindrome có thể nhỏ hơn hoặc lớn hơn số có hiệu số tuyệt đối nhỏ hơn. Vì vậy, nếu số giống như 145, thì kết quả sẽ là 141.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• sn:=kích thước của n
• nếu sn bằng 1 thì -
  • giảm n [0] đi 1 và trả về chuỗi 1s có kích thước n [0]
• half_sn:=(sn + 1) / 2
• half_val:=stol (chuỗi con của n từ chỉ mục 0 đến half_sn
• Xác định ứng viên mảng ={10 ^ (sn) - 1, 10 ^ (sn - 1) - 1, 10 ^ (sn - 1) + 1, 10 ^ (sn) +1
• Xác định mảng fmdc ={half_val, half_val - 1, half_val + 1}
• cho mỗi giá trị c trong fmds
  • rev:=chuyển đổi c thành chuỗi
  • nếu sn mod 2 khác 0, thì -
    • xóa phần tử cuối cùng khỏi phiên bản
  • đảo ngược vòng quay của mảng
  • chèn c vào cuối ứng viên
• sắp xếp các ứng viên mảng
• val:=n dưới dạng số nguyên
• cho từng ứng viên trong các ứng cử viên -
  • nếu ứng cử viên giống với val, thì -
    • Bỏ qua phần sau, chuyển sang phần lặp tiếp theo
  • diff:=abs | ứng cử viên - val |
  • nếu diff
  • min_diff:=diff
  • ans:=chuyển đổi ứng viên thành chuỗi

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   string nearestPalindromic(string n) {
      int sn = n.size();
      if(sn == 1){
      return string(1, --n[0]);
   }
   int half_sn = (sn+1)/2;
   long half_val = stol(n.substr(0, half_sn));
   vector<long> candidates = {pow(10, sn)-1, pow(10, sn-1)-1, pow(10, sn-1)+1, pow(10, sn)+1};
   vector <long> fmdc = {half_val, half_val-1,half_val+1};
   for(long c:fmdc){
      string rev = to_string(c);
      if(sn%2)rev.pop_back();
      reverse(rev.begin(),rev.end());
      candidates.push_back(stol(to_string(c) + rev));
   }
   sort(candidates.begin(), candidates.end());
   string ans;
   long val = stol(n), min_diff = INT_MAX;
   for(long candidate : candidates){
      if(candidate == val)continue;
      long diff = labs(candidate - val);
      if(diff < min_diff){
         min_diff = diff;
         ans = to_string(candidate);
         }
      }
      return ans;
   }
};
main(){
   Solution ob;
   cout << (ob.nearestPalindromic("145"));
}

Đầu vào

“145”

Đầu ra

141