【C++数论】880. 索引处的解码字符串|2010

本文涉及知识点

数论：质数、最大公约数、菲蜀定理

LeetCode880. 索引处的解码字符串

给定一个编码字符串 s 。请你找出 解码字符串 并将其写入磁带。解码时，从编码字符串中 每次读取一个字符 ，并采取以下步骤：
如果所读的字符是字母，则将该字母写在磁带上。
如果所读的字符是数字（例如 d），则整个当前磁带总共会被重复写 d-1 次。
现在，对于给定的编码字符串 s 和索引 k，查找并返回解码字符串中的第 k 个字母。
示例 1：
输入：s = “leet2code3”, k = 10
输出：“o”
解释：
解码后的字符串为 “leetleetcodeleetleetcodeleetleetcode”。
字符串中的第 10 个字母是 “o”。
示例 2：
输入：s = “ha22”, k = 5
输出：“h”
解释：
解码后的字符串为 “hahahaha”。第 5 个字母是 “h”。
示例 3：
输入：s = “a2345678999999999999999”, k = 1
输出：“a”
解释：
解码后的字符串为 “a” 重复 8301530446056247680 次。第 1 个字母是 “a”。
提示：
2 <= s.length <= 100
s 只包含小写字母与数字 2 到 9 。
s 以字母开头。
1 <= k <= 10⁹
题目保证 k 小于或等于解码字符串的长度。
解码后的字符串保证少于 2⁶³ 个字母。

数论

str记录所有字符串，int数组d记录所有数字。比如：ab3e1，则str = {“ab”,“e”},d = {3,1}。
long long数组len[i]记录各操作后的字符串的长度。
len[0]=0
$$\{\begin{array}{llc}len[2i+1]=len[2i]+str[i].length& & 奇数\\ len[2i+2]=len[2i+1]\ast d[i]& & 偶数\end{array}$$
f(x)函数的定义：
len[i1] > x ，且i1最小
如果i1是奇数,return str[i1/2][x-len[i1-1]]。
如果i1是偶数：return f(x % len[i1-1])。
最终调用：f(k-1)。

代码

核心代码

class Solution {
		public:
			string decodeAtIndex(string s, int k) {
				const int N = s.length();
				vector<string> strs;
				vector<int> d;
				for (int i = 0; i < N;) {
					string str;
					while ((i < N) && isalpha(s[i])) {
						str += s[i]; i++;
					}
					strs.emplace_back(str);
					if ((i < N) && isdigit(s[i])) {
						d.emplace_back(s[i] - '0'); i++;
					}
				}
				if (d.size() < strs.size()) {
					d.emplace_back(1);
				}
				vector<long long> lens = { 0 };
				for (int i = 0; i < strs.size(); i++) {
					lens.emplace_back(lens.back() + strs[i].length());
					lens.emplace_back(lens.back() * d[i]);
				}
				function<char(int)> f = [&](long long x) {
					int i1 = upper_bound(lens.begin(), lens.end(), x)-lens.begin();
					if (i1 & 1) {
						return strs[i1 / 2][x - lens[i1 - 1]];
					}
					return f(x % lens[i1 - 1]);
				};
				return string(1,f(k - 1));
			}
		};

单元测试

string s;
		int k;
		TEST_METHOD(TestMethod1)
		{
			s = "a1", k = 1;
			auto res = Solution().decodeAtIndex(s, k);
			AssertEx(string("a"), res);
		}
		TEST_METHOD(TestMethod2)
		{
			s = "abc", k = 1;
			auto res = Solution().decodeAtIndex(s, k);
			AssertEx(string("a"), res);
		}
		TEST_METHOD(TestMethod11)
		{
			s = "leet2code3", k = 10;
			auto res = Solution().decodeAtIndex(s,k);
			AssertEx(string("o"), res);
		}
		TEST_METHOD(TestMethod12)
		{
			s = "ha22", k = 5;
			auto res = Solution().decodeAtIndex(s, k);
			AssertEx(string("h"), res);
		}
		TEST_METHOD(TestMethod13)
		{
			s = "a2345678999999999999999", k = 1;
			auto res = Solution().decodeAtIndex(s, k);
			AssertEx(string("a"), 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++**实现。