如果你想在校招中顺利拿到更好的offer,阿秀建议你多看看前人的经验 ,比如准备简历实习校招总结offer选择也欢迎来一起参加秋招打卡活动 等;如果你是计算机小白,学习/转行/校招路上感到迷茫或者需要帮助,可以点此联系阿秀;免费分享阿秀个人学习计算机以来的收集到的好资源,点此白嫖;如果你需要《阿秀的学习笔记》网站中求职相关知识点的PDF版本的话,可以点此下载

# 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