「Leetcode-演算法_Mid1006」從單堆疊到雙堆疊-有解無憂

Mid 1006 笨階乘堆疊/后綴

單堆疊 -- 運算優化 + 堆疊

思路描述

每四個數一組

這四個數中前三個會進行乘、除然后與最后一個相加

Stack 入前三個之和與最后一個數

以 4 舉例

運算式 4 * 3 / 2 + 1 --> (4 * 3 / 2) + 1

以 temp 代表括號內元素運算值
plus 代表括號后元素運算值

回圈入隊 temp 、plus

回圈運算 temp + plus - temp + plus

當 stack.size() == 1 時回傳結果

資料運算程序

測驗 `5`

5 * 4 / 3 + 2 -1
- temp
  - 20
  - 6
- plus
  - 2
- 再處理
- temp
  - 1
- stack
  - 6 2 1

測驗 6

6 * 5 / 4 + 3 - 2 * 1
- temp
  - 30
  - 7
- plus
  - 3
- 再處理
- temp
  - 2
- plus
  - null
- stack
  - 7 3 2

代碼實作

class Solution {
    public int clumsy(int N) {
        // 先乘除 后加減
        
        // 標識
        int temp , result = 0;
        Deque<Integer> stack = new LinkedList<>();

        while (N > 0) {
            
            // 矯正 4 + 1
            if (N > 1) {
                temp = multiplication(N, --N);
            } else {
                temp = N;
            }

            // 作除法
            if (N > 1) {
                stack.offerLast(divsion(temp, --N));
            } else{
                stack.offerLast(temp);
                break;
            }

            if (N > 1) {
                stack.offerLast(--N);
            } else{
                break;
            }
            
            // 后移一位 防止 下一位出錯 因為下一位可能進行乘法
            --N;
        }

        while (stack.size() > 1) {
            stackPlus(1, stack);

            if (stack.size() > 1) {
                stackPlus(-1, stack);
            }
        }

        return stack.pollFirst();
    }

    private int multiplication(int a, int b) {
        return a * b;
    }

    private int divsion(int a, int b) {
        return Math.floorDiv(a, b);
    }

    private void stackPlus(int sign, Deque<Integer> stack) {
        stack.offerFirst(stack.pollFirst() + stack.pollFirst() * sign);
    }
}

演算法分析

時間復雜度: O(n)

空間復雜度: O(1)

雙堆疊 -- 通用計算器

維護雙堆疊

知識堆疊:

后綴運算式(逆波蘭式)
Deque 雙端佇列介面
- 法作用
  
  ll/add 添加元素
  
  fer/remove 洗掉元素
  
  ek/get 讀取元素
  
  支持 語法 + First/Last 對頭、尾實作雙向操作

法	作用
ll/add	添加元素
fer/remove	洗掉元素
ek/get	讀取元素

記錄在這里的一處踩坑:

calculate() 中一開始為了減少區域變數的使用直接用deq.pollLast() 導致減法、除法運算時邏輯上的錯誤

class Solution {
    // 計算器
    public int clumsy(int N) {
        Deque<Integer> numDeq = new LinkedList();
        Deque<Character> operatorDeq = new LinkedList();
        // 運算子優先級
        Map<Character,Integer> priorityMap = new HashMap<>(){
            {
                put('*',2);
                put('/',2);
                put('-',1);
                put('+',1);
            }
        };
        char[] operators = new char[]{'*','/','+','-'};
        
        for (int i = N, index = 0; i > 0 ; --i, ++index) {
            // 數字直接入堆疊
            numDeq.offerLast(i);
            // 取對應運算子
            char operator = operators[index % 4];
            
            // 運算子堆疊不為空 且 堆疊內元素優先級都 高于 當前將入堆疊的運算子 ——》 計算堆疊內所有可以計算的
            while (!operatorDeq.isEmpty() && priorityMap.get(operatorDeq.peekLast()) >= priorityMap.get(operator)) {
                calculate(numDeq, operatorDeq);
            }

            // 運算子入堆疊
            operatorDeq.offerLast(operator);
        }

        // 由于最后一個運算子沒必要入堆疊 所以 取出
        operatorDeq.pollLast();
        while (!operatorDeq.isEmpty()) {
            calculate(numDeq, operatorDeq);
        }
        return numDeq.peekLast();
    }

    // 計算函式-->取出 N 堆疊底兩個元素 與 O 堆疊一個元素去運算;
    private void calculate(Deque<Integer> numDeq, Deque<Character> operatorDeq) {
        // 這里一定要把 兩個都取出來 不然不能算減法和除法
        int addtion = 0 , a = numDeq.pollLast() , b = numDeq.pollLast();
        switch (operatorDeq.pollLast()){
            case '+' : addtion = a + b;break;
            case '-' : addtion = b - a;break;
            case '*' : addtion = a * b;break;
            case '/' : addtion = Math.floorDiv(b , a);break;
        }
        numDeq.offerLast(addtion);
    }

}

雙堆疊的圖示

N=3 index=2

示例: 3index=2