【枚举】564. 寻找最近的回文数

本文涉及知识点

枚举

LeetCode564. 寻找最近的回文数

给定一个表示整数的字符串 n ，返回与它最近的回文整数（不包括自身）。如果不止一个，返回较小的那个。
“最近的”定义为两个整数差的绝对值最小。
示例 1:
输入: n = “123”
输出: “121”
示例 2:
输入: n = “1”
输出: “0”
解释: 0 和 2是最近的回文，但我们返回最小的，也就是 0。
提示:
1 <= n.length <= 18
n 只由数字组成
n 不含前导 0
n 代表在 [1, 10¹⁸ - 1] 范围内的整数

枚举

令 nl = n.length。
如果1 == nl ，返回strig(1,n[0]-1);
half =nl/2
string strMid = (1&ml) ? n[half] : “”;
令 x = atoi(n.sub(0,half));
否则比较如下三个数：
第一个数：x+strMid + x的逆序
第二个数：
$\begin{cases} (x+1)+strMid + (x+1)的逆序 && (x+1)和x的位数相同 \\ 10\cdots 01 ,其中0共有n-1位 &&oher \end{cases}$

第三个数：(x-1) + strMid + (x-1)的逆向
$\begin{cases} (x-1)+strMid + (x-1)的逆序 && (x-1)和x的位数相同，且x-1不为0 \\ 9\cdots 9 ,其中9共有n-1位 &&oher \end{cases}$

当strMid不为空时，枚举0到9，因为本题运算量比较小，可以全部枚举。

代码

核心代码

class Solution {
public:
	string nearestPalindromic(string n) {
		const int nl = n.length();
		const long long llN = atoll(n.c_str());
		if (1 == nl) { return string(1, n[0] - 1); }
		const int half = nl / 2;
		const string strMid = (nl & 1) ? string(1,n[half]) : "";
		string sx = n.substr(0, half);
		long long x = atoll(sx.c_str());
		vector<string> res;
		auto Add1 = [&](long long x,string sMid) {
			string tmp = std::to_string(x);
			string s1 = tmp + sMid + string(tmp.rbegin(), tmp.rend());	
			res.emplace_back(s1);
		};
		if ("" == strMid) {
			Add1(x, "");
		}
		else {
			for (char ch = '0'; ch <= '9'; ch++) {
				Add1(x, string(1, ch));
			}
		}		
		auto Add = [&](int y) {
			string sxa = std::to_string(y);
			if ((0 == y)||(sx.length() > sxa.length())) {
				res.emplace_back(nl - 1, '9');
			}
			else if (sx.length() == sxa.length()) {
				if ("" == strMid) {
					res.emplace_back(sxa  + string(sxa.rbegin(), sxa.rend()));
					return;
				}
				for (char ch = '0'; ch <= '9'; ch++) {
					res.emplace_back(sxa + string(1, ch) + string(sxa.rbegin(), sxa.rend()));
				}
			}
			else {
				res.emplace_back('1' + string(nl - 1, '0') + '1');
			}
		};
		Add(x + 1);
		Add(x - 1);
		vector<long long> vRes;
		for (const auto& s : res) {
			if (s == n) { continue; }
			long long cur = atoll(s.c_str());
			vRes.emplace_back(cur);
		}
		sort(vRes.begin(), vRes.end());
		long long llSub = LLONG_MAX;
		long long llRes = 0;
		for (const auto& cur : vRes) {	
			if (abs(cur - llN) < llSub) {
				llSub = abs(cur - llN);
				llRes = cur;
			}
		}
		return std::to_string(llRes);
	}
};

单元测试

template<class T1,class T2>
void AssertEx(const T1& t1, const T2& t2)
{
	Assert::AreEqual(t1 , t2);
}

template<class T>
void AssertEx(const vector<T>& v1, const vector<T>& v2)
{
	Assert::AreEqual(v1.size(), v2.size());	
	for (int i = 0; i < v1.size(); i++)
	{
		Assert::AreEqual(v1[i], v2[i]);
	}
}

template<class T>
void AssertV2(vector<vector<T>> vv1, vector<vector<T>> vv2)
{
	sort(vv1.begin(), vv1.end());
	sort(vv2.begin(), vv2.end());
	Assert::AreEqual(vv1.size(), vv2.size());
	for (int i = 0; i < vv1.size(); i++)
	{
		AssertEx(vv1[i], vv2[i]);
	}
}

namespace UnitTest
{
	string n;
	TEST_CLASS(UnitTest)
	{
	public:
		TEST_METHOD(TestMethod0)
		{
			n = "123";
			auto res = Solution().nearestPalindromic(n);
			AssertEx(string("121"), res);
		}
		TEST_METHOD(TestMethod1)
		{
			n = "1";
			auto res = Solution().nearestPalindromic(n);
			AssertEx(string("0"), res);
		}
		TEST_METHOD(TestMethod2)
		{
			n = "332";
			auto res = Solution().nearestPalindromic(n);
			AssertEx(string("333"), res);
		}
		TEST_METHOD(TestMethod3)
		{
			n = "100";
			auto res = Solution().nearestPalindromic(n);
			AssertEx(string("99"), res);
		}
		TEST_METHOD(TestMethod4)
		{
			n = "1000";
			auto res = Solution().nearestPalindromic(n);
			AssertEx(string("999"), res);
		}
		TEST_METHOD(TestMethod5)
		{
			n = "99";
			auto res = Solution().nearestPalindromic(n);
			AssertEx(string("101"), res);
		}
		TEST_METHOD(TestMethod6)
		{
			n = "999";
			auto res = Solution().nearestPalindromic(n);
			AssertEx(string("1001"), res);
		}
		TEST_METHOD(TestMethod7)
		{
			n = "11911";
			auto res = Solution().nearestPalindromic(n);
			AssertEx(string("11811"), res);
		}
		TEST_METHOD(TestMethod8)
		{
			n = "11011";
			auto res = Solution().nearestPalindromic(n);
			AssertEx(string("11111"), res);
		}
		TEST_METHOD(TestMethod9)
		{
			n = "88";
			auto res = Solution().nearestPalindromic(n);
			AssertEx(string("77"), res);
		}
	};
}

扩展阅读

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

我想对大家说的话
《喜缺全书算法册》以原理、正确性证明、总结为主。
按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