这是四则或许对你有帮助的讯息

1、👉 最近我发现了一个每日都会推送最新校招资讯的《校招日程》文档,其中包括往届补录应届实习校招信息,比如各种大厂、国企、银行、事业编等信息都会定期更新,帮忙扩散一下。

2、😍 免费分享阿秀个人学习计算机以来的收集到的免费资源,点此白嫖

3、🚀如果你想在校招中顺利拿到更好的offer,阿秀建议你多看看前人踩过的坑留下的经验,事实上你现在遇到的大多数问题你的学长学姐师兄师姐基本都已经遇到过了。

4、🔥 欢迎准备计算机校招的小伙伴加入我的学习圈子,一个人踽踽独行真的不如一群人报团取暖,过去22届和23届的小伙伴好好跟着走下去的,最后基本都拿到了不错的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