【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{cases} len[2i+1] = len[2i] + str[i].length && 奇数\\ len[2i+2] = len[2i+1]*d[i] && 偶数\\ \end{cases}$
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);
		}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功