赞
踩
创造不易,可以点点赞吗~
如有错误,欢迎指出~
目录
把递归代码实现为非递归代码
比如:逆序打印链表
- // 递归方式
- void printList(Node head){
- if(null != head){
- printList(head.next);
- System.out.print(head.val + " ");
- }
- }
-
- // 循环方式
- void printList(Node head){
- if(null == head){
- return;
- }
-
- Stack<Node> s = new Stack<>();
- // 将链表中的结点保存在栈中
- Node cur = head;
- while(null != cur){
- s.push(cur);
- cur = cur.next;
- }
也叫后缀表达式(运算符在操作数的后面),好处是:忽略运算符的优先级
我们平时运算加减乘除的式子其实是 中缀表达式
比如式子a+b*c+(d*e+f)*g转成逆波兰表达式 abc*+de*f+g*+
逆波兰表达式的运算规则:
比如式子1+2*3+(4*5+6)*7
逆波兰表达式1 2 3*4 5*6 +7 *+
……
给你一个字符串数组 tokens
,表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。oj链接
- class Solution {
- public int evalRPN(String[] tokens) {
- Stack<Integer> stack=new Stack<>();
- for(int i=0;i<tokens.length;i++){
- String tmp=tokens[i];
- if(!isOperation(tokens[i])){
- Integer val=Integer.valueOf(tmp);//将字符转化为整形
- stack.push(val);
- }else{
- Integer val2=stack.pop();//val2作为右操作数
- Integer val1=stack.pop();
- switch(tmp){
- case "+":
- stack.push(val1+val2);
- break;
- case "-":
- stack.push(val1-val2);
- break;
- case "*":
- stack.push(val1*val2);
- break;
- case "/":
- stack.push(val1/val2);
- break;
- }
- }
- }
- return stack.pop();
- }
-
- //判断字符是否是 运算符
- public boolean isOperation(String s){
- if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/")){
- return true;
- }
- return false;
- }
- }
括号匹配:栈最终为空,且字符串已经遍历完了
不匹配:
- class Solution {
- public boolean isValid(String s) {
- Stack<Character> stack=new Stack<>();
- for(int i=0;i<s.length();i++){
- char ch=s.charAt(i);
-
- if(ch=='('||ch=='['||ch=='{'){
- stack.push(ch);
- }else{
- //遇到右括号
- if(stack.empty()){
- return false;//栈为空,没有左括号与之匹配
- }else{
- //取栈顶元素左括号 看与当前右括号是否匹配
- char chL=stack.peek();
- if(chL=='('&&ch==')'
- ||chL=='['&&ch==']'
- ||chL=='{'&&ch=='}'){
- stack.pop();//说明当前这个括号匹配,所以要扔出去
- }else{
- return false;
- }
-
- }
- }
- }
- return stack.empty();//如果循环走完,栈为空,返回真
- }
- }
1. 遍历pushV数组,入栈,每次入栈后判断和popV数组的下标j是否一致
2.不一样,继续i++(继续进栈);
一样,出栈,j++
3.出栈时,若一直一样就一直出,遇到不一样的,i++继续入栈;
注意:
stack.peek()==popV[j] 引用类型时要用equals判断,这里为简单类型int.
- public boolean IsPopOrder (int[] pushV, int[] popV) {
- // write code here
- Stack<Integer> stack=new Stack<>();
- int j=0;
- for(int i=0;i<pushV.length;i++){
- stack.push(pushV[i]);
- while(j<popV.length&&!stack.empty()&&
- stack.peek()==popV[j]){
- stack.pop();
- j++;
- }
- }
- return stack.empty();
- }
- }
分别创建两个栈:普通栈 和 最小栈
push存放元素的过程:
pop取元素的过程(返回值是普通站的元素):
每次pop元素时需要判断出栈的元素是不是和最小栈的栈顶元素一样,若一样,最小栈也得pop
top瞄一眼(相当于peek,返回的是普通栈的值)
getMin获取最小栈的栈顶元素
- import java.util.Stack;
-
- class MinStack {
- public Stack<Integer> stack;
- public Stack<Integer> minStack;
-
- public MinStack() {
- stack=new Stack<>();
- minStack=new Stack<>();
- }
-
- public void push(int val) {
- stack.push(val);
- if(minStack.empty()){
- minStack.push(val);
- }else{
- Integer peekVal=minStack.peek();
- if(val<=peekVal){
- minStack.push(val);
- }
- }
- }
-
- public void pop() {
- if (stack.empty()) {
- return;
- }
- int popVal=stack.pop();
- if(popVal==minStack.peek()){
- minStack.pop();
- }
-
- }
-
- public int top() {
- if(stack.empty()){
- return -1;
- }
- return stack.peek();
- }
-
- public int getMin() {
- if(minStack.empty()){
- return -1;
- }
- return minStack.peek();
- }
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。