LeetCode 栈&队列

Input: "()"
Output: true

Input: "()[]{}"
Output: true

Input: "(]"
Output: false

Input: "([)]"
Output: false

Input: "{[]}"
Output: true

public boolean isValid2(String s) {
    if(s.length()<=0){
        return true;
    }
    Stack<Character> stack=new Stack();
    for(int i=0;i<s.length();i++){
        if(s.charAt(i)=='(' || s.charAt(i)=='{' || s.charAt(i)=='['){
            stack.push(s.charAt(i));
        }else{
            //注意这种情况，一开始就是])}
            if(stack.isEmpty()){
                return false;
            }
            char p=s.charAt(i);
            if( (p==')' && stack.pop()!='(') || (p==']' && stack.pop()!='[') || (p=='}' && stack.pop()!='{')){
                return false;
            }
        }
    }
    return stack.isEmpty();
}

public class MyStack<T>{

    T [] objValues=null;

    int top=-1;

    public MyStack(int size){
        objValues= (T[]) new Object[size];
    }

    public void push(T obj){
        objValues[++top]=obj;
    }

    public T peek(){
        if (top<0) {
            throw new RuntimeException("stack is isEmpty");
        }
        return objValues[top];
    }

    public T pop(){
        if (top<0) {
            throw new RuntimeException("stack is isEmpty");
        }
        //覆盖
        return objValues[top--];
    }

    public boolean isEmpty(){
        return top<0;
    }
}

public boolean isValid(String s) {
    if(s.length()<=0){
        return true;
    }
    while(true){
        int len=s.length();
        s=s.replace("{}","");
        s=s.replace("()","");
        s=s.replace("[]","");
        if (len==s.length()) {
            break;
        }
    }
    return "".equals(s);
}

输入："()"
输出：True

输入："(*)"
输出：True

输入："(*))"
输出：True

public boolean checkValidString(String s) {
    Stack<Integer> bracketStack=new Stack<>();
    Stack<Integer> starStack=new Stack<>();
    for (int i=0;i<s.length();i++) {
        if (s.charAt(i)=='(') {
            bracketStack.push(i);
        }else if(s.charAt(i)=='*'){
            starStack.push(i);
        }else{
            if (bracketStack.isEmpty()) {
                if (starStack.isEmpty()) {
                    return false;
                }
                starStack.pop();
            }else{
                bracketStack.pop();
            }
        }
    }
    //消除左括号
    while(!starStack.isEmpty() && !bracketStack.isEmpty()){
        if(starStack.peek()>bracketStack.peek()){ //这里的逻辑不太好，其实可以很简单
            bracketStack.pop();
        }
        starStack.pop();
    }
    return bracketStack.isEmpty();
}

//2020.4.10 重写一下
public boolean checkValidString(String s) {
    Deque<Integer> stack=new ArrayDeque<>();
    Deque<Integer> helpStack=new ArrayDeque<>();
    for(int i=0;i<s.length();i++){
        if(s.charAt(i)=='('){
            stack.push(i);
        }else if(s.charAt(i)==')'){
            if(!stack.isEmpty()){
                stack.pop();
            }else{
                if(helpStack.isEmpty()){
                    return false;
                }
                helpStack.pop();
            }
        }else{
            helpStack.push(i);
        }
    }
    while(!stack.isEmpty() && !helpStack.isEmpty()){
        if(stack.pop()>helpStack.pop()){
            return false;
        }
    }
    return stack.isEmpty();
}

输入："())"
输出：1

输入："((("
输出：3

输入："()"
输出：0

输入："()))(("
输出：4

public int minAddToMakeValid(String S) {
    int left=0,right=0;
    int wa=0;
    for(int i=0;i<S.length();i++){
        if(S.charAt(i)=='('){
            left++;
        }else{
            if(left>0){
                left--;
            }else{
                wa++;
            }
        }
    }
    return wa+left;
}

s = "3[a]2[bc]", 返回 "aaabcbc".
s = "3[a2[c]]", 返回 "accaccacc".
s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".

