算法总结

标签：总结 Deque int util 算法 import public 小行星

继续字符串的算法题：

package com.chenghaixiang.jianzhi2.day12;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author 程海翔
 * @school 石家庄铁道大学
 */
public class Office036 {
}
//后缀表达式由波兰的逻辑学家卢卡西维兹提出，也称逆波兰表达式。后缀表达式的特点是：没有括号，运算符总是放在和它相关的操作数之后。
//根据 逆波兰表示法，求该后缀表达式的计算结果。
//
//有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack=new LinkedList<>();
        int n=tokens.length;
        for(int i=0;i<n;i++){
            String token=tokens[i];
            if(isNumber(token)){
                stack.push(Integer.parseInt(token));
            }else {
                //弹出数字
                int num2=stack.pop();
                int num1=stack.pop();
                switch (token){
                    case "+":
                        //计算结果压入栈
                        stack.push(num1+num2);
                        break;
                    case "-":
                        stack.push(num1-num2);
                        break;
                    case "*":
                        stack.push(num1*num2);
                        break;
                    case "/":
                        stack.push(num1/num2);
                        break;
                    default:
                }
            }
        }
        return stack.pop();
    }

    //判断是否为数字，是返回true
    boolean isNumber(String token){
        return !("+".equals(token)||"-".equals(token)||"*".equals(token)||"/".equals(token));
    }
}

View Code

package com.chenghaixiang.jianzhi2.day12;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author 程海翔
 * @school 石家庄铁道大学
 */
public class Office037 {
    public static void main(String[] args) {
        int[] aa={1,10,-15};
        Solution01 solution01=new Solution01();
        solution01.asteroidCollision(aa);
    }
}
//给定一个整数数组 asteroids，表示在同一行的小行星。
//
//对于数组中的每一个元素，其绝对值表示小行星的大小，正负表示小行星的移动方向（正表示向右移动，负表示向左移动）。每一颗小行星以相同的速度移动。
//
//找出碰撞后剩下的所有小行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞。

class Solution01 {
    public int[] asteroidCollision(int[] asteroids) {
        Deque<Integer> stacks=new LinkedList<>();
        for(int aster:asteroids){
            boolean alive=true;
            //当栈不为空，当前小行星方向为左，前一个小行星方向为右时进入
            while (alive&&aster<0&&!stacks.isEmpty()&&stacks.peek()>0){
                if(stacks.peek()<-aster){
                    alive=true;
                }else {
                    alive=false;
                }
                // 栈顶小行星爆炸,就是当前值的前一个小行星爆炸
                if(stacks.peek()<=-aster){
                    stacks.pop();
                }
            }
            if(alive){
                stacks.push(aster);
            }
        }
        int size=stacks.size();
        //将栈中元素取出
        int[] res=new int[size];
        for (int i=size-1;i>=0;i--){
            res[i] =stacks.pop();
        }
        return res;
    }
}

View Code

 

标签：总结,Deque,int,util,算法,import,public,小行星
From： https://www.cnblogs.com/chenghaixiang/p/16597161.html