# 71. 简化路径

力扣原题链接(点我直达) (opens new window)

以 Unix 风格给出一个文件的绝对路径,你需要简化它。或者换句话说,将其转换为规范路径。

在 Unix 风格的文件系统中,一个点(.)表示当前目录本身;此外,两个点 (..) 表示将目录切换到上一级(指向父目录);两者都可以是复杂相对路径的组成部分。更多信息请参阅:Linux / Unix中的绝对路径 vs 相对路径

请注意,返回的规范路径必须始终以斜杠 / 开头,并且两个目录名之间必须只有一个斜杠 /。最后一个目录名(如果存在)不能以 / 结尾。此外,规范路径必须是表示绝对路径的最短字符串。

示例 1:

输入:"/home/" 输出:"/home" 解释:注意,最后一个目录名后面没有斜杠。 示例 2:

输入:"/../" 输出:"/" 解释:从根目录向上一级是不可行的,因为根是你可以到达的最高级。 示例 3:

输入:"/home//foo/" 输出:"/home/foo" 解释:在规范路径中,多个连续斜杠需要用一个斜杠替换。 示例 4:

输入:"/a/./b/../../c/" 输出:"/c" 示例 5:

输入:"/a/../../b/../c//.//" 输出:"/c" 示例 6:

输入:"/a//b////c/d//././/.." 输出:"/a/b/c"

# 第一版,看别人的,用vector比栈方便

执行用时 :12 ms, 在所有 cpp 提交中击败了70.22%的用户