public String decodeString(String s) {
    if (s==null || s.length()<=0) {
        return "";
    }
    //转换为 StringBuilder 比较好处理，且效率较高
    StringBuilder sb=new StringBuilder(s);
    Stack<Integer>  stack=new Stack<>();
    int i=0;//遍历索引
    while(i<sb.length()) {
        if (sb.charAt(i)=='[') {
            stack.push(i);
        }else if(sb.charAt(i)==']'){
            int left=stack.pop();//对应左括号索引
            String temp=sb.substring(left+1,i);//相邻括号中的字符
            int preInt=left;
            //'['前的数字，一开始以为只是个位数，还是挺麻烦的
            while(preInt-1>=0 && sb.charAt(preInt-1)>='0' && sb.charAt(preInt-1) <='9'){
                preInt--;
            }
            //repeat 次数
            int repeat=Integer.valueOf(sb.substring(preInt,left));
            //删除 k[encoded_string] 
            sb.delete(preInt,Math.min(i+1,sb.length()));
            for (int j=0;j<repeat;j++) {
                //从 k 位置重新插入字符
                sb.insert(preInt,temp);
            }
            //重新定位索引到尾部
            i=preInt+(repeat*temp.length())-1;
        }
        i++;
    }
    return sb.toString();
}

private int index=0; //字符索引下标

public String decodeString(String s) {
    if (s==null || s.length()<=0) {
        return "";
    }
    String sb="";
    while(index<s.length()){
        if (s.charAt(index)==']') { //遇到右括号就结束
            index++;//index 定位到右括号下一个
            return sb;
        }else if(s.charAt(index)>='0' && s.charAt(index)<='9'){
            int temp=index;
            while(index<s.length() && s.charAt(index)!='['){
                index++;
            }
            int repeat=Integer.valueOf(s.substring(temp,index));
            index++;//跳过'['
            String rs=decodeString(s);//从左括号开始
            for (int i=0;i<repeat;i++) {
                sb+=rs;
            }
        }else{
            sb+=s.charAt(index++);
        }
    }
    return sb;
}

输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]

输入：["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

public void reverseString(char[] s) {
    if(s==null||s.length<=1)return;
    reverseString(s,0,s.length-1);
}

public void reverseString(char[] s,int l,int r) {
    if(l>=r){
        return;
    }
    char temp=s[l];
    s[l]=s[r];
    s[r]=temp;
    reverseString(s,++l,--r);
}

输入：["2", "1", "+", "3", "*"]
输出：9
解释：((2 + 1) * 3) = 9

输入：["4", "13", "5", "/", "+"]
输出：6
解释：(4 + (13 / 5)) = 6

输入：["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
输出：22
解释：
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

public static int evalRPN(String[] tokens) {
    //上面自己封装的 Stack
    MyStack<Integer> stack=new MyStack<>(tokens.length);
    for (int i=0;i<tokens.length;i++) {
        if("+".equals(tokens[i])){
            stack.push(stack.pop()+stack.pop());
        } else if("-".equals(tokens[i])){
            int rd1=stack.pop();
            int rd2=stack.pop();
            stack.push(rd2-rd1);
        }else if("*".equals(tokens[i])){
            stack.push(stack.pop()*stack.pop());
        }else if("/".equals(tokens[i])){
            int div1=stack.pop();
            int div2=stack.pop();
            stack.push(div2/div1);
        }else{
            stack.push(Integer.valueOf(tokens[i]));
        }
    }
    return stack.peek();
}

输入："/home/"
输出："/home"
解释：注意，最后一个目录名后面没有斜杠。

输入："/../"
输出："/"
解释：从根目录向上一级是不可行的，因为根是你可以到达的最高级。

输入："/home//foo/"
输出："/home/foo"
解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。

输入："/a/./b/../../c/"
输出："/c"

输入："/a/../../b/../c//.//"
输出："/c"

输入："/a//b////c/d//././/.."
输出："/a/b/c"

public static String simplifyPath(String path) {
    MyStack<String> stack=new MyStack<>(path.length());
    StringBuilder str=new StringBuilder(path);
    //这里划分出来有一部分是空的 ""
    String[] s=path.split("/");
    for (int i=0;i<s.length;i++) {
        if (!stack.isEmpty() && s[i].equals("..")) {
            //.. 回溯
            stack.pop();
        }else if (!".".equals(s[i]) && !"".equals(s[i]) && !s[i].equals("..") ) {
            //普通的英文字符 abcd
            stack.push(s[i]);
        }
    }
    if (stack.isEmpty()) {
        return "/";
    }
    StringBuilder res=new StringBuilder();
    for (int i=0;i<stack.size(); i++) {
        res.append("/"+stack.get(i));   
    }
    return res.toString();
}

//自己封装的 stack
public class MyStack<T>{

    T [] objValues=null;

    int top=-1;

    public MyStack(int size){
        objValues= (T[]) new Object[size];
    }

    public void push(T obj){
        objValues[++top]=obj;
    }

    public T peek(){
        if (top<0) {
            throw new RuntimeException("stack is isEmpty");
        }
        return objValues[top];
    }

    public T pop(){
        if (top<0) {
            throw new RuntimeException("stack is isEmpty");
        }
        //覆盖
        return objValues[top--];
    }

    public T get(int index){
        if (index>top || index < 0) {
            throw new RuntimeException("index is wrong");
        }
        return objValues[index];
    }

    public boolean isEmpty(){
        return top<0;
    }

    public int size(){
        return top+1;
    }
}

MyStack stack = new MyStack();

stack.push(1);
stack.push(2);  
stack.top();   // returns 2
stack.pop();   // returns 2
stack.empty(); // returns false

class MyStack {

    private ArrayDeque<Integer> queue=null;

    /** Initialize your data structure here. */
    public MyStack() {
        queue=new ArrayDeque();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        queue.add(x);
        int size=queue.size();
        //除了新加入的元素，其他的元素都出队再入队，将新加入的元素推置队列头
        while(size-- >1){
            queue.add(queue.pop());
        }
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
       return  queue.pop();
    }
    
    /** Get the top element. */
    public int top() {
        return queue.peek();
    }

    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue.isEmpty();
    }
}

public class MyStack{
   //形式上 q1 是负责进栈 q2 负责出栈
    private LinkedList inQueue=new LinkedList(); 
    private LinkedList outQueue=new LinkedList();

    private  void  add(Object obj){
        inQueue.add(obj);
    }

    private Object pop(){
        // q1 ----> q2 留一个
        while(inQueue.size()>1){
            outQueue.add(inQueue.poll());
        }
        //交换 q1,q2 的引用
        LinkedList temp;
        temp=inQueue;
        inQueue=outQueue;
        outQueue=temp;
        return outQueue.poll();
    }

    private Object peek(){
        //q1 --->q2 留一个，最后一个不 poll, 最后 poll
        while(inQueue.size()>1){
            outQueue.add(inQueue.poll());
            if(inQueue.size()==1){
                outQueue.add(inQueue.peek());
            }
        }
        //交换 q1,q2 的引用
        LinkedList temp;
        temp=inQueue;
        inQueue=outQueue;
        outQueue=temp;
        return outQueue.poll();
    }
}

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);  
queue.peek();  // returns 1
queue.pop();   // returns 1
queue.empty(); // returns false

