【回溯】2081. k 镜像数字的和

本文涉及知识点

枚举 回溯 回溯知识汇总

LeetCode2081. k 镜像数字的和

一个 k 镜像数字 指的是一个在十进制和 k 进制下从前往后读和从后往前读都一样的 没有前导 0 的 正 整数。
比方说，9 是一个 2 镜像数字。9 在十进制下为 9 ，二进制下为 1001 ，两者从前往后读和从后往前读都一样。
相反地，4 不是一个 2 镜像数字。4 在二进制下为 100 ，从前往后和从后往前读不相同。
给你进制 k 和一个数字 n ，请你返回 k 镜像数字中 最小 的 n 个数 之和 。
示例 1：
输入：k = 2, n = 5
输出：25
解释：
最小的 5 个 2 镜像数字和它们的二进制表示如下：
十进制 二进制
1 1
3 11
5 101
7 111
9 1001
它们的和为 1 + 3 + 5 + 7 + 9 = 25 。
示例 2：
输入：k = 3, n = 7
输出：499
解释：
7 个最小的 3 镜像数字和它们的三进制表示如下：
十进制 三进制
1 1
2 2
4 11
8 22
121 11111
151 12121
212 21212
它们的和为 1 + 2 + 4 + 8 + 121 + 151 + 212 = 499 。
示例 3：
输入：k = 7, n = 17
输出：20379000
解释：17 个最小的 7 镜像数字分别为：
1, 2, 3, 4, 5, 6, 8, 121, 171, 242, 292, 16561, 65656, 2137312, 4602064, 6597956, 6958596
提示：
2 <= k <= 9
1 <= n <= 30

枚举

从1位开始枚举所有镜像数字，看是否是10进制的镜像数组。
结果是long long，说明不超过64位。
或者 n=30，k从1到9，看是否溢出。
首位不能是0，包括1位数。
下面以奇数位为例来说明，回溯。两个参数：vector path,int leve。
如果已经发现的数超过n，返回。
如果leve >= path.size 处理path 并返回。
如果0 == leve，path[leve] 1到k-1，BackTrack(path,leve+1)
否则,path[leve]0到k-1，BackTrack(path,leve+1)

奇数位处理path

tmp = path + 转置(path[0…n-2])再转成10进制，再转成字符串，看是否是回文(镜像数字)。
可以不生成tmp，直接转。

偶数位处理

tmp = path + 转置(path)再转成10进制，再转成字符串，看是否是回文(镜像数字)。
可以不生成tmp，直接转。

用到的函数

path 转10进制，并判断是否是回文。

代码

核心代码

class Solution {
public:
	long long kMirror(int k, int n) {
		int cnt = 0;
		long long sum = 0;
		vector<int> path;		
		for (int bit = 1;cnt < n; bit++) {
			auto Do = [&]() {
				bool bOdd = 1 & bit;
				long long num = 0;
				for (const auto& n : path) {
					num = k * num + n;
				}
				for (int i = path.size() - 1 - bOdd; i >= 0; i--) {
					num = k * num + path[i];
				}
				string str = to_string(num);
				for (int i = 0; i < str.length() / 2; i++) {
					if (str[i] != str[str.length() - 1 - i]) { return; }
				}
				cnt++;
				sum += num;
			};
			std::function<void(int)> BackTrack = [&](int leve) {
				if (cnt >= n) { return; }
				if (path.size() == leve) {
					Do();
					return;
				}
				for (int i = (0 == leve); i < k; i++) {
					path[leve] = i;
					BackTrack(leve + 1);
				}
			};

			path.resize((bit+1)/2);
			BackTrack(0);
		}
		return sum;		
	}
};

单元测试

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
{
	int k,n;
	TEST_CLASS(UnitTest)
	{
	public:

		TEST_METHOD(TestMethod0)
		{
			k = 2, n = 5;
			auto res = Solution().kMirror(k, n);
			AssertEx(25LL, res);
		}
		TEST_METHOD(TestMethod1)
		{
			k = 3, n = 7;
			auto res = Solution().kMirror(k, n);
			AssertEx(499LL, res);
		}
		TEST_METHOD(TestMethod2)
		{
			k = 7, n = 17;
			auto res = Solution().kMirror(k, n);
			AssertEx(20379000LL, res);
		}
	};
}

扩展阅读

视频课程

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

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

相关推荐

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。