内存消耗 :10 MB, 在所有 cpp 提交中击败了90.52%的用户

 string simplifyPath(string path) {
  	string result;
	vector<string> que;
	for (auto i = 0; i < path.size(); ++i)//这个 i++ 是跳过 /号的
	{
		string temp="";
		while (path[i] != '/' && i < path.size())//遇到 / 则跳出,然后去判断当前temp是什么情况
		{
			temp += path[i++];
		}
		if (temp == ".")
			continue;
		else if (temp == "..")
		{
			if (!que.empty()) //如果为空,已经跳不出去了,直接continue就可以了,不为空就把当前末尾pop出去
				que.pop_back();
			else
				continue;
		}
		else if (temp.size() != 0)
			que.push_back(temp);
	}
	for (int i = 0; i < que.size(); i++)
	{
		result += '/';
		result.append(que[i]);
	}
	return result.size() == 0 ? "/" : result;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

# 第二版,稍微改进一点

执行用时 :8 ms, 在所有 cpp 提交中击败了91.91%的用户

内存消耗 :9.8 MB, 在所有 cpp 提交中击败了94.78%的用户

string simplifyPath(string path) {
	string result;
	vector<string> que;
	for (unsigned i = 0; i < path.size(); ++i)//这个 i++ 是跳过 /号的
	{
		string temp="";
		while (path[i] != '/' && i < path.size())//遇到 / 则跳出,然后去判断当前temp是什么情况
		{
			temp += path[i++];
		}
		if (temp == ".")
			continue;
		else if (temp == "..")
		{
			if (!que.empty()) //如果为空,已经跳不出去了,直接continue就可以了,不为空就把当前末尾pop出去
				que.pop_back();
			else
				continue;
		}
		else if (temp.size() != 0)
			que.push_back(temp);
	}
	for (unsigned i = 0; i < que.size(); i++)
	{
		result += '/';
		result.append(que[i]);
	}

	if (result.size() == 0) return "/";
	else return result;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

# 394. 字符串解码

力扣原题链接(点我直达) (opens new window)

给定一个经过编码的字符串,返回它解码后的字符串。

编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。

此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a 或 2[4] 的输入。

示例:

s = "3[a]2[bc]", 返回 "aaabcbc". s = "3[a2[c]]", 返回 "accaccacc". s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".

# 第一版,自己写的

执行用时 :8 ms, 在所有 C++ 提交中击败了26.58%的用户

内存消耗 :8.9 MB, 在所有 C++ 提交中击败了57.94%的用户

string decodeString(string s) {

	string res,temp,countStr;
	int count;

	for (auto i : s) {
		count = 0;
		temp = "";
		countStr = "";
		if (i != ']')
			res.push_back(i);
		else {
			while (res.back() != '[')//直到遇到了[
			{
				temp += res.back();
				res.pop_back();
			}
			res.pop_back();//将 [ 推出去
			
			while (!res.empty() && res.back() >= '0' && res.back() <= '9') {
				countStr += res.back();
				res.pop_back();			
			}
			reverse(countStr.begin(), countStr.end());
			count = stod(countStr, 0);
			reverse(temp.begin(),temp.end());

			for (int j = 0; j < count; ++j) res += temp;
			
		}

	}
	return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

# 402. 移掉K位数字 确实不会

力扣原题链接(点我直达) (opens new window)

给定一个以字符串表示的非负整数 num,移除这个数中的 k 位数字,使得剩下的数字最小。

注意:

num 的长度小于 10002 且 ≥ k。 num 不会包含任何前导零。 示例 1 :

输入: num = "1432219", k = 3 输出: "1219" 解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。 示例 2 :

输入: num = "10200", k = 1 输出: "200" 解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。 示例 3 :

输入: num = "10", k = 2 输出: "0" 解释: 从原数字移除所有的数字,剩余为空就是0。

# 636. 函数的独占时间

力扣原题链接(点我直达) (opens new window)

给出一个非抢占单线程CPU的 n 个函数运行日志,找到函数的独占时间。

每个函数都有一个唯一的 Id,从 0 到 n-1,函数可能会递归调用或者被其他函数调用。

日志是具有以下格式的字符串:function_id:start_or_end:timestamp。例如:"0:start:0" 表示函数 0 从 0 时刻开始运行。"0🔚0" 表示函数 0 在 0 时刻结束。

函数的独占时间定义是在该方法中花费的时间,调用其他函数花费的时间不算该函数的独占时间。你需要根据函数的 Id 有序地返回每个函数的独占时间。

示例 1:

输入: n = 2 logs = ["0:start:0", "1:start:2", "1🔚5", "0🔚6"] 输出:[3, 4] 说明: 函数 0 在时刻 0 开始,在执行了 2个时间单位结束于时刻 1。 现在函数 0 调用函数 1,函数 1 在时刻 2 开始,执行 4 个时间单位后结束于时刻 5。 函数 0 再次在时刻 6 开始执行,并在时刻 6 结束运行,从而执行了 1 个时间单位。 所以函数 0 总共的执行了 2 +1 =3 个时间单位,函数 1 总共执行了 4 个时间单位。 说明:

输入的日志会根据时间戳排序,而不是根据日志Id排序。 你的输出会根据函数Id排序,也就意味着你的输出数组中序号为 0 的元素相当于函数 0 的执行时间。 两个函数不会在同时开始或结束。 函数允许被递归调用,直到运行结束。 1 <= n <= 100

# 第一版,看了别人的思路,真的厉害

执行用时 :24 ms, 在所有 cpp 提交中击败了99.12%的用户

内存消耗 :11.2 MB, 在所有 cpp 提交中击败了100.00%的用户

 vector<int> exclusiveTime(int n, vector<string>& logs) {
    vector<int> result(n, 0);
		stack<pair<int, int>> myStack;//辅助栈,<first, second>分别代表<函数id,起始时间>
		//扫描所有log
		for (auto& log : logs) {
			string operation = "";//id的操作,“start”或者“end”
			int funcId = 0, timeStamp = 0, index = 0, logSize = log.size();//log的函数id、操作时间戳
			//第一步:读取函数id
			while (log[index] != ':') {
				funcId = funcId * 10 + log[index++] - '0';
			}
			index += 1;//跳过 : 
			//第二步:读取操作类型
			while (log[index] != ':') {
				operation += log[index++];
			}
			index += 1; //再次跳过 :
			//第三步:读取时间戳
			while (index < logSize) {
				timeStamp = timeStamp * 10 + log[index++] - '0';
			}
			//第四步:根据操作进行不同的处理
			if (operation == "start") {
				//如果是函数start,直接放入stack中
				myStack.push({ funcId, timeStamp });
			}
			else {//函数end的情况
				int runTime = timeStamp - myStack.top().second + 1;//计算栈顶id运行时间
				myStack.pop();
				result[funcId] += runTime;//加入到总时间中
				//如果此时栈还不为空,则说明当前栈顶函数里面嵌套了当前函数id,需要减去当前函数运行的时间
				if (!myStack.empty()) {
					result[myStack.top().first] -= runTime;
				}
			}
		}
		return result; 
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

# 第二版,自己复现一遍

执行用时 :28 ms, 在所有 cpp 提交中击败了93.86%的用户

内存消耗 :11.1 MB, 在所有 cpp 提交中击败了100.00%的用户

vector<int> exclusiveTime(int n, vector<string>& logs) {//自己复现一编
	vector<int> res(n,0);
	stack<pair<int, int>>st;//函数ID和起始时间的映射

	for (auto& log : logs) {
				
		int funID = 0, startTime = 0, logSize=log.size(), index=0;
		string opera= "";
		while (log[index] != ':') {//取的函数ID
			funID = funID * 10 + log[index++] - '0';
		}
		index++;//跳过 : 号
		//cout << "funID" << funID << endl;
		while (log[index] != ':') {//取的开始还是结束符号
			opera +=  log[index++];
		}
		//cout << "opera" << opera << endl;
		index++;//再次跳过 :号

		while (index<logSize) {//取的操作时间
			startTime = startTime * 10 + log[index++] - '0';
		}
		//cout << "startTime" << startTime << endl;
		if (opera == "start") {//存入开始时间
			st.push({ funID,startTime });
		}
		else {
			int totalRunTime = startTime - st.top().second + 1;
			//cout << "totaltime " << totalRunTime << endl;
			res[funID] += totalRunTime;//以0为中介,属于自己的就加上则减
			st.pop();
			if (!st.empty()) {
				res[st.top().first] -= totalRunTime;//不属于自己的就减去
			}
		}

	}
	return res;
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

# 第三种,别的方法,学到了,但是执行时间较久

学到了istringstream的法子

执行用时 :76 ms, 在所有 cpp 提交中击败了22.81%的用户

内存消耗 :11.1 MB, 在所有 cpp 提交中击败了100.00%的用户

vector<int> res(n, 0);
	stack<pair<int, int>> stk;

	for (auto &log : logs)
	{
		istringstream ss(log);//初始化一个string流
		string s1, s2, s3;
		getline(ss, s1, ':');//以 ; 为阶段符,将ss符合中的内容输入到 s1中,也就是输入了函数ID,此时ss中被取走的有s1和 “;” 
		getline(ss, s2, ':');//,将s1+";"去除后,对于剩下的ss以 ; 为阶段符,将ss符合中的内容输入到 s2中,也就是输入了start或者end
		getline(ss, s3);//,默认是以 \n 为结束符号的

		int id = stoi(s1), time = stoi(s3);
		string action = s2;
		
		if (action == "start")
		{
			if (!stk.empty())
				res[stk.top().first] += time - stk.top().second;
			stk.push({ id,time });
		}
		else
		{
			pair<int, int> p = stk.top();
			stk.pop();

			res[p.first] += time - p.second + 1;
			if (!stk.empty())
				stk.top().second = time + 1;
		}

	}

	return res;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

# 739. 每日温度 经典

力扣原题链接(点我直达) (opens new window)

根据每日 气温 列表,请重新生成一个列表,对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高,请在该位置用 0 来代替。

例如,给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73],你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示:气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度,都是在 [30, 100] 范围内的整数。

# 第一版,超时了


 vector<int> dailyTemperatures(vector<int>& T) {
    vector<int> res;
	res.push_back(0);
	int len = T.size();
	for (int i=len-2; i>=0; --i) {
		int j = i +1;
		while (j != len) {
			if (T[i] < T[j]) { res.push_back(j - i); break; }
			else
				j++;
		}
		if (j == len) res.push_back(0);
	}
	reverse(res.begin(), res.end());

	return res;  
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 第二版,看的别人的

https://leetcode-cn.com/problems/daily-temperatures/solution/jie-ti-si-lu-by-pulsaryu/

执行用时 :224 ms, 在所有 cpp 提交中击败了97.42%的用户

内存消耗 :14.7 MB, 在所有 cpp 提交中击败了94.18%的用户

    vector<int> dailyTemperatures(vector<int>& T) {
	int len = T.size();
	vector<int> res(len);
	res[len - 1] = 0;
	for (int i = len-2; i >=0 ;--i) {

		for (int j = i + 1; j < len; j += res[j]) 
         // j+= result[j]是利用已经有的结果进行跳跃,只需要找比当前大的值进行比较即可,小于的直接跳过
        {
			if (T[j] > T[i]) { res[i] = j - i; break; }
			if (res[j] == 0) { res[i] = 0; break; }
		}//遇到0表示后面不会有更大的值,那当然当前值就应该也为0

	}
	return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 第三版,稍微改进一点

执行用时 :228 ms, 在所有 cpp 提交中击败了95.98%的用户

内存消耗 :14.6 MB, 在所有 cpp 提交中击败了95.15%的用户

res(len)时已经初始化为0了,所以可以去掉那两步赋值为0的部分

vector<int> dailyTemperatures(vector<int>& T) {
	
	int len = T.size();
	vector<int> res(len);
	//res[len - 1] = 0;
	for (int i = len-2; i >=0 ;--i) {

		for (int j = i + 1; j < len; j += res[j]) {
			if (T[j] > T[i]) { res[i] = j - i; break; }
			if (res[j] == 0) {  break; }
		}

	}
	return res;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 856. 括号的分数

力扣原题链接(点我直达) (opens new window)

给定一个平衡括号字符串 S,按下述规则计算该字符串的分数:

() 得 1 分。 AB 得 A + B 分,其中 A 和 B 是平衡括号字符串。 (A) 得 2 * A 分,其中 A 是平衡括号字符串。

示例 1:

输入: "()" 输出: 1 示例 2:

输入: "(())" 输出: 2 示例 3:

输入: "()()" 输出: 2 示例 4:

输入: "(()(()))" 输出: 6

提示:

S 是平衡括号字符串,且只含有 ( 和 ) 。 2 <= S.length <= 50

# 第一版 抄的,看都看不太懂...

执行用时 :4 ms, 在所有 C++ 提交中击败了76.89%的用户

内存消耗 :8.2 MB, 在所有 C++ 提交中击败了92.86%的用户

/*
借鉴别人的 (()(())) = (()) + ((())) , 且  分数 = 2^(层数-1)
出现 '(' 代表层数+1 , 出现 ')' 代表层数 -1
*/
class Solution {
public:
    int scoreOfParentheses(string S) {
        int deep=0,ans=0;
        for(int i=0;i<S.length();i++){
            if(S[i] == '(')deep++;
            else deep--;
            if(S[i]==')' && S[i-1]=='(') ans += 1 << deep;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 921. 使括号有效的最少添加

力扣原题链接(点我直达) (opens new window)

给定一个由 '(' 和 ')' 括号组成的字符串 S,我们需要添加最少的括号( '(' 或是 ')',可以在任何位置),以使得到的括号字符串有效。

从形式上讲,只有满足下面几点之一,括号字符串才是有效的:

它是一个空字符串,或者 它可以被写成 AB (A 与 B 连接), 其中 A 和 B 都是有效字符串,或者 它可以被写作 (A),其中 A 是有效字符串。 给定一个括号字符串,返回为使结果字符串有效而必须添加的最少括号数。

示例 1:

输入:"())" 输出:1 示例 2:

输入:"(((" 输出:3 示例 3:

输入:"()" 输出:0 示例 4:

输入:"()))((" 输出:4

提示:

S.length <= 1000 S 只包含 '(' 和 ')' 字符。

执行用时 :0 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗 :8.7 MB, 在所有 C++ 提交中击败了72.99%的用户

# 第一版 队列,看完理解了

int minAddToMakeValid(string S) {
	if (S.size() <= 1) return S.size();
	stack<char> st;
	st.push(S[0]);
	for (int i = 1; i < S.size(); ++i) {
		if (S[i] == ')')	
		{
			if (st.empty()) st.push(')');
			else if(st.top() == '(') st.pop(); 
			else st.push(')');
		}
		else { 
			st.push(S[i]);
		}
	}
	int cut = 0;
	while (!st.empty()) {
		st.pop();
		cut++;
	}
	return cut;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 第二版 自己隔天复现,还可以

执行用时 :4 ms, 在所有 C++ 提交中击败了79.92%的用户

内存消耗 :8.7 MB, 在所有 C++ 提交中击败了41.42%的用户

vector<string> letterCombinations(string digits) {
	map<char, string> mp = { {'2',"abc"},{'3',"def"},{'4',"ghi"},{'5',"jkl"},{'6',"mno"},{'7',"pqrs"},{'8',"tuv"},{'9',"wxyz"} };//建立映射
	queue<string> que;//借助队列
	vector<string> result;
	unsigned i, j,length;
	string strTemp;

	for (i = 0; i < mp[digits[0]].size(); ++i) { //首先将映射表的第一个元素的内容导入进去
		strTemp.push_back(mp[digits[0]][i]);
		que.push(strTemp);
		strTemp.clear();
	}

	for (i = 1; i < digits.size(); ++i) {//头元素之外的其他元素
		length = que.size();
		while (length--) {//对于当前st的所有元素,挨个取出来与后面的进行组合
			strTemp = que.front(); //把队列头拿出来处理
			for (j = 0; j < mp[digits[i]].size(); ++j) {
				cout << strTemp + mp[digits[i]][j] << endl;
				que.push(strTemp + mp[digits[i]][j]);
			}
			que.pop(); //处理完,去除头部元素
		}
	}

	while (!que.empty()) { //转存到vector上
		result.push_back(que.front());
		que.pop();
	}
	return result;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

# 946. 验证栈序列

力扣原题链接(点我直达) (opens new window)

给定 pushed 和 popped 两个序列,只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时,返回 true;否则,返回 false 。

示例 1:

输入:pushed = [1,2,3,4,5], popped = [4,5,3,2,1] 输出:true 解释:我们可以按以下顺序执行: push(1), push(2), push(3), push(4), pop() -> 4, push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1 示例 2:

输入:pushed = [1,2,3,4,5], popped = [4,3,5,1,2] 输出:false 解释:1 不能在 2 之前弹出。

提示:

0 <= pushed.length == popped.length <= 1000 0 <= pushed[i], popped[i] < 1000 pushed 是 popped 的排列。

# 第一版,自己写的,看错了,改了好久

执行用时 :12 ms, 在所有 cpp 提交中击败了79.08%的用户

内存消耗 :8.9 MB, 在所有 cpp 提交中击败了88.28%的用户

    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
    if (pushed.size() != popped.size()) return false;

	stack<int> st;
	unsigned j=0,lenPush = pushed.size();

	for (unsigned i = 0; i < lenPush && j<lenPush;++i) {
		//cout << "i:" << i << endl;
		st.push(pushed[i]);
		if (popped[j] != st.top())
			continue;
		else
		{
			//cout <<"1:" <<popped[j] << " " << st.top() << endl;
			st.pop();
			j++;
			//cout << "2:" << popped[j] <<" "<<j << endl;
			for (int k = st.size() - 1; k >= 0; --k) {
				
				//cout << "3:" << popped[j] << " " << st.top() <<" j "<<j<< endl;
				if (!st.empty() && st.top() == popped[j]) {
					j++;
					st.pop();
					//cout << "4:" << popped[j] << " " << j << endl;
				}
				else
					break;
			}

		}
	}
	return st.empty() && j  == lenPush;
        
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

# 1003. 检查替换后的词是否有效

力扣原题链接(点我直达) (opens new window)

给定有效字符串 "abc"。

对于任何有效的字符串 V,我们可以将 V 分成两个部分 X 和 Y,使得 X + Y(X 与 Y 连接)等于 V。(X 或 Y 可以为空。)那么,X + "abc" + Y 也同样是有效的。

例如,如果 S = "abc",则有效字符串的示例是:"abc","aabcbc","abcabc","abcabcababcc"。无效字符串的示例是:"abccba","ab","cababc","bac"。

如果给定字符串 S 有效,则返回 true;否则,返回 false。

示例 1:

输入:"aabcbc" 输出:true 解释: 从有效字符串 "abc" 开始。 然后我们可以在 "a" 和 "bc" 之间插入另一个 "abc",产生 "a" + "abc" + "bc",即 "aabcbc"。 示例 2:

输入:"abcabcababcc" 输出:true 解释: "abcabcabc" 是有效的,它可以视作在原串后连续插入 "abc"。 然后我们可以在最后一个字母之前插入 "abc",产生 "abcabcab" + "abc" + "c",即 "abcabcababcc"。 示例 3:

输入:"abccba" 输出:false 示例 4:

输入:"cababc" 输出:false

提示:

1 <= S.length <= 20000 2、S[i] 为 'a'、'b'、或 'c'

# 第一版,应该先判断是否为空再进行其他

执行用时 :24 ms, 在所有 cpp 提交中击败了63.73%的用户

内存消耗 :10.6 MB, 在所有 cpp 提交中击败了81.74%的用户

bool isValid(string S) {
	stack<char> st;
	for (auto &ch : S) {
		if (st.empty()){
			st.push(ch);
		}
		else if (ch == 'c') {
			if (!st.empty() && st.top() == 'b'  ) { //在下一步删除前删除前,应该先判断是否为空再进行其他操作
				st.pop();
				if (!st.empty() && st.top() == 'a' ) //在下一步删除前删除前,应该先判断是否为空再进行其他操作
					st.pop();
				else
				{
					st.push('b');
				}
			}
			else
			{
				st.push('c');
			}
		}
		else
			st.push(ch);
	}
	return st.empty();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

# 1190. 反转每对括号间的子串

力扣原题链接(点我直达) (opens new window)

给出一个字符串 s(仅含有小写英文字母和括号)。

请你按照从括号内到外的顺序,逐层反转每对匹配括号中的字符串,并返回最终的结果。

注意,您的结果中 不应 包含任何括号。

示例 1:

输入:s = "(abcd)" 输出:"dcba" 示例 2:

输入:s = "(u(love)i)" 输出:"iloveu" 示例 3:

输入:s = "(ed(et(oc))el)" 输出:"leetcode" 示例 4:

输入:s = "a(bcdefghijkl(mno)p)q" 输出:"apmnolkjihgfedcbq"

提示:

0 <= s.length <= 2000 s 中只有小写英文字母和括号 我们确保所有括号都是成对出现的

# 第一版 自己写的

执行用时 :4 ms, 在所有 cpp 提交中击败了84.02%的用户

内存消耗 :8.6 MB, 在所有 cpp 提交中击败了100.00%的用户

    string reverseParentheses(string s) {
    stack<char> res;
	string str="";
	for (auto i : s) {
		if(i==')'){
		
			while (res.top() != '(') {
				str += res.top();
				res.pop();
			}
			res.pop();//将'('推出去

			for(auto j:str)
			{
				res.push(j);
			}
			str = "";

		}
		else {
			res.push(i);
		}

	}
	while (!res.empty()) {
		str += res.top();
		res.pop();
	}
	reverse(str.begin(), str.end());
	return str;   
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

# 第二版,循环时使用引用

执行用时 :0 ms, 在所有 cpp 提交中击败了100.00%的用户

内存消耗 :8.7 MB, 在所有 cpp 提交中击败了100.00%的用户

 string reverseParentheses(string s) {
    stack<char> res;
	string str="";
	for (auto &i : s) { //使用引用有很大提升
		if(i==')'){
		
			while (res.top() != '(') {
				str += res.top();
				res.pop();
			}
			res.pop();//将'('推出去

			for(auto &j:str)
			{
				res.push(j);
			}
			str = "";

		}
		else {
			res.push(i);
		}

	}
	while (!res.empty()) {
		str += res.top();
		res.pop();
	}
	reverse(str.begin(), str.end());//注意要反转一下
	return str;   
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

# 1209. 删除字符串中的所有相邻重复项 II

力扣原题链接(点我直达) (opens new window)

给你一个字符串 s,「k 倍重复项删除操作」将会从 s 中选择 k 个相邻且相等的字母,并删除它们,使被删去的字符串的左侧和右侧连在一起。

你需要对 s 重复进行无限次这样的删除操作,直到无法继续为止。

在执行完所有删除操作后,返回最终得到的字符串。

本题答案保证唯一。

示例 1:

输入:s = "abcd", k = 2 输出:"abcd" 解释:没有要删除的内容。 示例 2:

输入:s = "deeedbbcccbdaa", k = 3 输出:"aa" 解释: 先删除 "eee" 和 "ccc",得到 "ddbbbdaa" 再删除 "bbb",得到 "dddaa" 最后删除 "ddd",得到 "aa" 示例 3:

输入:s = "pbbcggttciiippooaais", k = 2 输出:"ps"

提示:

1 <= s.length <= 10^5 2 <= k <= 10^4 s 中只含有小写英文字母。

# 第一版,真的不会,抄的

执行用时 :52 ms, 在所有 C++ 提交中击败了23.22%的用户

内存消耗 :10.4 MB, 在所有 C++ 提交中击败了100.00%的用户

string removeDuplicates(string s, int k) {
	//deeedbbcccbda
	stack<int>times;
	stack<char>st;
	for (auto vi : s) {
		if (st.empty() || st.top() != vi)
			st.push(vi), times.push(1);
		else if (st.top() == vi)
			++times.top();

		if (times.top() == k) st.pop(), times.pop();
	}

	string result="";
	while (!st.empty()) {
		result.insert(result.begin(), times.top(), st.top());
		st.pop(), times.pop();
	}
	return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 第二版,稍微改进一点

执行用时 :28 ms, 在所有 C++ 提交中击败了34.70%的用户

内存消耗 :10.1 MB, 在所有 C++ 提交中击败了100.00%的用户

    string removeDuplicates(string s, int k) {
	stack<int>times;
	stack<char>st;
	for (auto vi : s) {
		if (st.empty() || st.top() != vi)
			st.push(vi), times.push(1);
		else if (st.top() == vi)
			++times.top();

		if (times.top() == k) st.pop(), times.pop();
	}

	string result="";
	int i,len;
	char ch;
	while (!st.empty()) {
		/*result.insert(result.begin(), times.top(), st.top());*/
		len = times.top();
		ch = st.top();
		for ( i = 0; i < len; ++i) {
			result += ch;
		}
		st.pop(), times.pop();
	}
        
    reverse(result.begin(),result.end());//很重要
	return result;
        
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29