首页 > 编程语言 >算法学习day11栈与队列part02-20、1047、150

算法学习day11栈与队列part02-20、1047、150

时间:2023-05-10 22:48:11浏览次数:54  
标签:150 ch 20 String part02 pop public slow stack

package LeetCode.StackAndQueuepart02;

/**
 * 20. 有效的括号
 * 给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。
 * 有效字符串需满足:
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 * 每个右括号都有一个对应的相同类型的左括号。
 * 示例:
 * 输入:s = "()"
 * 输出:true
 * */

import java.util.Deque;
import java.util.LinkedList;

/**
 * 括号匹配是使用栈解决的经典问题。
 * 由于栈结构的特殊性,非常适合做对称匹配类的题目。
 * */
public class ValidParentheses_20 {
    public static void main(String[] args) {
        String str = "()[]{}";
        boolean result = isValid(str);
        System.out.println(result);
    }
    public static 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();
    }
}
package LeetCode.StackAndQueuepart02;
/**
* 1047. 删除字符串中的所有相邻重复项
* 给出由小写字母组成的字符串 S,重复项删除操作会选择两个相邻且相同的字母,并删除它们。
* 在 S 上反复执行重复项删除操作,直到无法继续删除。
* 在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
* 示例:
* 输入:"abbaca"
* 输出:"ca"
* 解释:
* 例如,在 "abbaca" 中,我们可以删除 "bb" 由于两字母相邻且相同,这是此时唯一可以执行删除操作的重复项。
* 之后我们得到字符串 "aaca",其中又只有 "aa" 可以执行重复项删除操作,所以最后的字符串为 "ca"。
* */
/**
 * 思路:
 * 我们在删除相邻重复项的时候,其实就是要知道当前遍历的这个元素,
 * 我们在前一位是不是遍历过一样数值的元素,那么如何记录前面遍历过的元素呢?
 *
 * 所以就是用栈来存放,那么栈的目的,就是存放遍历过的元素,
 * 当遍历当前的这个元素的时候,去栈里看一下我们是不是遍历过相同数值的相邻元素。
 * */
public class RemoveAllAdjacentDuplicatesInString_1047 {
    public static void main(String[] args) {
        String str = "abbaca";
        String result = removeDuplicates(str);
        System.out.println(result);
    }
    // 栈相关知识
    public static 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();
    }
    // 双指针
    public static String removeDuplicates2(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);
    }

}
package LeetCode.StackAndQueuepart02;
import java.util.Deque;
import java.util.LinkedList;

/**
 * 150. 逆波兰表达式求值
 * 给你一个字符串数组 tokens ,表示一个根据 逆波兰表示法 表示的算术表达式。
 * 请你计算该表达式。返回一个表示表达式值的整数。
 * 有效的算符为 '+'、'-'、'*' 和 '/' 。
 * 每个操作数(运算对象)都可以是一个整数或者另一个表达式。
 * 两个整数之间的除法总是 向零截断 。
 * 表达式中不含除零运算。
 * 输入是一个根据逆波兰表示法表示的算术表达式。
 * 答案及所有中间计算结果可以用 32 位 整数表示。
 * 示例:
 * 输入:tokens = ["2","1","+","3","*"]
 * 输出:9
 * 解释:该算式转化为常见的中缀算术表达式为:((2 + 1) * 3) = 9
 * */
public class EvaluateReversePolishNotation_150 {
    public static void main(String[] args) {
        String [] tokens = {"2","1","+","3","*"};
        int result = evalRPN(tokens);
        System.out.println(result);
    }
    public static 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();
    }
}

 

标签:150,ch,20,String,part02,pop,public,slow,stack
From: https://www.cnblogs.com/lipinbigdata/p/17389558.html

相关文章

  • 2023.5.10三天学习总结
    一.三天学习情况1.vp了一场河南省赛2.补完了一下上把cf的E以及校赛的题3.学习了一下启发式合并二.学习情况截图 三.题解(158条消息)2023河南省赛vp题解_scanner___yw的博客-CSDN博客四.总结1.这两天刷了两个模拟题,发现代码能力确实得到了......
  • ubuntu apt 安装报错:Media change: please insert the disc labeled 'Ubuntu 20.04.5
    前言如果你在Ubuntu上使用apt安装软件包时遇到"Mediachange:pleaseinsertthedisclabeled..."的错误消息,这通常是因为apt源列表中包含CD/DVD源,但你的系统中没有插入相应的安装介质(CD或DVD)。解决检查/etc/apt/sources.list文件中,是否出现CD/DVD源。类似d......
  • 2023-05-10:给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表 如果在二叉
    2023-05-10:给你一棵以root为根的二叉树和一个head为第一个节点的链表如果在二叉树中,存在一条一直向下的路径且每个点的数值恰好一一对应以head为首的链表中每个节点的值,那么请你返回True否则返回False。一直向下的路径的意思是:从树中某个节点开始,一直连续向下的路径......
  • 2023.5.10编程一小时打卡
    一、问题描述:给出下面的人员基类框架:classPerson{protected:stringname;intage;public:Person();Person(stringp_name,intp_age);voiddisplay(){cout<<name<<“:”<<age<<endl;}};建立一个派生类student,增加以下成员数据:in......
  • 每日总结2023-05-10
    今天完成了对于Android中Fragment的了解:Fragment有自己的生命周期Fragment依赖于ActivityFragment通过getActivity()可以获取所在的Activity;Activity通过FragmentManager的findFragmentById()或findFragmentByTag()获取FragmentFragment和Activity是多对多......
  • 20230510
    今天学习ajax相关知识,明天准备复习连接池以及DButils。<%--CreatedbyIntelliJIDEA.User:双休日Date:2023/5/9Time:19:58TochangethistemplateuseFile|Settings|FileTemplates.--%><%@pagecontentType="text/html;charset=UTF-8"language="java&q......
  • [SWPUCTF 2021 新生赛]老鼠走迷宫
    查壳:熟悉的配方,解包,反编译吧:进入.py文件:题目是走迷宫,进去后也发现了地图,那么我们将它打印出来:得到这么一张地图,那么看看起点和终点,起点:第一行第二个,终点:最后一行倒数第二个。画地图咯:得到Des='sssssddssddssaaaassssddwwddddssssssaawwaassssddssaassddddwwddssddwwwwwww......
  • NOIP 2022 游记 / 联赛充满了失望
    Day18:30左右发密码,密码给错了一次,但是延时,biu#2019miss和solo@2022。8:36开考看到第一题,一眼前缀和题,但是这个需要枚举一堆东西,心里就咯噔一下,我乱写一通然后就过了第一个样例,随之发现第二个大样例WA了,调了一阵又过了所有样例,艹已经过了2h,预估\(76\)分,但是非常怕挂分......
  • 适合数据库管理者的七个空间数据库(在2021版本中)
    适合数据库管理者的七个空间数据库(在2021版本中)   华为云开发者联盟该内容已被华为云开发者联盟社区收录加入社区默认分类专栏收录该内容153篇文章18订阅订阅专栏空间数据和空间数据库的价值超越了地图和可视化。空间数据是可推动数据库管理......
  • [NISACTF 2022]ezpython
    查壳:(后来发现:但凡有这玩意的都和解包有关)32位,运行,发现让我们输入一个key,进IDA:把能找的都找了,愣是没发现什么,除了一个类似base64的编码,实在没办法,去看了大佬的文章,说是py下的exe的解包,跟据大佬们的思路来了一波,果然出来了。开始吧,首先是将该运行文件与pyinstxtractor放一起(这......