自从进了C++的组，我的Java生了，然而C++还不够熟。偶尔想做下算法题娱乐一下但C++就是拦路虎，简直不会刷题了有点尴尬。
这道题寻找最近的回文数，这道题基本是考验认知能力的，看你现场分析问题解决问题的能力，没有太多套路。
就是要好好分析找出规律然后写出干净的code.
最brute force的解法是我沿着这个数向上一路找找到第一个比它大的回文数，再向下找找到第一个比它小的回文数。然后两个比较一下。这个时间复杂度比较高。
对于回文数，我们可以采用构建的方式来做。
对于一个数，把它从中间劈成两半，
- 一个回文数的前一半和后一半一定是对称的，所以我们可以合成回文数
- 如果找最近的回文数，则尽量改动后一半和前一半match。
- 我们有三个candidate，就是
a. 前一半， + 前一半翻转 合成一个数
b. 前一半+1, + （前一半+1,翻转）合成
c. 前一半-1, + （前一半-1,翻转) 合成
举例1: 3456
a : 3443
b : 3553
c : 3333
举例2: 34567
a : 34543
b : 34643
c : 34443
但如果这数是1000这种， 前一半减1就是9, 合成数是99,明显不对， 所以这种情况下，最近是数是比它小的位的全是9的。
同理我们还要考虑9999这种。
所以一共有五种情况需要考虑。
代码如下，对我最challenge的地方是C++
容易出bug的地方是如果处理长度为奇数的case.
class Solution {
public:
string nearestPalindromic(string n) {
int len = n.size();
long nAsNum = stol(n);
unordered_set<long> s;
s.insert(pow(10, len) + 1);
s.insert(pow(10, len - 1) - 1);
long pre = stol(n.substr(0, (len + 1) / 2));
for (long i = -1; i <= 1; ++i) {
string prefix = to_string(pre + i);
s.insert(stol(prefix + string(prefix.rbegin() + (len % 2), prefix.rend())));
}
s.erase(nAsNum);
long diff = LONG_MAX;
long ans = *(s.begin());
for (long cand : s) {
if (abs(cand - nAsNum) < diff) {
ans = cand;
diff = abs(cand - nAsNum);
} else if (abs(cand - nAsNum) == diff) {
ans = min(cand, ans); // cannot combine the two cases together
}
}
return to_string(ans);
}
};
学习到的C++ 的知识点有
- substr
- reverse a string: string(prefix.rbegin(), prefix.rend())
- stol : convert a string to long
- LONG_MAX
