【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++**实现。