Monodyee

这个屌丝很懒，什么也没留下！

热门标签

Leedcode专题之栈（简单题）_栈有效字符串需满足:

作者：Monodyee | 2024-02-25 01:07:30

踩

栈有效字符串需满足:

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 = &top;
        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;
    }
};

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Monodyee/article/detail/137409?site