一、字符串解码
思路：栈
这道题怎么看都好像是用栈来实现，因为有左右括号。(可是第一时间我没想到)
- 遍历字符串，此时会有几种情况：
- 1.如果是数字字符，给一个
num变量，将该字符转化成数字存储起来。 - 2.如果是字母（题目说只可能是小写），给一个字符串
str，将该字母存储到字符串里。 - 3.如果是" [ ",此时需要将刚才的数字和字母分别入栈，将数字num入到
nums栈，str入到strs栈，然后清空num和str - 4.如果是" ] “,先将
nums栈的栈顶元素取出来给给top变量，然后循环top次将str追加到strs栈的栈顶元素后面，比如这时候strs栈栈顶元素是"aaa”，str是"ab"，top = 2，那么就将str追加，结果为：aaaabab。最后再将strs栈的栈顶元素赋值回给str。 - 注意：遇到" ] “后，下一个字符不可能是” [ "，不符合题目要求，只可能是数字字符或字母字符，仍然会按照正常的流程继续走下去。
- 最后返回str即可。
具体代码如下：
class Solution { public: string decodeString(string s) { int num = 0; //存储数字 string str = ""; //存储字符串 stack<int> nums; //遇到'['：数字入数字栈 stack<string> strs;//字符串入字符串栈 for(int i = 0;i<s.size();++i) { if(s[i] >='0' && s[i] <= '9') { //如果出现连续的数字，个位就要*10再加起来 num = num * 10 + (s[i] - '0') ; } else if(s[i] >= 'a' && s[i] <='z') { str = str + s[i]; } else if(s[i] == '[') { //入数字栈 nums.push(num); num = 0; //入字符串栈 strs.push(str); str = ""; } //遇到']'了 else { int top = nums.top(); nums.pop(); for(int j = 0;j<top;++j) { //注意这里是将str追加到栈顶元素之后 strs.top() += str; } //将栈顶元素给回str //']'之后接下来的字符不可能是'['，这不符合题目要求 //所以接下来的字符不管是数字还是字母，都可以正常进行 str = strs.top(); strs.pop(); } } return str; } };
时间复杂度：O(N)，空间复杂度O(1)
二、数组中重复的数字
思路1：计数法
具体过程如下：
- 1.开一个n大小的顺序表，初始化为0，作为0~n-1区间的每个数字出现的次数。
- 2.遍历一遍数组，将出现的数字在计数顺序表的位置++，比如：出现的数字是5，那么就在顺序表的下标5的位置+1
- 3.如果计数顺序表中的任意元素出现次数大于1，则说明对应的元素重复出现，返回即可。
具体代码如下：
class Solution { public: int findRepeatNumber(vector<int>& nums) { int n = nums.size(); vector<int> count(n); for(int i =0;i<nums.size();++i) { count[nums[i]]++; if(count[nums[i]] > 1) return nums[i]; } return -1; } };
时间复杂度O(n),空间复杂度O(n)
思路2：原地交换法
这个方法也可以理解为：岗位对接人才问题。
具体如下：
- 1.这个原地交换法就相当于分配工作，每个索引代表一个工作岗位，每个岗位必须专业对口，既0索引必须0元素才能上岗。而我们的目的就是找出溢出的人才，既0索引岗位有多个0元素竞争。
- 2.我们先从0索引岗位开始遍历，首先我们看0索引是不是已经专业对口了，如果已经专业对口既nums[0]=0，那我们就跳过0岗位看1岗位。
- 3.如果0索引没有专业对口，那么我们看现在0索引上的人才调整到他对应的岗位上，比如num[0]=2，那我们就把2这个元素挪到他对应的岗位上既num[2]，这个时候有两种情况:
- 1、num[2]岗位上已经有专业对口的人才了，既num[2]=2，这就说明刚刚那个在num[0]上的2是溢出的人才，我们直接将其返回即可。
- 2、num[2]上的不是专业对口的人才，那我们将num[0]上的元素和num[2]上的元素交换，这样num[2]就找到专业对口的人才了。
- 4.之后重复这个过程直到帮num[0]找到专业对口的人才，然后以此类推帮num[1]找人才、帮num[2]找人才，直到找到溢出的人才。
图解过程如下：
具体代码如下：
class Solution { public: int findRepeatNumber(vector<int>& nums) { int i = 0; while(i < nums.size()) { //岗位和人才对口了，继续往下找，直到找到溢出的人才 if(i == nums[i]) { ++i; continue; } //情况1.该人才是溢出人才 if(nums[i] == nums[nums[i]]) return nums[i]; //情况2.不是溢出人才，那就把该人才调整到对应岗位 else swap(nums[i],nums[nums[i]]); } return -1; } };
时间复杂度O(n)，空间复杂度O(1)
总结
通过今天的两道题：
- 1.我发现只要有括号的匹配，或者有涉及到括号的，都可以考虑使用栈来解决。
- 2.对于找重复的数字/字符串/字符等，均可使用计数法，空间复杂度O（N）来统计出现次数。
或者使用“岗位对接人才”的原地交换法解决此类问题。
