栈 --面试经典150题

简化路径(medium)

做题过程

思路是对的，主要就是用栈和分类讨论，但是还有熟悉语言特性什么的做的不好。

算法概述

本题要求为简化文件路径。用栈管理输入的复杂路径。

时间复杂度为O(n)
空间复杂度为O(n)

JAVA

class Solution {
    public String simplifyPath(String path) {
        StringBuilder ans = new StringBuilder();
        Deque<String> deque = new LinkedList<>();
        String[] components = path.split("/");  // 将路径按 '/' 切分成组件

        for (String component : components) {
            if (component.equals("") || component.equals(".")) {
                // 如果是空字符串（连续的'/'）或者'.'，直接跳过
                continue;
            }
            if (component.equals("..")) {
                // 如果是'..'，弹出栈顶元素（回到上一级路径）
                if (!deque.isEmpty()) {
                    deque.pollLast();
                }
            } else {
                // 普通的路径组件，入栈
                deque.offerLast(component);
            }
        }

        // 如果栈是空的，返回根路径 "/"
        if (deque.isEmpty()) {
            return "/";
        }

        // 边删除栈中元素边拼凑答案
        while (!deque.isEmpty()) {
            ans.append("/").append(deque.pollFirst());
        }

        return ans.toString();
    }
}

总结

最重要的是先用 split('\')把文件路径分为一级一级的部分，这样会极大简化后续的分类工作、还有像 边删节栈边拼接字符串 的技巧也非常重要。
还有：

一定要记得用equals()
C++也有面向STL的split(string, "\")

逆波兰表达式

做题过程

需要用正则判断数字，而且还是对deque的操作不熟悉。

算法概述

原题

本题要求为计算逆波兰表达式。使用栈即可。

时间复杂度为O(n)
空间复杂度为O(n)

JAVA

class Solution {
    Deque<Integer> deque = new LinkedList<>();
    
    public int evalRPN(String[] tokens) {
        for (String token : tokens) {
            if (token.matches("-?\\d+")) {  
                deque.offer(Integer.parseInt(token));  
            } else {
                calculate(token);  
            }
        }
        
        return deque.peek();  
    }

    private void calculate(String t) {
        int num2 = deque.pollLast();  
        int num1 = deque.pollLast();  

        int temp = 0;
        switch (t) {
            case "+":
                temp = num1 + num2;
                break;
            case "-":
                temp = num1 - num2;
                break;
            case "*":
                temp = num1 * num2;
                break;
            case "/":
                temp = num1 / num2;
                break;
        }
        
        deque.offer(temp);  
    }
}

重要实例方法及属性(JAVA)

poll()和pollLast()：前者是 队列的入队 ，后者才是 栈的弹出栈顶 。

总结

对API和re都不熟悉，很麻烦，必须整理总结一下。

基本计算器(hard)

做题过程

就是栈，但还要带括号时的优先级，比较麻烦。

算法概述

原题

本题为数据结构课程的基本例题（除去乘除法，还更加简单）。但是还有更逆天的解决方法。

JavaScript

/**
 * @param {string} s
 * @return {number}
 */
var calculate = function(s) {
    return eval(s)
};

总结

对于javascript这样的语言，解析字符串的优先级很高，因为是浏览器的脚本语言，所以会提供这样一个不安全但有效的接口。

真的逆天🚀