[LeetCode]Find the Closest Palindrome

这道题思路并不复杂，主要是实现比较麻烦，需要考虑各种各样的情况。那么首先可以明确的一点是，对于一个数，我们要寻找大于它的最小回文prev和小于它的最大回文next。这里面差值最小的那个就是答案。这里面有几种情况：

• 直接用前半部分镜像生成，比如1234->1221(prev)，35212->35253(next)
• 用前半部分+1镜像生成，比如1234->1331(next), 345->353(next)
• 用前半部分-1镜像生成，比如1200->1111(prev), 341->333(prev)

所以我们需要生成这三个数，然后取差值最小的。需要注意的是，这里面有几种情况我们需要特殊处理：

• 当用前半部分+1的时候位数变多了并且当前数长度为偶数，比如99，我们取前半部分9，9+1 = 10，这时候我们就需要生成奇数长度101而不是1001
• 当用前半部分+1的时候位数变多了并且当前数长度为奇数，比如999，我们取前半部分99，99+1 = 100，我们需要抹去最后一位变为10，并且生成偶数长度1001
• 当用前半部分-1的时候位数变少了并且当前数长度为偶数，比如1000，我们取前半部分10，10 - 1= 9，这时候我们要额外在末尾补9，并且生成奇数长度999
• 用前半部分-1的时候位数变少了并且当前数长度为奇数，比如100，我们取前半部分10，10 - 1= 9，这时候我们要生成偶数长度99

假设输入string长度为L，O(L)时间就可以做到并且不需要额外空间，代码如下：

	class Solution {
	public:
	string nearestPalindromic(string n) {
	int len = n.size();
	long num = stol(n);
	bool odd = len % 2;
	if (n == "10" || n == "11")return "9";
	//general case
	string half1 = n.substr(0, (len + 1) / 2), half2 = to_string(stol(half1) + 1), half3 = to_string(stol(half1) - 1);
	//handle special case, e.g. 1000, 998
	bool diffSize2 = false, diffSize3 = false;
	if (half2.size() > half1.size()) { if(odd)half2.pop_back(); diffSize2 = true; }
	if (half1.size() > half3.size()) { if(!odd)half3.push_back('9'); diffSize3 = true; };
	string res1 = mirror(half1, odd);
	string res2 = mirror(half2, diffSize2 ? !odd : odd);
	string res3 = mirror(half3, diffSize3 ? !odd : odd);
	long diff1 = abs(num - stol(res1)), diff2 = abs(num - stol(res2)), diff3 = abs(num - stol(res3));
	if (!diff1)return diff3 <= diff2 ? res3 : res2;
	auto minDiff = min(diff1, min(diff2, diff3));
	if (minDiff == diff3)return res3;
	else if (minDiff == diff1)return res1;
	else return res2;
	}
	private:
	string mirror(string s, bool odd)
	{
	int len = s.size();
	string rev = odd ? s.substr(0, len - 1) : s;
	reverse(rev.begin(), rev.end());
	return s + rev;
	}
	};

view raw Find the Closest Palindrome.cpp hosted with ❤ by GitHub