代码随想录九| 20. 有效的括号、1047. 删除字符串中的所有相邻重复项、150. 逆波兰表达式求值

20. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

动画如下：

20.有效括号

第一种情况，字符串里左方向的括号多余了，所以不匹配。
第二种情况，括号没有多余，但是括号的类型没有匹配上。
第三种情况，字符串里右方向的括号多余了，所以不匹配。

//辅助函数：判断栈顶元素与输入的括号是否为一对。若不是，则返回False
int notMatch(char par, char* stack, int stackTop) {
    switch(par) {
        case ']':
            return stack[stackTop - 1] != '[';
        case ')':
            return stack[stackTop - 1] != '(';
        case '}':
            return stack[stackTop - 1] != '{';
    }
    return 0;
}

bool isValid(char * s){
    int strLen = strlen(s);
    //开辟栈空间
    char stack[5000];
    int stackTop = 0;

    //遍历字符串
    int i;
    for(i = 0; i < strLen; i++) {
        //取出当前下标所对应字符
        char tempChar = s[i];
        //若当前字符为左括号，则入栈
        if(tempChar == '(' || tempChar == '[' || tempChar == '{')
            stack[stackTop++] = tempChar;
        //若当前字符为右括号，且栈中无元素或右括号与栈顶元素不符，返回False
        else if(stackTop == 0 || notMatch(tempChar, stack, stackTop))
            return 0;
        //当前字符与栈顶元素为一对括号，将栈顶元素出栈
        else
            stackTop--;
    }
    //若栈中有元素，返回False。若没有元素（stackTop为0），返回True
    return !stackTop;
}

java写法

class Solution {
    public boolean isValid(String s) {
        Deque<Character> deque = new LinkedList<>();
        char ch;
        for (int i = 0; i < s.length(); i++) {
            ch = s.charAt(i);
            //碰到左括号，就把相应的右括号入栈
            if (ch == '(') {
                deque.push(')');
            }else if (ch == '{') {
                deque.push('}');
            }else if (ch == '[') {
                deque.push(']');
            } else if (deque.isEmpty() || deque.peek() != ch) {
                return false;
            }else {//如果是右括号判断是否和栈顶元素匹配
                deque.pop();
            }
        }
        //最后判断栈中元素是否匹配
        return deque.isEmpty();
    }
}

题目链接

文章链接

视频链接

1047. 删除字符串中的所有相邻重复项

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。在S上反复执行重复项删除操作，直到无法继续删除。

用栈来存放，存放遍历过的元素，当遍历当前的这个元素的时候，去栈里看是不是遍历过相同数值的相邻元素，然后再去做对应的消除操作。从栈中弹出剩余元素，此时是字符串ac，因为从栈里弹出的元素是倒序的，所以再对字符串进行反转一下，就得到了最终的结果。如动画所示：

1047.删除字符串中的所有相邻重复项

递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数。

在企业项目开发中，尽量不要使用递归！在项目比较大的时候，由于参数多，全局变量等等，使用递归很容易判断不充分return的条件，非常容易无限递归（或者递归层级过深），造成栈溢出错误（这种问题还不好排查！）

方法一：使用栈

char * removeDuplicates(char * s){
    //求出字符串长度
    int strLength = strlen(s);
    //开辟栈空间。栈空间长度应为字符串长度+1（为了存放字符串结束标志''）
    char* stack = (char*)malloc(sizeof(char) * strLength + 1);
    int stackTop = 0;

    int index = 0;
    //遍历整个字符串
    while(index < strLength) {
        //取出当前index对应字母，之后index+1
        char letter = s[index++];
        //若栈中有元素，且栈顶字母等于当前字母（两字母相邻）。将栈顶元素弹出
        if(stackTop > 0 && letter == stack[stackTop - 1])
            stackTop--;
        //否则将字母入栈
        else
            stack[stackTop++] = letter;
    }
    //存放字符串结束标志''
    stack[stackTop] = '';
    //返回栈本身作为字符串
    return stack;
}

java写法

//字符串作为栈
class Solution {
    public String removeDuplicates(String s) {
        // 将 res 当做栈
        // 也可以用 StringBuilder 来修改字符串，速度更快
        // StringBuilder res = new StringBuilder();
        StringBuffer res = new StringBuffer();
        // top为 res 的长度
        int top = -1;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // 当 top > 0,即栈中有字符时，当前字符如果和栈中字符相等，弹出栈顶字符，同时 top--
            if (top >= 0 && res.charAt(top) == c) {
                res.deleteCharAt(top);
                top--;
            // 否则，将该字符 入栈，同时top++
            } else {
                res.append(c);
                top++;
            }
        }
        return res.toString();
    }
}

方法二：双指针法

