长葛网站建设,珠海企业网站建站,网站建设分金手指排名十七,在福州做搬家网站多少钱文章目录 1. 682 棒球比赛2. 71 简化路径3. 388 文件的最长绝对路径4. 150 逆波兰表达式求值5. 227. 基本计算器II6. 224. 基本计算器7. 20. 有效的括号8. 636. 函数的独占时间9. 591. 标签验证器10. 32.最长有效括号12. 341. 扁平化嵌套列表迭代器13. 394.字符串解码 1. 682 棒… 文章目录 1. 682 棒球比赛2. 71 简化路径3. 388 文件的最长绝对路径4. 150 逆波兰表达式求值5. 227. 基本计算器II6. 224. 基本计算器7. 20. 有效的括号8. 636. 函数的独占时间9. 591. 标签验证器10. 32.最长有效括号12. 341. 扁平化嵌套列表迭代器13. 394.字符串解码 1. 682 棒球比赛 解法
使用变长数组对栈进行模拟。
如果操作是 那么访问数组的后两个得分将两个得分之和加到总得分并且将两个得分之和入栈。
如果操作是D那么访问数组的最后一个得分将得分乘以 2 加到总得分并且将得分乘以 2 入栈。
如果操作是C那么访问数组的最后一个得分将总得分减去该得分并且将该得分出栈。
如果操作是整数那么将该整数加到总得分并且将该整数入栈。
时间复杂度O(n其中 n为数组 ops 的大小。遍历整个ops 需要 O(n)。
空间复杂度O(n)。变长数组最多保存O(n) 个元素。
class Solution {
public:int calPoints(vectorstring operations) {int sum0;int tmp0;vectorinttop;for(int i0;i operations.size();i){if(operations[i]){int ntop.size();tmp top[n-1]top[n-2];top.emplace_back(tmp);}else if(operations[i]C){top.pop_back();}else if(operations[i]D){int ntop.size();tmptop[n-1]*2;top.emplace_back(tmp);}else{tmpatoi(operations[i].c_str());top.emplace_back(tmp);}}for(auto item:top){sumitem;}return sum;}
};2. 71 简化路径 解法使用栈来解决首先将path根据/分隔为由若干个字符串组成的列表因为多个/最终也表示/。但是由于c没有split函数因此要自己手动实现一个split方法。之后对于vector内的元素如果是一个点保持不变两个点目录切换到上一级对应弹栈若都不是代表目录名则入栈。
最后将目录名用“/”连接输出即可
class solution62 {public:string simplifyPath(string path) {vectorstringresult;int npath.length();//split path by /for(int i0;in;){if(path[i]/){i;if(in)break;string tmp;while(path[i]!/in){tmppath[i];i;}if(!tmp.empty()){result.emplace_back(tmp);}}}vectorstringlast;for(auto r:result){if(r.)continue;else if(r..){if(!last.empty())last.pop_back();}elselast.emplace_back(r);}string lastreuslt/;int mlast.size();for(int i0;im;i){lastreusltlast[i];if(i!m-1){lastreuslt/;}}return lastreuslt;}
};
时间复杂度O(n)其中 n 是字符串path 的长度。
空间复杂度O(n)。我们需要 O(n) 的空间存储names 中的所有字符串。
3. 388 文件的最长绝对路径 解法hash表前缀和
文件系统可以的最长绝对路径即文件系统按照层次便利的最长路径遍历的终点为一个文件。
题目中的制表符\t的个数为深度根目录的深度为0。因此可以以\n来划分文件字符串设置指针i和j,i指向首位置j指向下一个\n的位置因此j-i为两个\n之间的长度包含了\t因为文件总长度不包含\t。因此若为文件夹该L层的长度为 j-ilevelLen[L-1]1-cnt 其中levelLen[L-1]是上一层的长度cnt为\t个数1表示“/” 若为文件,总长度为 j-ilevelLen[L-1]-cnt 其中levelLen[L-1]是上一层的长度cnt为\t个数 最长长度一直从文件长度中取最大值。
代码
class solution63 {
public:int lengthLongestPath(string input) {int ninput.size();unordered_mapint,intleveltoLen;int ans0;for(int i0;in;i){int ji;int cnt0;bool isFilefalse;while(jninput[j]!\n){if(input[j]\t)cnt;else if(input[j].){isFile true;}j;}int len;if(isFile){lenj-ileveltoLen[cnt-1]-cnt;ansmax(ans,len);}else{lenj-ileveltoLen[cnt-1]1-cnt;}leveltoLen[cnt]len;ij;}return ans;}
};时间复杂度O(n) n为字符串长度
空间复杂度O(n) 哈希表空间
4. 150 逆波兰表达式求值 解法中缀表达式可以使用栈来维护首先遍历算数表达式如果遇到数字入栈如果遇到符号则出栈两个数字并且与符号相作用然后入栈最后栈中剩余的唯一数字则为最后结果。
代码
class solution64 {
public:int evalRPN(vectorstring tokens) {vectorintstacks;for(auto item:tokens){if(item){int t1stacks.back();stacks.pop_back();int t2stacks.back();stacks.pop_back();int tmpt2t1;stacks.emplace_back(tmp);}else if(item-){int t1stacks.back();stacks.pop_back();int t2stacks.back();stacks.pop_back();int tmpt2-t1;stacks.emplace_back(tmp);}else if(item*){int t1stacks.back();stacks.pop_back();int t2stacks.back();stacks.pop_back();int tmpt2*t1;stacks.emplace_back(tmp);}else if(item/){int t1stacks.back();stacks.pop_back();int t2stacks.back();stacks.pop_back();int tmpt2/t1;stacks.emplace_back(tmp);}else{int t std::atoi(item.c_str());stacks.emplace_back(t);}}return stacks.back();}
};时间复杂度O(n)其中 n 是数组 tokens 的长度。需要遍历数组 tokens 一次计算逆波兰表达式的值。
空间复杂度O(n)其中 n是数组tokens 的长度。使用栈存储计算过程中的数栈内元素个数不会超过逆波兰表达式的长度。
5. 227. 基本计算器II 解法
这题没有括号实现计算器可以使用双栈的思路一个栈存储数字另一个栈存储运算符注意到*/的运算符优先级相同±运算符优先级相同乘除的优先级高于加减。因此当运算符a入栈时需要判断栈顶元素如果a为或者-号则栈内所有其他运算符必须先和数字占进行结合计算。如果a为乘号或者除号则栈顶元素为“”或者“-”可以直接入栈。
遍历完式子之后如果符号栈为空返回数字栈中的数字如果符号栈不为空则按照符号栈的顺序弹栈并且与数字栈结合计算返回结果。 注意两点c的isdigit函数可以判断字符串是否为数字且数字为非负整数不止是一位数因此需要对数字进行转换。 并且s[i]-0’需要用int进行强制类型转换因为减法运算可能导致溢出或者不确定的结构使得ascii为负数。 代码可能比较冗余但逻辑是清晰的。
代码
class solution65 {
public:int calculate(string s) {vectorintnum;vectorcharop;int ns.size();for(int i0;in;i){if(s[i] )continue;else if(s[i]*){int tmp;while(!op.empty()){if(op.back()/){int t1num.back();num.pop_back();int t2num.back();num.pop_back();tmpt2/t1;num.emplace_back(tmp);}else if(op.back()*){int t1num.back();num.pop_back();int t2num.back();num.pop_back();tmpt2*t1;num.emplace_back(tmp);}else{break;}op.pop_back();}op.emplace_back(s[i]);}else if(s[i]/){int tmp;while(!op.empty()){if(op.back()/){int t1num.back();num.pop_back();int t2num.back();num.pop_back();tmpt2/t1;num.emplace_back(tmp);}else if(op.back()*){int t1num.back();num.pop_back();int t2num.back();num.pop_back();tmpt2*t1;num.emplace_back(tmp);}else{break;}op.pop_back();}op.emplace_back(s[i]);}else if(s[i]||s[i]-){int t1,t2,tmp;while(!op.empty()){if(op.back()){t1num.back();num.pop_back();t2num.back();num.pop_back();tmpt2t1;num.emplace_back(tmp);}else if(op.back()-){t1num.back();num.pop_back();t2num.back();num.pop_back();tmpt2-t1;num.emplace_back(tmp);}else if(op.back()*){t1num.back();num.pop_back();t2num.back();num.pop_back();tmpt2*t1;num.emplace_back(tmp);}else if(op.back()/){t1num.back();num.pop_back();t2num.back();num.pop_back();tmpt2/t1;num.emplace_back(tmp);}op.pop_back();}op.emplace_back(s[i]);}else{int n0;while(isdigit(s[i])){nn*10s[i]-0;i;}num.emplace_back(n);i--;}}int t1,t2,tmp;while(!op.empty()){char oop.back();op.pop_back();t1num.back();num.pop_back();t2num.back();num.pop_back();if(o*){tmpt2*t1;}else if(o/){tmpt2/t1;}else if(o){tmpt2t1;}else{tmpt2-t1;}num.emplace_back(tmp);}return num.back();}};
时间复杂度O(n)其中n 为字符串 s的长度。需要遍历字符串 s 一次计算表达式的值。
空间复杂度O(n)其中 n 为字符串 s 的长度。空间复杂度主要取决于栈的空间栈的元素个数不超过 n。
6. 224. 基本计算器 解法使用两个栈 num 和 op 。
num 存放所有的数字 op 存放所有的数字以外的操作。±
1.首先预处理字符串将所有空格去掉。
2.然后对于所有的(直接放入符号栈
3.如果有新的符号入栈且不是)“,可以将当前栈内可以计算的符号进行计算避免在通过”)进行判断计算的时候将-操作顺序变换导致出错。
4.如果遇到)“将当前”(前的所有符号都计算并且弹出左括号计算结果加入num 时刻注意一些细节由于第一个数可能是负数如“-21”为了减少边界判断,先往 nums 添加一个 0; 为防止 () 内出现的首个字符为运算符如-22如果遇到-在num中添加0 代码
class solution66 {
public:int calculate(string s) {vectorintnum;//为了防止第一个数是负数num.emplace_back(0);vectorcharop;bool flagfalse;string ns;for(int i0;is.size();i){if(s[i] )continue;nss[i];}int nns.size();for(int i0;in;i){if(ns[i](){if(ns[i1]-||ns[i1]){num.emplace_back(0);}op.emplace_back(ns[i]);}else{if(isdigit(ns[i])){int m0;while(isdigit(ns[i])){mm*10int(ns[i]-0);i;}num.emplace_back(m);i--;}else if(ns[i]||ns[i]-){//将栈内能算的先算避免之后算让如-操作的号运算比-前int t1,t2,tmp;while(!op.empty()op.back()!(){t1num.back();num.pop_back();t2num.back();num.pop_back();char oop.back();op.pop_back();if(o)tmpt2t1;else if(o-)tmpt2-t1;num.emplace_back(tmp);}op.emplace_back(ns[i]);}else if(ns[i])){int t1,t2,tmp;while(op.back()!(){t1num.back();num.pop_back();t2num.back();num.pop_back();char oop.back();op.pop_back();if(o)tmpt2t1;else if(o-)tmpt2-t1;num.emplace_back(tmp);}op.pop_back();}}}int t1,t2,tmp;while(!op.empty()){char oop.back();op.pop_back();t1num.back();num.pop_back();t2num.back();num.pop_back();if(o)tmpt2t1;else if(o-)tmpt2-t1;num.emplace_back(tmp);}return num.back();}
};时间复杂度o(n)
空间复杂度o(n)
7. 20. 有效的括号 解法利用栈来解决首先字符串为空或者长度为1一定返回false
然后便利字符串中的括号如果是左括号则入栈如果碰到右括号如果栈中非空并且栈顶有对应的左括号与其匹配则弹栈;否则将右括号入栈
最后如果栈为空说明匹配否则不匹配
class solution67 {
public:bool isValid(string s) {vectorcharstack;if(s.empty()||s.size()1)return false;for( auto item:s){if(item(||item[||item{)stack.emplace_back(item);else if(item)){if(stack.empty()||stack.back()!()stack.emplace_back(item);elsestack.pop_back();}else if(item]){if(stack.empty()||stack.back()![)stack.emplace_back(item);elsestack.pop_back();}else if(item}){if(stack.empty()||stack.back()!{)stack.emplace_back(item);elsestack.pop_back();}}return stack.empty();}
};
时间复杂度O(n)
空间复杂度O(n)
8. 636. 函数的独占时间 解法因为每个函数都有对应的start和end即栈中记录函数的id号和开始时间戳result记录每个函数的累积执行时间
1.若为起始函数直接入栈
2.若有新的函数为start则入栈栈顶的函数s的运行时间是当前新函数的时间戳timestamp2-栈顶时间戳timestamp1;累加到result[s]中且需要将栈顶函数的其实时间改为新函数的其实时间。
3.如果新函数为end那么会弹出栈顶函数s,栈顶函数的运行时间为当新函数的时间戳timestamps2-栈顶时间戳1此时pop栈顶函数同时若栈顶不为空的话新的栈顶函数的时间戳为timestamp21
最后栈为空返回result
代码
class solution68 {
public:vectorint exclusiveTime(int n, vectorstring logs) {vectorintresult(n,0);vectorpairint,intstack;for(auto log:logs){int pos1log.find(:);int pos2log.rfind(:);int idstd::atoi(log.substr(0,pos1).c_str());string statuslog.substr(pos11,pos2-pos1-1);int timestampstd::atoi(log.substr(pos21,log.size()).c_str());pairint,intitem make_pair(id, timestamp);if(statusstart){if(!stack.empty()){result[stack.back().first]timestamp-stack.back().second;stack.back().secondtimestamp;}stack.emplace_back(item);}else{result[id]timestamp-stack.back().second1;stack.pop_back();if(!stack.empty()){stack.back().secondtimestamp1;}}}return result;}
};时间复杂度O(n))其中 n 为全部日志 logs 的数量n 条日志信息对应总共 n 次入栈和出栈操作。 空间复杂度O(n)其中 n 为全部日志logs 的数量n 条日志信息对应n/2次入栈操作最坏的情况下全部 n/2 条日志入栈后才会依次弹栈。 c函数使用注意substr函数的形式为s.substr(pos, n) 需要两个参数第一个是开始位置第二个是获取子串的长度。 函数可以从一个字符串中获取子串返回一个string包含s中从pos开始的n个字符的拷贝pos的默认值是0n的默认值是s.size() - pos即不加参数会默认拷贝整个s。 官方解法中给出了一个按照冒号分割字符串的新方式 char type[10]; int idx, timestamp; 在C中你可以使用 sscanf 函数来按照指定的格式从一个C风格的字符串中读取数据。这个函数的原型为 int sscanf(const char* str, const char* format, ...);它的工作方式类似于 scanf 函数但是不是从标准输入读取而是从给定的字符串中读取数据。 在你提供的代码中sscanf 函数的格式字符串是 %d:%[^:]:%d。这个格式字符串指示 sscanf 从 log.c_str() 这个字符串中按照以下规则读取数据 %d读取一个整数赋值给 idx。:读取一个冒号但不存储。%[^:]读取一个非冒号的字符串赋值给 type。这个格式说明符 %[^:] 使用了 [^:] 表达式它表示匹配除冒号外的任意字符这样可以读取 type 的值。:读取一个冒号但不存储。%d读取一个整数赋值给 timestamp。 所以当 sscanf 函数调用时它会根据给定的格式字符串解析 log.c_str() 中的内容并将解析出的值存储到相应的变量。 需要注意的是虽然在C中可以使用 sscanf 进行字符串解析但这通常不是最安全的方法因为它对于输入数据的格式和边界条件的检查相对较弱。在实际应用中更推荐使用更安全的字符串解析方法比如使用 std::istringstream 或者字符串分割库来处理字符串。 9. 591. 标签验证器 解法栈模拟
字符串模拟假设字符串 s 长度为 n当前处理到的位置为 i根据以下优先级进行检查
优先尝试检查以 i 为开始的连续段是否为 CDATA若能匹配到开头则尝试匹配到 CDATA 的结尾处并更新 i若无法找到结尾返回 False 1.尝试匹配 s[i] 若满足则根据 s[i1] 是否为 / 来判断当前 TAG_NAME 是处于右边还是左边然后将 TAG_NAME 取出记为 tag判断 tag 长度是否合法不合法返回 False合法则根据是左边还是右边的 TAG_NAME 分情况讨论 2.位于左边的 TAG_NAME将其加入栈中等待右边的 TAG_NAME 与其匹配 位于右边的 TAG_NAME将其与当前栈顶的元素进行匹配若栈为空或匹配不上返回 False. 3.其余情况则为普通字符。 最后由于整个 s 应当被一对 TAG_NAME 所包裹因此当 i0时不能是情况 1和情况 3需要特判一下。 注意细节因为题目中说到代码必须被合法的闭合标签包围因此当字符串未遍历完成stack不能为空所以对于pop标签后若是栈为空且没有遍历完字符串则返回false如“A/AB/B” 情况此时A标签pop时候stack已经为空。 同理当为其他字符时必须保证stack内有标签存在 代码
class solution69 {
public:string findTagName(string s,int index,intend){int iindex;string reuslt;int ns.size();while(inisupper(s[i])){reuslts[i];i;}endi;if(in){return ;}if(s[i]){return reuslt;}else{return ;}}bool isCdata(string s,int index,int end){int iindex;int ns.size();string c[CDATA[;int cnt0;for( iindex;in;i){if(s[i]!c[cnt]){return false;}cnt;if(cntc.size()){break;}}i;while(in){if(s[i]]){if(i2ns[i1]]s[i2]){endi2;return true;}}i;}return false;}bool isValid(string code) {vectorstringstack;int ncode.size();for(int i0;in;i){int end;if(code[i]){if(i1ncode[i1]/){//end标签string s findTagName(code,i2,end);if(stack.empty())return false;string startstack.back();if(s.empty()||s!start){return false;}stack.pop_back();if(stack.empty()end!n-1)return false;}else if(i1ncode[i1]!){bool flag isCdata(code,i2,end);if(!flag){return false;}if(stack.empty()end!n-1)return false;}else{string s findTagName(code,i1,end);if(s.empty()||s.size()9||s.size()1)return false;stack.emplace_back(s);}iend;}else{if(stack.empty())return false;}}return stack.empty();}
};时间复杂度O(n)
空间复杂度O(n)
10. 32.最长有效括号 解法
我们定义 dp[i] 表示以下标 i 字符结尾的最长有效括号的长度。我们将dp 数组全部初始化为 0 。显然有效的子串一定以 ‘)’ 结尾因此我们可以知道以 ‘(’ 结尾的子串对应的dp 值必定为 0 我们只需要求解 ‘‘)’ 在 dp 数组中对应位置的值。 我们从前往后遍历字符串求解 dp 值我们每两个字符检查一次s[i−1]‘(’也就是字符串形如 “……()”我们可以推出 dp[i]dp[i−2]2 我们可以进行这样的转移是因为结束部分的 “()” 是一个有效子字符串并且将之前有效子字符串的长度增加了 2 2 2 。 s[i−1] ′)’ 这种情况下如果前面有和s[i]组成有效括号对的字符即形如 ((…))这样的话就要求s[i−1]位置必然是有效的括号对否则s[i]s[i]s[i]无法和前面对字符组成有效括号对。 这时我们只需要找到和s[i]配对对位置并判断其是否是 ( 即可。和其配对位置为i-dp[i-1]1. 若s[i-dp[i-1]-1]‘(’: 有效括号长度新增长度 2i位置对最长有效括号长度为 i-1位置的最长括号长度加上当前位置新增的 2那么有 dp[i]dp[i−1]2 值得注意的是i−dp[i−1]−1 和 i 组成了有效括号对这将是一段独立的有效括号序列如果之前的子序列是形如 (…) 这种序列那么当前位置的最长有效括号长度还需要加上这一段。所以 dp[i]dp[i−1]dp[i−dp[i−1]−2]2; 这个地方很容易遗漏因为如用例)()(())如果直接dp[i]dp[i-1]2就很容易遗漏。 代码
class solution70 { public: int longestValidParentheses(string s) { int ns.size(); int *dpnew int[n]; std::fill(dp,dpn,0); int result0; for(int i1;is.size();i){ if(s[i]‘)’) { if(s[i-1]‘(’) { if(i-20) dp[i]dp[i-2]2; else dp[i]2; } else{ if(i-dp[i-1]0s[i-dp[i-1]-1]‘(’){ dp[i]dp[i-1]2; int prei-dp[i-1]-20?dp[i-dp[i-1]-2]:0; dp[i]pre; } } } resultmax(result,dp[i]); } delete []dp; return result; } }; 时间复杂度 O(n)其中 n 为字符串的长度。我们只需遍历整个字符串一次即可将 dp 数组求出来。空间复杂度 O(n)】。我们需要一个大小为 n 的 dp 数组。### 11. 385.迷你语法分析器解法这道题用栈来解决主要是要读懂辅助结构NestedInteger的几个函数的意思。1. NestedInteger(); Constructor initializes an empty nested list. 构造函数初始化一个空的嵌套列表。
2. NestedInteger(int value); Constructor initializes a single integer.构造函数初始化一个整数。
3. void add(const NestedInteger ni); Set this NestedInteger to hold a nested list and adds a nested integer to it.设置这个NestedInteger保存一个嵌套的列表并向它添加一个嵌套的整数。3个方法的具体效果如下csharpNestedInteger ans NestedInteger(); // ans []ans.add(NestedInteger(789)); // ans [789]NestedInteger temp NestedInteger(); // temp []temp.add(NestedInteger(456)); // temp [456]temp.add(ans); // temp [456, [789]]NestedInteger res NestedInteger(); // res []res.add(NestedInteger(123)); // res [123]res.add(temp); // res [123, [456, [789]]]因此利用栈来遍历字符串如果遇到‘[’则表示一个新的NestedInteger对象将其入栈如果遇到的是“,“或者”]则表示一个数字或者一个NestedInteger对象的结束需要将这个数字添加到栈顶的对象中去。
以下又可以分成两种情况若]或“,”左边是数字说明是独立的对象因此将数字加入栈顶对象中
若“]”的左边是“]”带边对象的嵌入因此当前栈顶的对象应该嵌入到它的上一个对象中如789嵌入到456对象中 其中还需要注意一些特殊情况若不以“[”开头则说明只包含一个数字对象而且注意可能有负数需要判断 代码
/*** // This is the interface that allows for creating nested lists.* // You should not implement it, or speculate about its implementation* class NestedInteger {* public:* // Constructor initializes an empty nested list.* NestedInteger();** // Constructor initializes a single integer.* NestedInteger(int value);** // Return true if this NestedInteger holds a single integer, rather than a nested list.* bool isInteger() const;** // Return the single integer that this NestedInteger holds, if it holds a single integer* // The result is undefined if this NestedInteger holds a nested list* int getInteger() const;** // Set this NestedInteger to hold a single integer.* void setInteger(int value);** // Set this NestedInteger to hold a nested list and adds a nested integer to it.* void add(const NestedInteger ni);** // Return the nested list that this NestedInteger holds, if it holds a nested list* // The result is undefined if this NestedInteger holds a single integer* const vectorNestedInteger getList() const;* };*/
class Solution {
public:NestedInteger deserialize(string s) {if(s[0]![)return NestedInteger(atoi(s.c_str()));vectorNestedIntegerstack;int num0;bool flagfalse;for(int i0;is.size();i){char cs[i];if(c-){flagtrue;continue;}else if(isdigit(c)){numnum*10int(c-0);}//检测到左括号同步往栈中添加对象else if(c[)stack.emplace_back(NestedInteger());else if (c,||c]){//如果其左边是整数说明它是一个对象如果c为逗号说明其对象有其他嵌套对象为]说明为完整对象if(isdigit(s[i-1])){if(flag){num*-1;}stack.back().add(NestedInteger(num));}num0;flagfalse;if(c]stack.size()1){//将其和上一个对象合并NestedInteger nstack.back();stack.pop_back();stack.back().add(n);}}}return stack.back();}
};时间复杂度O(n)其中 n是 s 的长度。我们需要遍历 s 的每一位来解析。
空间复杂度O(n)其中 n 是 s 的长度。栈的深度最多为 O(n)。
12. 341. 扁平化嵌套列表迭代器 解法一递归 注意,递归是最简单的方法但是在面试过程中面试官可能想考察的不会是递归的方法而是迭代的方法 因为整个nestedList结构可看成树形结构的一种表达形式树上的叶子结点就是一个正数而非叶子结点就是一个列表。
因此我们可以对这个nestedList结构进行深搜在深搜的过程中将最终结果存入数组。
如上述的例子 n e x t e d L i s t [ [ 1 , 1 ] , 2 , [ 1 , 1 ] ] nextedList[[1,1],2,[1,1]] nextedList[[1,1],2,[1,1]]那么通过dfs将结果存入 r e s u l t result result得到 [ 1 , 1 , 2 , 1 , 1 ] [1,1,2,1,1] [1,1,2,1,1]
所以 h a s n e x t hasnext hasnext即判断 r e s u l t result result中是否有整数, n e x t next next则是返回 r e s u l t result result中的整数.
/*** // This is the interface that allows for creating nested lists.* // You should not implement it, or speculate about its implementation* class NestedInteger {* public:* // Return true if this NestedInteger holds a single integer, rather than a nested list.* bool isInteger() const;** // Return the single integer that this NestedInteger holds, if it holds a single integer* // The result is undefined if this NestedInteger holds a nested list* int getInteger() const;** // Return the nested list that this NestedInteger holds, if it holds a nested list* // The result is undefined if this NestedInteger holds a single integer* const vectorNestedInteger getList() const;* };*/class NestedIterator {
public:vectorintresult;vectorint::iterator iters;void dfs(const vectorNestedInteger nestedList){for(auto nest:nestedList){if(nest.isInteger()){result.emplace_back(nest.getInteger());}else{dfs(nest.getList());}}}NestedIterator(vectorNestedInteger nestedList) {dfs(nestedList);itersresult.begin();}int next() {return *iters;}bool hasNext() {return iters!result.end();}
};/*** Your NestedIterator object will be instantiated and called as such:* NestedIterator i(nestedList);* while (i.hasNext()) cout i.next();*/时间复杂度初始化O(n)next 和 hasNext 为O(1)。其中 n 是嵌套的整型列表中的元素个数。
空间复杂度O(n)。需要一个数组存储嵌套的整型列表中的所有元素。
解法二迭代
基于迭代的方式利用栈来模拟递归的过程 初始化的时候由于栈是先进先出的可以利用vector模拟栈将所有元素逆序加入栈中。 在hasNext()方法中判断栈顶是否为int 若为ints说明有下一个元素返回truenext()函数被调用此时弹出栈顶元素 如果是list就将当前列表的各个元素再放入栈中【逆序】 使用栈的好处就是不用一开始就展开所有元素只在需要展开的时候展开
代码
/*** // This is the interface that allows for creating nested lists.* // You should not implement it, or speculate about its implementation* class NestedInteger {* public:* // Return true if this NestedInteger holds a single integer, rather than a nested list.* bool isInteger() const;** // Return the single integer that this NestedInteger holds, if it holds a single integer* // The result is undefined if this NestedInteger holds a nested list* int getInteger() const;** // Return the nested list that this NestedInteger holds, if it holds a nested list* // The result is undefined if this NestedInteger holds a single integer* const vectorNestedInteger getList() const;* };*/class NestedIterator {
public:vectorNestedIntegerresult;NestedIterator(vectorNestedInteger nestedList) {for(int inestedList.size()-1;i0;i--){result.push_back(nestedList[i]);}}int next() {int nextresult.back().getInteger();result.pop_back();return next;}bool hasNext() {if(result.empty()){return false;} auto itemresult.back();if(item.isInteger()){return true;}else{//此时展开NestedInteger 利用hasnext判断//注意必须为逆序放入不然弹出顺序又问题auto numitem.getList();result.pop_back();for(int inum.size()-1;i0;i--){result.push_back(num[i]);}return hasNext();}}
};/*** Your NestedIterator object will be instantiated and called as such:* NestedIterator i(nestedList);* while (i.hasNext()) cout i.next();*/时间复杂度初始化和 next 为 O(1)hasNext 为均摊 O(1)。
空间复杂度O(n)。最坏情况下嵌套的整型列表是一条链我们需要一个O(n) 大小的栈来存储链上的所有元素。
13. 394.字符串解码 解法1辅助栈
首先创建两个栈数字栈nums和字符串栈str遍历该字符串s对于其中一个字符c若为数字则入数字栈;若为字符[a-z,A-Z]则继续遍历知道该位置不为字符类型将其拼接成字符串入str栈若c为[“则入str栈若c为”]。那么str栈不断弹栈直到遇到“[”。此时栈中的字符串必须按照逆序拼接组成新的字符串。然后取得数字栈顶数字n将该字符串重复n次后加入str栈中“[”必定和数字配对因此若出现“[”数字栈顶必有数字最后遍历结束后将str栈中元素顺序拼接就能得到结果
代码
class solution72 {
public:vectorintnums;vectorstringstr;string laststr;string decodeString(string s) {int i0;while(is.size()){int num0;int flag0;while(isdigit(s[i])){num(s[i]-0)10*num;i;flag1;}if(flag)nums.emplace_back(num);string c;flag0;while(isalpha(s[i])){cs[i];i;flag1;}if(flag)str.emplace_back(c);if(s[i][){str.emplace_back(string(1,s[i]));i;}if(s[i]]){int numnums.back();nums.pop_back();string s;while(str.back()