https://leetcode-cn.com/problems/find-the-closest-palindrome/
hard题 有点难 自己想了半天没想明白 看y总的思路明白了这道题
属于脑筋急转弯类型的题
给定一个数 求最近的回文数 可大可小 绝对值最小 若有两个相同的 返回较小的那个
思路：根据一个数的前半段进行构造 直接构造回文数
给定 12345 构造成 12321 12421 12221
比如给的12345 最近的是12321 但是给定12399 最近的就是12421
但是如果给定19911 最近的反而是19891
所以说就是这三个数 但是不仅仅是这三个数字 还有两种特殊情况
比如9999 最接近的不是100001 这样会多一位 应该是10001
同理1001 最近的也不是99 而是999
所以一共是五个数 上面三个加上pow(10,n)+1和pow(10,n-1)-1
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
39
40
41
42
43
44
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
class Solution
{
public:
string nearestPalindromic(string n)
{
//寻找最近的数
int len = n.size();
set<ll> st;
//如9999 最近的是10001
st.insert((ll)pow(10, len) + 1);
//如10000 最近的有10001和9999 但是要返回较小的
st.insert((ll)pow(10, len - 1) - 1);
//截取前一半 先不管是长度为奇数还是偶数
ll m = stoll(n.substr(0, (len + 1) / 2));
//将三个数加到set中
for (ll i = m - 1; i <= m + 1; i++)
{
//构造回文数
//区分一下偶数还是技术
string a=to_string(i),b=a;
reverse(b.begin(),b.end());
if(len%2){
st.insert(stoll(a+b.substr(i)));
}else{
st.insert(stoll(a+b));
}
}
//由于set内部自动排序 所以两数绝对值之差相等时，会返回较小的
ll k=stoll(n);
//防止数字本身是回文数的情况
st.erase(k);
ll ans=LONG_LONG_MAX;
for(ll i:st){
if(abs(i-k)<abs(ans-k)){
ans=i;
}
}
return to_string(ans);
}
};
|