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

# 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