大尺度做爰床视频网站,目前还有阳性患者吗最新消息,wordpress和discuz哪个好,智慧园区管理系统问题描述
该问题#xff0c;用最简单的语言描述#xff0c;就是将通过一定规则压缩的字符解压为原始字符#xff0c;举例如下图示#xff1a;
求解思路
按照人最直觉的想法#xff0c;解压思路如下#xff1a;
如果不存在中括号#xff0c;就直接返回结果#xff…问题描述
该问题用最简单的语言描述就是将通过一定规则压缩的字符解压为原始字符举例如下图示
求解思路
按照人最直觉的想法解压思路如下
如果不存在中括号就直接返回结果如果由中括号一层层包起来的就是一层层往里剥如果有多个独立的中括号结构就每个中括号内容分别解压结果加起来
上面的思路本质上是递归。
代码实现
根据上述思路用c编写代码 string decodeString(string s) {string result;stackint indexList;int startIndex -1;int endIndex -1;for (int i 0; i s.length(); i) {if (s[i] [) {if (indexList.size() 0)startIndex i;indexList.push(i);} else if (s[i] ]) {indexList.pop();if (indexList.size() 0) {endIndex i;break;}}}if (startIndex -1)return s;if (endIndex s.length() - 1) {string innerStr decodeString(s.substr(startIndex 1, endIndex - startIndex - 1));int leftIndex 0;for (int i 0; i startIndex; i) {if (s[i] 0 s[i] 9) {leftIndex i;break;}}result result s.substr(0, leftIndex);int count stoi(s.substr(leftIndex, startIndex - leftIndex));for (int i 0; i count; i) {result result innerStr;}return result;}return decodeString(s.substr(0, endIndex 1)) decodeString(s.substr(endIndex 1));}实现结果
上面代码运行后34个算例全部测试通过耗时2毫秒空间10.61M见下图
优化思路
上述代码中存在重复计算。比如针对算例 开始计算了一次’]‘所在位置为3然后将字符串拆分为3[a]“和2bc”然后在对3[a]进行解码时要重新计算同一个’]的位置。
为了避免重复计算选择从内往外解码具体思路如下 定义数字栈indexList字符串栈strList缓存字符串midStr结果字符串result
匹配’[‘字符识别’[前面的字符串和数字将缓存中的字符串midStr与识别的字符串相加字符串和数字分别入栈清空缓存中的字符匹配’]‘字符识别’]前面的字符串将缓存中的字符串midStr与识别的字符串相加得到字符串tempStr将数字栈和字符串栈分别出栈出栈的元素分别为lastNum、lastStr。lastNum数量的tempStr接长并在前面加上lastStr得到新的字符串currentStr将currentStr存入缓存如果数字栈中元素个数为0将缓存中的字符串接长到结果字符串result中清空缓存midStr如果最后一个’]后面还有字符将剩余字符添加到结果。
该思路取消递归改用栈实现(不需要递归所以能直接在已有结果上解码不需要递归后重新查找位置)同时增加一个midStr用于解码过程中信息传递。该思路最大限度避免了重复计算。
优化后的代码 pairstring, int GetPairFromStr(string str) {int startIndex -1;for (int i 0; i str.length(); i) {if (str[i] 0 str[i] 9) {startIndex i;break;}}if (startIndex -1)return {str, 0};return {str.substr(0, startIndex), stoi(str.substr(startIndex))};}string decodeString(string s) {if (s.find([) string::npos)return s;stackint indexList;stackstring strList;int startIndex 0;string result;string midStr;for (int i 0; i s.length(); i) {if (s[i] [) {pairstring, int tempPair GetPairFromStr(s.substr(startIndex, i - startIndex));indexList.push(tempPair.second);strList.push(midStr tempPair.first);midStr ;startIndex i 1;} else if (s[i] ]) {string tempStr midStr s.substr(startIndex, i - startIndex);string lastStr strList.top();int lastNum indexList.top();string currentStr lastStr;for (int i 0; i lastNum; i) {currentStr currentStr tempStr;}indexList.pop();strList.pop();startIndex i 1;midStr currentStr;if (indexList.size() 0) {result result currentStr;midStr ;}}}if (startIndex ! s.length())result result s.substr(startIndex);return result;}优化结果
优化后34个算例全部通过运行时间0毫秒消耗内存9.78M见下图 结果对比可知优化后运行时间减少了超过75%空间有所减少复杂度不变。