class MyQueue {

    Stack<Integer> inStack=null;

    Stack<Integer> outStack=null;
    /** Initialize your data structure here. */
    public Stack2Queue232() {
        inStack=new Stack<>();
        outStack=new Stack<>();
    }

    /** Push element x to the back of queue. */
    public void push(int x) {
        inStack.push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        s2s();
        return outStack.pop();
    }

    /** Get the front element. */
    public int peek() {
        s2s();
        return outStack.peek();
    }

    /** Returns whether the queue is empty. */
    public boolean empty() {
        return outStack.isEmpty() && inStack.isEmpty();
    }

    private void s2s(){
        if (outStack.isEmpty()) {
            while(!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }     
    }
}

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

class MinStack {

    /** initialize your data structure here. */
    private Stack<Integer> stack=null;

    private Stack<Integer> helpStack=null;

    public MinStack() {
        stack=new Stack<>();
        helpStack=new Stack<>();
    }
    
    public void push(int x) {
        stack.push(x);
        if (helpStack.isEmpty()) {
            helpStack.push(x);
        }else{
            if (helpStack.peek()>x) {
                helpStack.push(x);
            }else{
                helpStack.push(helpStack.peek());
            }
        }
    }
    
    public void pop() {
        stack.pop();
        helpStack.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return helpStack.peek();
    }
}

class MinStack {

    /** initialize your data structure here. */
    private Stack<Integer> stack=null;

    private Stack<Integer> helpStack=null;

    public MinStack() {
        stack=new Stack<>();
        helpStack=new Stack<>();
    }

    public void push(int x) {
        stack.push(x);
        if (helpStack.isEmpty()) {
            helpStack.push(x);
        }else if (x<=helpStack.peek()) {
            //相等的也要入栈，不然不好控制后面出栈
            helpStack.push(x);
        }
    }
    
    public void pop() {
        int top=stack.pop();
        //和辅助栈栈顶相同就出栈
        if(top==helpStack.peek()){
            helpStack.pop();
        }
        /*
        if(stack.pop()==helpStack.peek()){
            helpStack.pop();
        }*/
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return helpStack.peek();
    }
}

public class MinStack155_2{
    /** initialize your data structure here. */
    private Stack<Integer> stack=null;

