首页 > 其他分享 >LeetCodeHot100 栈 155. 最小栈 394. 字符串解码

LeetCodeHot100 栈 155. 最小栈 394. 字符串解码

时间:2024-03-24 14:57:44浏览次数:26  
标签:155 int LeetCodeHot100 public curString 394 字符串 new stack

155. 最小栈
https://leetcode.cn/problems/min-stack/description/?envType=study-plan-v2&envId=top-100-liked

class MinStack {
        Deque<Integer> deque;
        PriorityQueue<Integer> priorityQueue;
        public MinStack() {
            deque = new LinkedList<>();
            priorityQueue = new PriorityQueue<>();
        }

        public void push(int val) {
            deque.addLast(val);
            priorityQueue.add(val);
        }

        public void pop() {
            Integer i = deque.pollLast();
            priorityQueue.remove(i);
        }

        public int top() {
            return deque.peekLast();
        }

        public int getMin() {
            return priorityQueue.peek();
        }
    }

总结:用优先级队列查min
394. 字符串解码
https://leetcode.cn/problems/decode-string/description/?envType=study-plan-v2&envId=top-100-liked

public String decodeString(String s) {
        // 准备两个栈,一个存放数字,一个存放字符串
        // 遍历有四种情况
        // 1. 如果是数字,将数字转换成整型数字待处理
        // 2. 如果是字符,将字符添加到临时字符串待处理
        // 3. 如果是'[',将当前数字和临时字符串添加到各自的栈中
        // 4. 如果是']',将数字和字符从各自的栈中取出,然后拼接成新的临时字符串
        // 创建数字栈、字符串栈、临时数字和临时字符串
        Deque<Integer> stack_nums = new ArrayDeque<>();
        Deque<StringBuilder> stack_words = new ArrayDeque<>();
        StringBuilder curString = new StringBuilder();
        int curNum = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)){
                curNum = curNum * 10 + c - '0';
            }else if (Character.isLetter(c)){
                curString.append(c);
            }else if (c == '['){
                stack_nums.push(curNum);
                curNum = 0;
                stack_words.push(curString);
                curString = new StringBuilder();
            }else {
                StringBuilder temStr = stack_words.pop();
                int cnt = stack_nums.pop();
                for (int j = 0; j < cnt; j++) {
                    temStr.append(curString);
                }
                curString = temStr;
            }
        }
        return curString.toString();
    }

总结:思路就是维护两个栈,用来存数字和字符串,字符串栈里是StringBuilder,维护两个变量,一个去计算。 数字栈存的是算好的数字,字符串栈存的是之前的字符串,需要拿出来跟当前的字符串拼接(拼接n次)

标签:155,int,LeetCodeHot100,public,curString,394,字符串,new,stack
From: https://www.cnblogs.com/jeasonGo/p/18092418

相关文章

  • LeetCodeHot100 二分查找 35. 搜索插入位置 74. 搜索二维矩阵 34. 在排序数组中查
    35.搜索插入位置https://leetcode.cn/problems/search-insert-position/description/?envType=study-plan-v2&envId=top-100-likedpublicintsearchInsert(int[]nums,inttarget){intleft=0;intright=nums.length-1;while(left<......
  • 洛谷题单指南-集合-P1551 亲戚
    原题链接:https://www.luogu.com.cn/problem/P1551题意解读:要判断两人是否是亲戚,只需要看两人是否属于一个集合,基于所有已知的亲戚关系,可以建立多个有亲戚关系的集合,这个过程可以借助并查集。解题思路:并查集:1、定义并查集是一种树形数据结构,本质上是多棵树,每棵树表示一个集合,......
  • abc155F题解
    abc155F题意:给定\(n\)个灯泡的位置\(a_i\)和状态\(b_i(0/1)\)。给定\(m\)个开关控制区间\([l_i,r_i]\)中所有的灯泡,即使用这个开关会使\([l_i,r_i]\)中所有的灯泡的状态都取反。问能否使这\(n\)个灯泡的状态都变成\(0\),如果可以,输出一种方案,否则,输出\(-1\)。思路:神仙转化题。......
  • LeetCodeHot100 73. 矩阵置零 54. 螺旋矩阵 48. 旋转图像 240. 搜索二维矩阵 II
    73.矩阵置零https://leetcode.cn/problems/set-matrix-zeroes/description/?envType=study-plan-v2&envId=top-100-likedpublicvoidsetZeroes(int[][]matrix){inttop=0,bottom=matrix.length,left=0,right=matrix[0].length;int[][]flag......
  • LeetCodeHot100 283. 移动零 11. 盛最多水的容器 15. 三数之和 42. 接雨水
    283.移动零https://leetcode.cn/problems/move-zeroes/description/?envType=study-plan-v2&envId=top-100-likedpublicvoidmoveZeroes(int[]nums){intr=0;for(inti=0;i<nums.length;i++){if(nums[i]!=0){......
  • LeetCodeHot100 283. 移动零 11. 盛最多水的容器 42. 接雨水 15. 三数之和
    283.移动零https://leetcode.cn/problems/move-zeroes/description/?envType=study-plan-v2&envId=top-100-likedpublicvoidmoveZeroes(int[]nums){intr=0;for(inti=0;i<nums.length;i++){if(nums[i]!=0){......
  • LeetCodeHot100 1.两数之和 46.字母异位词分组 128.最长连续序列
    1.两数之和https://leetcode.cn/problems/two-sum/description/?envType=study-plan-v2&envId=top-100-likedpublicint[]twoSum(int[]nums,inttarget){HashMap<Integer,Integer>map=newHashMap<>();for(inti=0;i<nums.l......
  • P1550 [USACO08OCT] Watering Hole G
    原题链接题解最小生成树的应用。这道题多转了一个弯,这道题其实多了一个结点(代表一个虚拟水井),每块田打井的费用可以过渡到从虚拟水井运水的费用,然后再套用最小生成树的模板即可。code #include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;structNode{......
  • 耳分解、双极定向和 P9394 Solution
    耳分解设无向图\(G'(V',E')\subsetG(V,E)\),简单路径或简单环\(P:x_1\to\dots\tox_k\)被称为\(G\)关于\(G'\)的耳,当且仅当其满足\(x_1,x_k\inV',x_2,x_3\dotsx_{k-1}\not\inV'\)。如果\(P\)是简单路径,那么\(P\)称为开耳。下面记树上\(x,y\)之间的路......
  • P1550 [USACO08OCT] Watering Hole G
    原题链接题解思维转换,想象井里的水都来自山上,并把山看成一个点,那么这道题就变成了最小生成树简证最小生成树原理:按边权排序,然后遍历,如果这条边的两个点之前每连过,那么就连上,因为这就是这两个点所在集合之间的最短路径了,不然这条边没必要加,因为已经联通了算是一种贪心?code#i......