代码随想录算法训练营第十一天 | LeetCode 20. 有效的括号、LeetCode 1047. 删除字符串中的所有相邻重复项、LeetCode 150. 逆波兰表达式求值

简介: 代码随想录算法训练营第十一天 | LeetCode 20. 有效的括号、LeetCode 1047. 删除字符串中的所有相邻重复项、LeetCode 150. 逆波兰表达式求值

1.1 思路

  1. 第一种场景是左括号多余了,比如“([{}]()”;第二种场景是括号没多,但是类型不匹配,比如“[{(]}]”;第三种场景是右括号多余了,比如“[{}]())))”。注意:“[{]}”是相当于第二种情况;而“)(”相当于第三种情况,第一个右括号没有左括号匹配,就相当于多了
  2. 遍历字符串,遇到左括号时,就把对应的右括号入栈,因为这样匹配的时候直接弹出来就直接比较就可以了,方便代码实现
  3. 遇到右括号时,就判断这个右括号是否就是栈顶的右括号,是则弹出,不是则为false;此时如果右括号多了的情况,比如“[{}]())))”,当遍历到倒数第3个右括号时,此时栈里为空,说明右括号多了,则为false
  4. 最后如果栈不为空,则说明左括号多了,则为false

1.2 代码

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack=new Stack<>();
        char ch;
        for(int i=0;i<s.length();i++){
            ch=s.charAt(i);
            if(ch=='('){
                stack.push(')');
            }else if(ch=='{'){
                stack.push('}');
            }else if(ch=='['){
                stack.push(']');
            }else if(stack.empty()||stack.peek()!=ch){
                return false;
            }else{
                stack.pop();
            }
        }
        return stack.empty();
    }
}

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

2.1 思路

  1. 这题类似上述的删除括号的方式,同样是使用栈来删除的
  2. 先创建栈,然后遍历字符串,栈是用来存遍历过的元素,每遍历一个都要在栈里判断是否遍历过当前的元素/前一个元素是否就是当前的元素,如果是,当前元素就不入栈并且把栈顶元素弹出,这个操作用栈就很方便。只要栈不为空或者栈顶元素与当前元素不相同就可以直接入栈
  3. 遍历完以后栈里剩下的就是要的字符串的反向,我们可以通过一个新的空的字符串str,然后让str=stack.pop()+str; 就是把栈顶元素放到字符串的后面,这样就可以实现把栈里的元素翻转了,得到的就是我们想要的字符串

2.2 代码

class Solution {
    public String removeDuplicates(String s) {
        Stack<Character> stack=new Stack<>();
        char ch;
        for(int i=0;i<s.length();i++){
            ch=s.charAt(i);
            if(stack.empty()||stack.peek()!=ch){
                stack.push(ch);
            }else {
                stack.pop();
            }
        }
        String str="";
        while(!stack.empty()){
            str=stack.pop()+str;
        }
        return str;
    }
}

3. LeetCode 150. 逆波兰表达式求值

3.1 思路

  1. 逆波兰表达式是什么?=> 逆波兰表达式也称后缀表达式,这是方便计算机运算的 =>(1+2)*(3+4)这种就是正常习惯看的中缀表达式 =>而后缀表达式就是类似二叉树的后序遍历,在这里式子就变成了 1 2 + 3 4 + *。这样的题目就比较适合用栈来做
  2. 如何做题?遍历字符串数组,题目里是每个字符作为一个字符串,当遇到数字就入栈;当遇到运算符就出栈两个元素,第一个出栈的数字放在运算符的右边,第二个出栈的数字放在运算符的左边。注意这里顺序不能乱
  3. 将运算结果再次入栈,不断这样运行遍历,最后栈里唯一的元素则是最终运算结果
  4. 其实这题和20. 有效的括号类似,只是这里是需要三个元素,两个数字遇到一个运算符,做一个消除的操作,合成了一个数字

3.2 代码

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack=new Stack<>();
        int temp1;
        int temp2;
        for(String s:tokens){
            if("+".equals(s)){
                temp1=stack.pop();
                temp2=stack.pop();
                stack.push(temp2+temp1);
            }else if("-".equals(s)){
                temp1=stack.pop();
                temp2=stack.pop();
                stack.push(temp2-temp1);
            }else if("*".equals(s)){
                temp1=stack.pop();
                temp2=stack.pop();
                stack.push(temp2*temp1);
            }else if("/".equals(s)){
                temp1=stack.pop();
                temp2=stack.pop();
                stack.push(temp2/temp1);
            }else{
                stack.push(Integer.valueOf(s));
            }
        }
        return stack.pop();
    }
}
相关文章
|
5天前
|
机器学习/深度学习 算法 API
【Paddle】PCA线性代数基础 + 领域应用:人脸识别算法(1.1w字超详细:附公式、代码)
【Paddle】PCA线性代数基础 + 领域应用:人脸识别算法(1.1w字超详细:附公式、代码)
9 0
|
5天前
|
算法 关系型数据库 C语言
卡尔曼滤波简介+ 算法实现代码(转)
卡尔曼滤波简介+ 算法实现代码(转)
20 4
|
5天前
|
机器学习/深度学习
leetcode代码记录(旋转图像
leetcode代码记录(旋转图像
9 0
|
5天前
|
算法
leetcode代码记录(全排列 II
leetcode代码记录(全排列 II
13 4
|
5天前
|
算法
leetcode代码记录(全排列
leetcode代码记录(全排列
12 1
|
5天前
|
索引
leetcode代码记录(Z 字形变换
leetcode代码记录(Z 字形变换
11 1
|
5天前
leetcode代码记录(最长回文子串
leetcode代码记录(最长回文子串
10 2
|
5天前
leetcode代码记录(回文数
leetcode代码记录(回文数
13 1
|
5天前
|
算法 数据安全/隐私保护 计算机视觉
基于二维CS-SCHT变换和LABS方法的水印嵌入和提取算法matlab仿真
该内容包括一个算法的运行展示和详细步骤,使用了MATLAB2022a。算法涉及水印嵌入和提取,利用LAB色彩空间可能用于隐藏水印。水印通过二维CS-SCHT变换、低频系数处理和特定解码策略来提取。代码段展示了水印置乱、图像处理(如噪声、旋转、剪切等攻击)以及水印的逆置乱和提取过程。最后,计算并保存了比特率,用于评估水印的稳健性。
|
1天前
|
算法
m基于BP译码算法的LDPC编译码matlab误码率仿真,对比不同的码长
MATLAB 2022a仿真实现了LDPC码的性能分析,展示了不同码长对纠错能力的影响。短码长LDPC码收敛快但纠错能力有限,长码长则提供更强纠错能力但易陷入局部最优。核心代码通过循环进行误码率仿真,根据EsN0计算误比特率,并保存不同码长(12-768)的结果数据。
19 9
m基于BP译码算法的LDPC编译码matlab误码率仿真,对比不同的码长