    private int min=0;

    public MinStack155_2() {
        stack=new Stack<>();
    }
    
    public void push(int x) {
        if (stack.isEmpty()) {
            min=x;
            stack.push(0);
        }else{
            int diff=x-min;
            min=diff>0?min:x;
            stack.push(diff);
        }
    }
    
    public void pop() {
        int diff=stack.pop();
        //小于等于 0 说明 min 就是当前真实的栈顶元素，也就是说 min-minPre=diff
        min=diff<=0?min-diff:min;
    }
    
    /*public int top() {
        int diff=stack.peek();
        return diff<=0?min:diff-min;
    }*/
    
    public int getMin() {
        return min;
    }
}

Examples:
Input: N = 1, K = 1
Output: 0

Input: N = 2, K = 1
Output: 0

Input: N = 2, K = 2
Output: 1

Input: N = 4, K = 5
Output: 1

Explanation:
row 1: 0
row 2: 01
row 3: 0110
row 4: 01101001

  第一行：0
  第二行：01
  第三行：01|10
  第四行：01 10|10 01
  第五行：01 10 10 01|10 01 01 10
  第六行：01 10 10 01 10 01 01 10 | 10 01 01 10 01 10 10 01

public int kthGrammar(int N, int K) {
    if(K==1 || N==1){
        return 0;
    }
    if(K==2){
        return 1;
    }
    int len=1<<(N-1); //当前行长度
    if(K>len/2){ //大于 1/2
        //结合上面的规律，找前半部分和自己等价的位置
        if(N%2!=0){ 
            K=len-K+1;
        }else{
            if(K%2==0){
                K=len-K+2;  
            }else{
                K=len-K;
            }
        }
    }
    //去上一行继续
    return kthGrammar(N-1,K);
}

//01 排列
//              0
//          /        \   
//      0                1
//    /   \            /    \
//  0       1        1       0
// / \     /  \     /  \    / \ 
//0   1   1    0   1    0  0   1

public int kthGrammar(int N, int K) {
    if (K==1) return 0;
    //(K+1)/2 是对应父节点的 index
    int parent=kthGrammar(N-1,(K+1)/2);
    //取反
    int f_parent=-(parent-1);
    if (K%2==0) {
        return f_parent;
    }
    return parent;
}

public static int kthGrammar3(int N, int K) {
    boolean r=false;
    while(K>1){
        if (K%2==0) {
            K=K/2;
            r=!r;
        }else{
            K=(K+1)/2;
        }
    }
    return r?1:0;
}

public static double fastPow(double x,int n){
    if(n==0){
        return 1;
    }
    if(n<0){
        x=1/x;
        n=-n;
    }
    double res=fastPow(x,n/2);
    if(n%2==0){
        return res*res;
    }
    return res*res*x;
}

public static double myPow(double x, int n) {
    if(n<0){
        x=1/x;
        n=-n;
    }
    return fastPow(x,n);
} 

public static double fastPow(double x,int n){
    if(n==0){
        return 1.0;
    }
    double  half=fastPow(x,n/2);
    if(n%2==0)
        return half*half;
    return half*half*x;
}

输入：s = "RLRRLLRLRL"
输出：4
解释：s 可以分割为 "RL", "RRLL", "RL", "RL", 每个子字符串中都包含相同数量的 'L' 和 'R'。

输入：s = "RLLLLRRRLR"
输出：3
解释：s 可以分割为 "RL", "LLLRRR", "LR", 每个子字符串中都包含相同数量的 'L' 和 'R'。

输入：s = "LLLLRRRR"
输出：1
解释：s 只能保持原样 "LLLLRRRR".

public static int balancedStringSplit(String s) {
    if (s.length()%2==1) {
        return 0;
    }
    Stack<Character> stack=new Stack<>();
    int count=0;
    for(int i=0;i<s.length();i++){
        if (!stack.isEmpty() ){
            if(s.charAt(i)==stack.peek()) {
                stack.push(s.charAt(i));    
            }else{
                stack.pop();
                if (stack.isEmpty()) {
                    count++;
                }
            }
        }else{
            stack.push(s.charAt(i));
        }
    }
    return count;
}

输入：s = "lee(t(c)o)de)"
输出："lee(t(c)o)de"
解释："lee(t(co)de)" , "lee(t(c)ode)" 也是一个可行答案。