网站建设温州,怎么做类似美团的网站吗,深圳专业网站设计公司,做海外推广的公司本文涉及知识点
数论#xff1a;质数、最大公约数、菲蜀定理
LeetCode880. 索引处的解码字符串
给定一个编码字符串 s 。请你找出 解码字符串 并将其写入磁带。解码时#xff0c;从编码字符串中 每次读取一个字符 #xff0c;并采取以下步骤#xff1a; 如果所读的字符是…本文涉及知识点
数论质数、最大公约数、菲蜀定理
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 109 题目保证 k 小于或等于解码字符串的长度。 解码后的字符串保证少于 263 个字母。
数论
str记录所有字符串int数组d记录所有数字。比如ab3e1则str {“ab”,“e”},d {3,1}。 long long数组len[i]记录各操作后的字符串的长度。 len[0]0 { l e n [ 2 i 1 ] l e n [ 2 i ] s t r [ i ] . l e n g t h 奇数 l e n [ 2 i 2 ] l e n [ 2 i 1 ] ∗ d [ i ] 偶数 \begin{cases} len[2i1] len[2i] str[i].length 奇数\\ len[2i2] len[2i1]*d[i] 偶数\\ \end{cases} {len[2i1]len[2i]str[i].lengthlen[2i2]len[2i1]∗d[i]奇数偶数 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();vectorstring strs;vectorint 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);}vectorlong 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]);}functionchar(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 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
