博客

Leedcode专题之栈（简单题）

  • Post author:
  • Post category:其他



1.


20. 有效的括号

给定一个只包括

'('

，

')'

，

'{'

，

'}'

，

'['

，

']'

的字符串

s

，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。 
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

遵循下述规则：

  1. 整数

    x

    – 表示本回合新获得分数

    x

  2. "+"

    – 表示本回合新获得的得分是前两次得分的总和。题目数据保证记录此操作时前面总是存在两个有效的分数。

  3. "D"

    – 表示本回合新获得的得分是前一次得分的两倍。题目数据保证记录此操作时前面总是存在一个有效的分数。

  4. "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;
    }
};


版权声明：本文为dyyay521原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。