20. Valid Parentheses
有效的括号
解题思路
将括号比较后者后，不同的入栈，相同的出栈，最后字符串遍历结束后栈为空则匹配成功。
public bool IsValid(string s) { //声明字典，括号匹配键值对 Dictionary<char, char> dict = new Dictionary<char, char>(); dict.Add(')', '('); dict.Add(']', '['); dict.Add('}', '{'); Stack<char> stack = new Stack<char>(); //遍历字符s，直到遍历s所有字符结束循环 for (int i = 0; i < s.Length; i++) { //栈空则直接将下个字符入栈，结束本次循环 if (stack.Count == 0) { stack.Push(s[i]); continue; } //获取字典中对应的括号，若和循环中s[i]相等则出栈，否则压入栈中 char temp; dict.TryGetValue(s[i], out temp); if (stack.Peek() == temp) stack.Pop(); else stack.Push(s[i]); } //遍历结束后若栈空，说明括号匹配 if (stack.Count == 0) return true; else return false; }
155. Min Stack
最小栈
解题思路
使用链栈，实现基本的入栈出栈，遍历栈中元素，同时比较其值，取其中最小，最后返回最小值。
public class MinStack { //结点类 public class Node{ public int val; public Node next; public Node(int item){ val=item; next=null; } public Node(){ val=0; next=null; } } //头结点指针和初始化 Node head; /** initialize your data structure here. */ public MinStack() { head=null; } //入栈方法，新入栈的结点成为head public void Push(int x) { if(head==null) head=new Node(x); Node p=new Node(x); p.next=head; head=p; } //出栈方法，head指向其后继结点 public void Pop() { if(head==null) return; head=head.next; } //返回head的值 public int Top() { return head.val; } //遍历链表，同时比较结点的值 public int GetMin() { Node p=head; int minNum=int.MaxValue; while(p.next!=null){ if(p.val<minNum){ minNum=p.val; } p=p.next; } return minNum; } } /** * Your MinStack object will be instantiated and called as such: * MinStack obj = new MinStack(); * obj.Push(x); * obj.Pop(); * int param_3 = obj.Top(); * int param_4 = obj.GetMin(); */
224. Basic Calculator
基本计算器
解题思路
准备两个栈，一个存放数字，一个存放"+"、"-"和"("，遇到")"不用入栈，直接进行操作。
取出一个操作符计算一个数字，直到遇到"("，加上"()"里最后一个数字后将总数入栈，循环往复后最后的表达式时没有括号的。
然后再进行循环遍历操作符栈，将数字进行计算，返回总数。
其中需要注意入栈是一个个字符，而数字不会只是个位数，所以要标记操作符的数量。
只要数字数量超过操作符，再遇到新数字就将数字栈是栈顶元素取出，乘以10加上新数字后入栈。
public class Solution { public int Calculate(string s) { int sum = 0 ; //操作符栈和数字栈 Stack<int> stackNum = new Stack<int>(); Stack<string> stackOpe = new Stack<string>(); //操作符的数量 int opeNum=0; //遍历s for (int i = 0; i < s.Length; i++) { //空字符直接跳过 if(s[i]==' ') continue; //遇到反括号开始计算括号里的数 else if(s[i]==')'){ //括号里的数的大小 int num=0; while(true){ //遇到+、-计算符号执行对应操作 if(stackOpe.Peek()=="+"){ num+=stackNum.Pop(); stackOpe.Pop(); opeNum--; } else if(stackOpe.Peek()=="-"){ num-=stackNum.Pop(); stackOpe.Pop(); opeNum--; } //遇到开括号结束计算 else if(stackOpe.Peek()=="("){ num+=stackNum.Pop(); stackOpe.Pop(); stackNum.Push(num); break; } } } //如果是+、-、)就将其入栈 else if(s[i]=='+'||s[i]=='-'||s[i]=='('){ stackOpe.Push(s[i].ToString()); //但只有+、-算作操作符数量 if(s[i]=='+'||s[i]=='-') opeNum++; } //如果不符合以上情形就是数字，入数字栈 else{ //如果数字栈中数字的数量大于操作符数量，说明这个字符和上一个字符是一个数字 //取出栈顶元素*10后加上该数字后再入栈 if(stackNum.Count-1>=opeNum) stackNum.Push(stackNum.Pop()*10+Convert.ToInt32(s[i].ToString())); else stackNum.Push(Convert.ToInt32(s[i].ToString())); } } //以操作符的数量为长度遍历 int length=stackOpe.Count; for(int i=0;i<length;i++){ //遇到+、-执行对应操作，这时整个表达式没有括号了 if(stackOpe.Peek()=="+"){ sum+=stackNum.Pop(); stackOpe.Pop(); } else if(stackOpe.Peek()=="-"){ sum-=stackNum.Pop(); stackOpe.Pop(); } } //加上栈中最后一个数字得到结果 sum+=stackNum.Peek(); return sum; } }
232. Implement Queue using Stacks
用栈实现队列
解题思路
用栈2接收栈1push出的数据，将栈2的栈顶元素记录后，再把栈2push回栈1
public class MyQueue { Stack<int> stack = new Stack<int>(); /** Initialize your data structure here. */ public MyQueue(){} /** Push element x to the back of queue. */ public void Push(int x){ stack.Push(x); } /** Removes the element from in front of queue and returns that element. */ public int Pop() { //声明一个新的栈2，记录栈1的长度 Stack<int> stack2 = new Stack<int>(); int length = stack.Count; //将栈1push到栈2中 for (int i = 0; i < length; i++) stack2.Push(stack.Pop()); //栈2执行pop操作就相当于栈1出队。 int temp = stack2.Pop(); //再将栈2push到栈1中 for (int i = 0; i < length-1; i++) stack.Push(stack2.Pop()); return temp; } /** Get the front element. */ public int Peek() { //peek的操作和pop的区别在于不移除栈顶元素，length不需要减一 Stack<int> stack2 = new Stack<int>(); int length = stack.Count; for(int i = 0; i < length; i++) stack2.Push(stack.Pop()); int temp = stack2.Peek(); for (int i = 0; i < length; i++) stack.Push(stack2.Pop()); return temp; } /** Returns whether the queue is empty. */ public bool Empty() { return stack.Count == 0; } } /** * Your MyQueue object will be instantiated and called as such: * MyQueue obj = new MyQueue(); * obj.Push(x); * int param_2 = obj.Pop(); * int param_3 = obj.Peek(); * bool param_4 = obj.Empty(); */
496. Next Greater Element I
下一个最大元素Ⅰ
解题思路
每次比较子数组元素在nums中时，都要新声明一个栈进行操作，这个栈否则只能操作一次
public class Solution { public int[] NextGreaterElement(int[] findNums, int[] nums) { int[] put = new int[findNums.Length]; Stack<int> stack = new Stack<int>(); //将nums2倒序入栈 for (int i = nums.Length - 1; i >= 0; i--) stack.Push(nums[i]); //遍历nums1的元素 for (int i = 0; i < findNums.Length; i++) put[i] = CheckItem(findNums[i], nums); return put; } public int CheckItem(int item, int[] nums) { //新建一份临时的nums的栈 Stack<int> temp = new Stack<int>(); for (int i = nums.Length - 1; i >= 0; i--) { temp.Push(nums[i]); } //循环直到栈中为空或找到符合条件的元素 while (true) { //找到元素在nums的位置 if (temp.Peek() == item) { //循环直到栈空或找到符合条件的元素 while (true) { if (temp.Peek() > item) return temp.Peek(); else temp.Pop(); if (temp.Count == 0) break; } } else temp.Pop(); if (temp.Count == 0) break; } return -1; } }
682. Baseball Game
棒球比赛
解题思路
对字符分别处理，每轮分数入栈，最后再把栈中元素相加，f若把or循环中if语句改写成switch后性能下降。
public class Solution { public int CalPoints(string[] ops) { Stack<int> stack = new Stack<int>(); int sum = 0; //遍历字符串 for (int i = 0; i < ops.Length; i++) { //针对C、D、+等情况进行操作 if (ops[i] == "C") stack.Pop(); else if (ops[i] == "D") stack.Push(stack.Peek() * 2); else if (ops[i] == "+") { //记录移除并记录栈顶元素 int pre = stack.Pop(); //记录此时的栈顶元素 int prepre = stack.Peek(); //将移除的元素入栈 stack.Push(pre); //将和入栈 stack.Push(pre + prepre); } //将分数入栈 else stack.Push(Convert.ToInt32(ops[i])); } //记录栈的数据数量，遍历取出计算总和 int length = stack.Count; for (int i = 0; i < length; i++) sum += stack.Pop(); return sum; } }
844. Backspace String Compare
比较含退格符的字符串
解题思路
注意遇到#时，栈执行移除栈顶操作，但若栈中无元素，不能执行移除操作，也不能把#入栈，其他情况都依次入栈。
然后比较两字符串的栈，其中一个空就跳出循环，若另一个也空就说明相等，否则不相等。
如果两栈移除的元素比较不相等，直接返回false。
public class Solution { public bool BackspaceCompare(string S, string T) { Stack<int> stack1 = new Stack<int>(); Stack<int> stack2 = new Stack<int>(); //将S、T两个字符串用栈处理退格符 PopBackspace(stack1, S); PopBackspace(stack2, T); while (true) { //两栈有一个空的就跳出循环，如果有一个没空说明字符串不相等 if (stack1.Count == 0 || stack2.Count == 0) break; //两栈移除栈顶元素并做比较，如果有一次不等就说明字符串不相等 if (stack1.Pop() != stack2.Pop()) return false; } return stack1.Count==0&&stack2.Count==0; } public void PopBackspace(Stack<int> stack, string N) { for (int i = 0; i < N.Length; i++) { //遇到#时移除栈顶元素，但栈不能为空否则报错栈空 if (N[i] == '#' && stack.Count != 0) stack.Pop(); //栈空时遇到了#结束不做任何操作，否则将#入栈了，错误 else if (N[i] == '#') continue; //除以上情况都入栈 else stack.Push(N[i]); } } }