char * removeDuplicates(char * s){
    //创建快慢指针
    int fast = 0;
    int slow = 0;
    //求出字符串长度
    int strLength = strlen(s);
    //遍历字符串
    while(fast < strLength) {
        //将当前slow指向字符改为fast指向字符。fast指针+1
        char letter = s[slow] = s[fast++];
        //若慢指针大于0，且慢指针指向元素等于字符串中前一位元素，删除慢指针指向当前元素
        if(slow > 0 && letter == s[slow - 1])
            slow--;
        else
            slow++;
    }
    //在字符串结束加入字符串结束标志''
    s[slow] = 0;
    return s;
}

java写法

class Solution {
    public String removeDuplicates(String s) {
        char[] ch = s.toCharArray();
        int fast = 0;
        int slow = 0;
        while(fast < s.length()){
            // 直接用fast指针覆盖slow指针的值
            ch[slow] = ch[fast];
            // 遇到前后相同值的，就跳过，即slow指针后退一步，下次循环就可以直接被覆盖掉了
            if(slow > 0 && ch[slow] == ch[slow - 1]){
                slow--;
            }else{
                slow++;
            }
            fast++;
        }
        return new String(ch,0,slow);
    }
}

题目链接

文章链接

视频链接

150. 逆波兰表达式求值

逆波兰表达式是一种后缀表达式，后缀就是指运算符写在后面。

中缀表达式 ( 1 + 2 ) * ( 3 + 4 ) 的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

（后缀表达式对计算机友好，不用考虑优先级）

示例 1：

输入: ["2", "1", "+", "3", " * "]
输出: 9
解释: 该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例 2：

输入: ["4", "13", "5", "/", "+"]
输出: 6
解释: 该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

示例 3：

输入: ["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

遍历表达式中的每个元素，如果是数字，则将其压入栈中；如果是运算符，则从栈中弹出两个元素，进行相应的运算，并将结果压入栈中。最终，栈中只剩下一个元素，即为表达式的值。

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int* stack;  // 栈
    int top;     // 栈顶指针
    int size;    // 栈的大小
} Stack;

Stack* createStack(int size) {
    Stack* stack = (Stack*)malloc(sizeof(Stack));      // 分配内存给栈
    stack->stack = (int*)malloc(sizeof(int) * size);   // 分配内存给栈数组
    stack->top = -1;                                   // 初始化栈顶指针为-1
    stack->size = size;                                // 记录栈的大小
    return stack;
}

void push(Stack* stack, int x) {
    stack->stack[++stack->top] = x;    // 将元素压入栈中，同时将栈顶指针后移一位
}

int pop(Stack* stack) {
    return stack->stack[stack->top--]; // 弹出栈顶元素，同时将栈顶指针前移一位
}

bool isEmpty(Stack* stack) {
    return stack->top == -1;            // 检查栈是否为空
}

int evalRPN(char** tokens, int tokensSize) {
    Stack* stack = createStack(tokensSize); // 创建一个大小为tokensSize的栈
    for (int i = 0; i < tokensSize; i++) {
        if (strcmp(tokens[i], "+") != 0 && strcmp(tokens[i], "-") != 0 &&
            strcmp(tokens[i], "*") != 0 && strcmp(tokens[i], "/") != 0) { // 如果是数字，则将其转换为整数，并压入栈中
            push(stack, atoi(tokens[i]));
        } else {                                                         // 如果是运算符，则从栈中弹出两个元素，进行相应的运算，并将结果压入栈中
            int b = pop(stack);
            int a = pop(stack);
            switch (tokens[i][0]) {
                case '+': push(stack, a + b); break;
                case '-': push(stack, a - b); break;
                case '*': push(stack, a * b); break;
                case '/': push(stack, a / b); break;
            }
        }
    }
    int result = pop(stack);   // 弹出栈中最后剩下的元素，即为表达式的值
    free(stack->stack);        // 释放栈数组内存
    free(stack);               // 释放栈内存
    return result;
}

java写法

class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new LinkedList();
        for (String s : tokens) {
            if ("+".equals(s)) {        // leetcode 内置jdk的问题，不能使用==判断字符串是否相等
                stack.push(stack.pop() + stack.pop());      // 注意 - 和/ 需要特殊处理
            } else if ("-".equals(s)) {
                stack.push(-stack.pop() + stack.pop());
            } else if ("*".equals(s)) {
                stack.push(stack.pop() * stack.pop());
            } else if ("/".equals(s)) {
                int temp1 = stack.pop();
                int temp2 = stack.pop();
                stack.push(temp2 / temp1);
            } else {
                stack.push(Integer.valueOf(s));
            }
        }
        return stack.pop();
    }
}

题目链接

文章链接

视频链接