Java類別Stack

題目：682. Baseball Game

連結：https://leetcode.com/problems/baseball-game/description/

• 等級：Easy

解題思路

1. 利用STACK紀錄需計算數值，遇到符號時進行計算

class Solution {
    public int calPoints(String[] operations) {
        Stack<Integer> save = new Stack<Integer>();
        for (int i = 0; i < operations.length;i++)
        {
            String s = operations[i];
            if (s.equals("C"))
            {
                save.pop();
                
            }
            else if (s.equals("+"))
            {
                int first = save.pop();
                int second = save.peek();
                save.push(first);
                save.push(first + second);
            }
            else if (s.equals("D"))
            {
                int first = save.peek();
                save.push(first * 2);
            }
            else
            {
                save.push(Integer.parseInt(s));
            }
        }

        int sumofStack=0;
        while(!save.isEmpty()){
            sumofStack = sumofStack + save.pop();
        }
        return sumofStack;   
    }
}

• Time complexity: O(n)
• Space complexity: O(n)

題目：71. Simplify Path

連結：https://leetcode.com/problems/simplify-path/description/

• 等級：Medium

解題思路

1. 以”/”進行字串切割
2. “..”指跳到上一層pop取得上一層字串
3. StringBuilder sb = new StringBuilder();進行字串重組

class Solution {
    public String simplifyPath(String path) {
        Stack<String> save = new Stack<String>();
        String arr[] = path.split("/");
        for(int i=0;i<arr.length;i++){
            if(arr[i].isEmpty())//雙//忽略
            {
                continue;
            }
            if(arr[i].equals("..") && !save.empty())//上一層
            {
                save.pop();
            }
            else if(!arr[i].equals("..") && !arr[i].equals("."))
            {
                save.push(arr[i]);//路徑紀錄
            }
        }
        if(save.isEmpty()){
            return "/";
        }

        StringBuilder sb = new StringBuilder();
        while (!save.isEmpty())
        {
            sb.insert(0,save.pop());
            sb.insert(0,"/");
        }
        return sb.toString();
    }
}

• Time complexity: O(n)
• Space complexity: O(1)