ค้นหา Palindrome ที่ใกล้ที่สุดใน C ++

สมมุติว่าเรามีตัวเลข n, เราต้องได้จำนวนที่ใกล้เคียงที่สุดคือพาลินโดรม ดังนั้นพาลินโดรมอาจน้อยกว่าหรือมากกว่าจำนวนที่ผลต่างสัมบูรณ์น้อยกว่า ดังนั้นหากตัวเลขเช่น 145 ผลลัพธ์จะเป็น 141

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• sn :=ขนาดของ n
• ถ้า sn เหมือนกับ 1 แล้ว −
  • ลด n[0] ลง 1 และส่งคืนสตริง 1s ของขนาด n[0]
• half_sn :=(sn + 1) / 2
• half_val :=stol(สตริงย่อยของ n จากดัชนี 0 ถึง half_sn
• กำหนดตัวเลือกอาร์เรย์ ={10^(sn) – 1, 10^(sn - 1) - 1, 10^(sn - 1) + 1, 10^(sn)+1
• กำหนดอาร์เรย์ fmdc ={ half_val, half_val - 1, half_val + 1 }
• สำหรับแต่ละค่า c ใน fmds
  • rev :=แปลง c เป็นสตริง
  • ถ้า sn mod 2 ไม่ใช่ศูนย์ ดังนั้น −
    • ลบองค์ประกอบสุดท้ายออกจาก rev
  • ย้อนกลับ rev อาร์เรย์
  • ใส่ c ต่อท้ายผู้สมัคร
• เรียงลำดับตัวเลือกอาร์เรย์
• val :=n เป็นจำนวนเต็ม
• สำหรับผู้สมัครแต่ละคนในผู้สมัคร −
  • ถ้าผู้สมัครเหมือนกับ val แล้ว −
    • ไม่ต้องสนใจตอนต่อไป ข้ามไปที่ตอนต่อไป
  • diff :=abs|candidate – val|
  • ถ้าต่าง
  • min_diff :=diff
  • ans :=แปลงผู้สมัครเป็นสตริง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#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"));
}

อินพุต

“145”

ผลลัพธ์

141