資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學在C++中查詢最接近的迴文數
假設我們有一個數字n，我們需要找到最接近它的迴文數。這個迴文數可以小於或大於n，只要其絕對差值最小即可。例如，如果數字是145，則結果將是141。
為了解決這個問題，我們將遵循以下步驟：
- sn := n的位數
- 如果sn等於1，則：
- 將n[0]減1，並返回一個長度為n[0]的由1組成的字串
- half_sn := (sn + 1) / 2
- half_val := 將n從索引0到half_sn的子串轉換為整數
- 定義一個數組candidates = {10^(sn) – 1, 10^(sn - 1) - 1, 10^(sn - 1) + 1, 10^(sn)+1}
- 定義一個數組fmdc = { half_val, half_val - 1, half_val + 1 }
- 對於fmdc中的每個值c：
- rev := 將c轉換為字串
- 如果sn模2不為零，則：
- 刪除rev的最後一個元素
- 反轉陣列rev
- 將c新增到candidates陣列的末尾
- 對candidates陣列進行排序
- val := 將n轉換為整數
- 對於candidates中的每個候選值：
- 如果候選值等於val，則：
- 忽略以下部分，跳過到下一個迭代
- diff := abs|候選值 – val|
- 如果diff < min_diff，則：
- min_diff := diff
- ans := 將候選值轉換為字串
- 如果候選值等於val，則：
- 返回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
更新於：2020年6月1日
178 次檢視
廣告