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

20. 有效的括号

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

有效字符串需满足:

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

动画如下:

20.有效括号

  1. 第一种情况,字符串里左方向的括号多余了 ,所以不匹配。 

    括号匹配1

  2. 第二种情况,括号没有多余,但是 括号的类型没有匹配上。 

    括号匹配2

  3. 第三种情况,字符串里右方向的括号多余了,所以不匹配。 

    括号匹配3

//辅助函数:判断栈顶元素与输入的括号是否为一对。若不是,则返回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();
    }
}

题目链接

文章链接

视频链接