1.
20. 有效的括号
给定一个只包括
'('
，
')'
，
'{'
，
'}'
，
'['
，
']'
的字符串
s
，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
class Solution {
public:
bool isValid(string s) {
stack<int> st;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '(') st.push(')');
else if (s[i] == '{') st.push('}');
else if (s[i] == '[') st.push(']');
// 第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号 return false
// 第二种情况：遍历字符串匹配的过程中，发现栈里没有我们要匹配的字符。所以return false
else if (st.empty() || st.top() != s[i]) return false;
else st.pop(); // st.top() 与 s[i]相等，栈弹出元素
}
// 第一种情况：此时我们已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false，否则就return true
return st.empty();
}
};
2.
94. 二叉树的中序遍历
给定一个二叉树的根节点
root
，返回它的
中序
遍历。
（非递归哦宝贝~）
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> st;
auto p = root;
while (p || !st.empty()) {
while (p) {
st.push(p);
p = p->left;
}
auto node = st.top();
st.pop();
res.emplace_back(node->val);
p = node->right;
}
return res;
}
};
3.
234. 回文链表
给你一个单链表的头节点
head
，请你判断该链表是否为回文链表。如果是，返回
true
；否则，返回
false
。
class Solution {
public:
bool isPalindrome(ListNode* head) {//O(n)、O(1)
ListNode* slow = head, *fast = head, *prev = nullptr;
while (fast){//find mid node
slow = slow->next;
fast = fast->next ? fast->next->next: fast->next;
}
while (slow){//reverse
ListNode* temp = slow->next;
slow->next = prev;
prev = slow;
slow = temp;
}
while (head && prev){//check
if (head->val != prev->val){
return false;
}
head = head->next;
prev = prev->next;
}
return true;
}
};
4.
682. 棒球比赛
你现在是一场采用特殊赛制棒球比赛的记录员。这场比赛由若干回合组成，过去几回合的得分可能会影响以后几回合的得分。比赛开始时，记录是空白的。你会得到一个记录操作的字符串列表
ops
，其中
ops[i]
是你需要记录的第
i
项操作，
ops
遵循下述规则：
-
整数
x
– 表示本回合新获得分数
x
-
"+"
– 表示本回合新获得的得分是前两次得分的总和。题目数据保证记录此操作时前面总是存在两个有效的分数。 -
"D"
– 表示本回合新获得的得分是前一次得分的两倍。题目数据保证记录此操作时前面总是存在一个有效的分数。 -
"C"
– 表示前一次得分无效，将其从记录中移除。题目数据保证记录此操作时前面总是存在一个有效的分数。
请你返回记录中所有得分的总和。
class Solution {
public:
int calPoints(vector<string>& ops) {
stack<int> score;
for(string s:ops) {
if(s.compare("C")==0) {
score.pop();
}
else if(s.compare("+")==0) {
int one = score.top();
score.pop();
int two = score.top();
score.pop();
score.push(two);
score.push(one);
score.push(one+two);
}
else if(s.compare("D")==0){
int one = score.top();
score.pop();
score.push(one);
score.push(2*one);
}
else {
score.push(stoi(s));
}
}
int sum = 0;
while(!score.empty()) {
sum += score.top();
score.pop();
}
return sum;
}
};
此题比较简单，只要分类讨论vector中的string对应哪种字符即可。如果是数字的话直接将其转换为整型数字，存入一个整型类型的vector中，然后其三种字符的话，只是分别对这个整型vector中的元素进行相关运算即可。最后得到一个存有有效分数的vector。累加即可得到结果。
5.
844. 比较含退格的字符串
给定
S
和
T
两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。
#
代表退格字符。
注意：
如果对空文本输入退格字符，文本继续为空。
class Solution {
public:
bool backspaceCompare(string S, string T) {
stack<char> S1;
stack<char> T1;
for (auto x : S)
{
if (x != '#')
S1.push(x);
if (x == '#' && !S1.empty())
S1.pop();
}
for (auto x : T)
{
if (x != '#')
T1.push(x);
if (x == '#' && !T1.empty())
T1.pop();
}
if (S1 == T1)
return true;
else
return false;
}
};
6.
897. 递增顺序搜索树
给你一棵二叉搜索树，请你
按中序遍历
将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。
class Solution {
public:
TreeNode* increasingBST(TreeNode* root) {
TreeNode *p = root, top, *prev = ⊤
stack<TreeNode*> s;
while (!s.empty() || p) {
while (p) s.push(p), p = p->left;
if (!s.empty()) {
p = s.top(), s.pop();
prev->right = p, prev = p;
p->left = NULL, p = p->right;
}
}
return top.right;
}
};
7
.
1021. 删除最外层的括号
有效括号字符串为空
""
、
"(" + A + ")"
或
A + B
，其中
A
和
B
都是有效的括号字符串，
+
代表字符串的连接。
-
例如，
""
，
"()"
，
"(())()"
和
"(()(()))"
都是有效的括号字符串。
如果有效字符串
s
非空，且不存在将其拆分为
s = A + B
的方法，我们称其为
原语（primitive）
，其中
A
和
B
都是非空有效括号字符串。给出一个非空有效字符串
s
，考虑将其进行原语化分解，使得：
s = P_1 + P_2 + ... + P_k
，其中
P_i
是有效括号字符串原语。对
s
进行原语化分解，删除分解中每个原语字符串的最外层括号，返回
s
class Solution {
public:
string removeOuterParentheses(string S) {
string res = "";
stack<char> mystack;
for (int i = 0; i < S.size(); i++) {
if (S[i] == ')')
mystack.pop();
if (!mystack.empty())
res+=S[i];
if (S[i] == '(')
mystack.push('(');
}
return res;
}
};
8.
1047. 删除字符串中的所有相邻重复项
给出由小写字母组成的字符串
S
，
重复项删除操作
会选择两个相邻且相同的字母，并删除它们。在 S 上反复执行重复项删除操作，直到无法继续删除。在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
class Solution {
public:
string removeDuplicates(string S) {
int top = 0;
for (char ch : S) {
if (top == 0 || S[top - 1] != ch) {
S[top++] = ch;
} else {
top--;
}
}
S.resize(top);
return S;
}
};
9.
1441. 用栈操作构建数组
给你一个目标数组
target
和一个整数
n
。每次迭代，需要从
list = {1,2,3..., n}
中依序读取一个数字。请使用下述操作来构建目标数组
target
：
-
Push
：从
list
中读取一个新元素， 并将其推入数组中。 -
Pop
：删除数组中的最后一个元素。 - 如果目标数组构建完成，就停止读取更多元素。
题目数据保证目标数组严格递增，并且只包含
1
到
n
之间的数字。请返回构建目标数组所用的操作序列。题目数据保证答案是唯一的。
class Solution {
public:
vector<string> buildArray(vector<int>& target, int n) {
int start = 1;
vector<string> res;
for(int i = 0; i < target.size(); ++i){
while(start < target[i]){
res.push_back("Push");
res.push_back("Pop");
start++;
}
if(start == target[i]){
res.push_back("Push");
start++;
}
}
return res;
}
};
10.
1475. 商品折扣后的最终价格
给你一个数组
prices
，其中
prices[i]
是商店里第
i
件商品的价格。
商店里正在进行促销活动，如果你要买第
i
件商品，那么你可以得到与
prices[j]
相等的折扣，其中
j
是满足
j > i
且
prices[j] <= prices[i]
的
最小下标
，如果没有满足条件的
j
，你将没有任何折扣。
请你返回一个数组，数组中第
i
个元素是折扣后你购买商品
i
最终需要支付的价格。
class Solution {
public:
vector<int> finalPrices(vector<int>& prices) {
//维护一个价格单调递增的栈存储索引值
//若当前价格小于栈顶所指价格，则栈顶索引值出栈，计算该索引处折扣后的价格，直到栈为空或当前价格大于栈顶所指价格
//将当前索引入栈
if(prices.empty()) return {};
stack<int> s;
int len=prices.size();
vector<int> ans(len);
s.push(0); //将第一个元素的索引入栈
for(int i=1;i<len;++i)
{
while(!s.empty()&&prices[i]<=prices[s.top()])
{
ans[s.top()]=prices[s.top()]-prices[i]; //计算折扣后的价格
s.pop(); //出栈
}
s.push(i);
}
while(!s.empty()) //剩余的是没有折扣的
{
ans[s.top()]=prices[s.top()];
s.pop();
}
return ans;
}
};
11.
1544. 整理字符串
给你一个由大小写英文字母组成的字符串
s
。一个整理好的字符串中，两个相邻字符
s[i]
和
s[i+1]
，其中
0<= i <= s.length-2
，要满足如下条件:
-
若
s[i]
是小写字符，则
s[i+1]
不可以是相同的大写字符。 -
若
s[i]
是大写字符，则
s[i+1]
不可以是相同的小写字符。
请你将字符串整理好，每次你都可以从字符串中选出满足上述条件的
两个相邻
字符并删除，直到字符串整理好为止。请返回整理好的
字符串
。题目保证在给出的约束条件下，测试样例对应的答案是唯一的。
注意：
空字符串也属于整理好的字符串，尽管其中没有任何字符。
class Solution {
public:
string makeGood(string s) { //就地操作
int top = 0;
for(int i = 0; i < s.size(); i++){
if(top == 0){
s[top++] = s[i];
}else{
if(s[top - 1] != s[i] && tolower(s[i]) == tolower(s[top - 1])){
top--;
}else{
s[top++] = s[i];
}
}
}
s.resize(top);
return s;
}
};
12.
1598. 文件夹操作日志搜集器
每当用户执行变更文件夹操作时，LeetCode 文件系统都会保存一条日志记录。
下面给出对变更操作的说明：
-
"../"
：移动到当前文件夹的父文件夹。如果已经在主文件夹下，则
继续停留在当前文件夹
。 -
"./"
：继续停留在当前文件夹
。
-
"x/"
：移动到名为
x
的子文件夹中。题目数据
保证总是存在文件夹
x
。
给你一个字符串列表
logs
，其中
logs[i]
是用户在
ith
步执行的操作。文件系统启动时位于主文件夹，然后执行
logs
中的操作。执行完所有变更文件夹操作后，请你找出
返回主文件夹所需的最小步数
。
class Solution {
public:
int minOperations(vector<string>& logs) {
int deep = 0;
for(int i = 0; i < logs.size(); i++){
if(logs[i] == "./") continue;
if(logs[i] == "../"){
deep = max(0, deep - 1);
}else{
deep += 1;
}
}
return deep;
}
};
13.
1614. 括号的最大嵌套深度
如果字符串满足以下条件之一，则可以称之为
有效括号字符串
（valid parentheses string
，可以简写为
VPS
）：
-
字符串是一个空字符串
""
，或者是一个不为
"("
或
")"
的单字符。 -
字符串可以写为
AB
（
A
与
B
字符串连接），其中
A
和
B
都是
有效括号字符串
。 -
字符串可以写为
(A)
，其中
A
是一个
有效括号字符串
。
类似地，可以定义任何有效括号字符串
S
的
嵌套深度
depth(S)
：
-
depth("") = 0
-
depth(C) = 0
，其中
C
是单个字符的字符串，且该字符不是
"("
或者
")"
-
depth(A + B) = max(depth(A), depth(B))
，其中
A
和
B
都是
有效括号字符串
-
depth("(" + A + ")") = 1 + depth(A)
，其中
A
是一个
有效括号字符串
例如：
""
、
"()()"
、
"()(()())"
都是
有效括号字符串
（嵌套深度分别为 0、1、2），而
")("
、
"(()"
都不是
有效括号字符串
。给你一个
有效括号字符串
s
，返回该字符串的
s
嵌套深度
。
class Solution {
public:
int maxDepth(string s) {
int max = 0;
stack<char> st;
for(int i = 0; i < s.size(); ++i){
if(s[i] == '('){
st.push('(');
}
if(st.size() > max){
max = st.size();
}
if(s[i] == ')'){
st.pop();
}
}
return max;
}
};
14.
1700. 无法吃午餐的学生数量
学校的自助午餐提供圆形和方形的三明治，分别用数字
0
和
1
表示。所有学生站在一个队列里，每个学生要么喜欢圆形的要么喜欢方形的。
餐厅里三明治的数量与学生的数量相同。所有三明治都放在一个
栈
里，每一轮：
-
如果队列最前面的学生
喜欢
栈顶的三明治，那么会
拿走它
并离开队列。 -
否则，这名学生会
放弃这个三明治
并回到队列的尾部。
这个过程会一直持续到队列里所有学生都不喜欢栈顶的三明治为止。
给你两个整数数组
students
和
sandwiches
，其中
sandwiches[i]
是栈里面第
i
个三明治的类型（
i = 0
是栈的顶部），
students[j]
是初始队列里第
j
名学生对三明治的喜好（
j = 0
是队列的最开始位置）。请你返回无法吃午餐的学生数量。
class Solution {
public:
int countStudents(vector<int>& students, vector<int>& sandwiches) {
int l1=0,r1=0;
for(auto x:students){
if(x==1) l1++;
else r1++;
}
for(auto x:sandwiches){
if(x==1&&l1>0) l1--;
else if(x==0&&r1>0) r1--;
else break;
}
return l1+r1;
}
};