美文网首页
3.栈(三)

3.栈(三)

作者: 今天柚稚了么 | 来源:发表于2020-07-09 15:56 被阅读0次

    题目汇总:https://leetcode-cn.com/tag/stack/

    385. 迷你语法分析器中等(不做)

    394. 字符串解码(不会做)

    402. 移掉K位数字中等(看题解可理解)

    456. 132模式中等(不做)

    496. 下一个更大元素 I简单[✔]

    503. 下一个更大元素 II中等[✔]

    591. 标签验证器困难(不做)

    636. 函数的独占时间中等(不做)

    682. 棒球比赛简单[✔]

    394. 字符串解码中等

    给定一个经过编码的字符串,返回它解码后的字符串。
    编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
    你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。
    此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a2[4] 的输入。
    示例 1:
    输入:s = "3[a]2[bc]"
    输出:"aaabcbc"
    示例 2:
    输入:s = "3[a2[c]]"
    输出:"accaccacc"
    示例 3:
    输入:s = "2[abc]3[cd]ef"
    输出:"abcabccdcdcdef"
    示例 4:
    输入:s = "abc3[cd]xyz"
    输出:"abccdcdcdxyz"

    思路:

    题解https://leetcode-cn.com/problems/decode-string/solution/decode-string-fu-zhu-zhan-fa-di-gui-fa-by-jyd/

    class Solution {//执行用时:2 ms, 在所有 Java 提交中击败了55.19%的用户
        public String decodeString(String s) {
            StringBuilder res = new StringBuilder();
            int multi = 0;
            LinkedList<Integer> stack_multi = new LinkedList<>();
            LinkedList<String> stack_res = new LinkedList<>();
            for(Character c : s.toCharArray()) {
                if(c == '[') {
                    stack_multi.addLast(multi);
                    stack_res.addLast(res.toString());
                    multi = 0;
                    res = new StringBuilder();
                }
                else if(c == ']') {
                    StringBuilder tmp = new StringBuilder();
                    int cur_multi = stack_multi.removeLast();
                    for(int i = 0; i < cur_multi; i++) tmp.append(res);
                    res = new StringBuilder(stack_res.removeLast() + tmp);
                }
                else if(c >= '0' && c <= '9') multi = multi * 10 + Integer.parseInt(c + "");
                else res.append(c);
            }
            return res.toString();
    
        }
    }
    

    402. 移掉K位数字中等

    给定一个以字符串表示的非负整数 num,移除这个数中的 k位数字,使得剩下的数字最小。
    注意:
    num 的长度小于 10002 且 ≥ k。
    num 不会包含任何前导零。
    示例 1 :
    输入: num = "1432219", k = 3
    输出: "1219"
    解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。
    示例 2 :
    输入: num = "10200", k = 1
    输出: "200"
    解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
    示例** 3 :**
    输入: num = "10", k = 2
    输出: "0"
    解释: 从原数字移除所有的数字,剩余为空就是0。

    思路:辅助栈
    class Solution {
        public String removeKdigits(String num, int k) {
            if(k>=num.length()||num.length()==0)
                return "0";
            Stack<Integer> stack = new Stack<>();
            stack.push(num.charAt(0)-'0');
            for(int i=1;i<num.length();i++){
                while(!stack.isEmpty() && k>0 && stack.peek()>num.charAt(i)-'0'){
                    stack.pop();
                    k--;
                }
                // 如果n!=0,入栈;如果n==0,但是栈不空,入栈
                if(num.charAt(i)-'0'!=0 || !stack.isEmpty()){
                    stack.push(num.charAt(i)-'0');
                }
            }
            //遍历完,但是还没去掉k个数字
            while(k>0){
                k--;
                stack.pop();
    
            }
            if(stack.isEmpty())
                return "0";
            StringBuilder s = new StringBuilder();
            while(!stack.isEmpty()){
                s.append(stack.pop());
            }
            return s.reverse().toString();//从后往前添加所以我们要逆序
        }
    }
    

    496. 下一个更大元素 I简单

    给定两个** 没有重复元素** 的数组 nums1nums2 ,其中nums1nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。
    nums1 中数字 x 的下一个更大元素是指 xnums2 中对应位置的右边的第一个比 **x **大的元素。如果不存在,对应位置输出 -1 。
    示例 1:
    输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
    输出: [-1,3,-1]
    解释:
    对于num1中的数字4,你无法在第二个数组中找到下一个更大的数字,因此输出 -1。
    对于num1中的数字1,第二个数组中数字1右边的下一个较大数字是 3。
    对于num1中的数字2,第二个数组中没有下一个更大的数字,因此输出 -1。
    示例 2:
    输入: nums1 = [2,4], nums2 = [1,2,3,4].
    输出: [3,-1]
    解释:
    对于 num1 中的数字 2 ,第二个数组中的下一个较大数字是 3 。
    对于 num1 中的数字 4 ,第二个数组中没有下一个更大的数字,因此输出 -1 。

    思路:单调栈+哈希表

    先对 nums2 中的每一个元素,求出其下一个更大的元素。随后对于将这些答案放入哈希映射(HashMap)中,再遍历数组 nums1,并直接找出答案。维护一个单调栈,栈中的元素从栈顶到栈底是单调不降的。

    class Solution {//执行用时:4 ms, 在所有 Java 提交中击败了90.74%的用户
        public int[] nextGreaterElement(int[] nums1, int[] nums2) {
            Stack<Integer> stack = new Stack<>();
            HashMap<Integer,Integer> map = new HashMap<>();
            int[] res = new int[nums1.length];
            for(int num : nums2){
                while(!stack.isEmpty() && stack.peek() < num){
                    map.put(stack.pop(), num);
                }
                stack.push(num);
            }
            for(int i=0;i<nums1.length;i++){
                res[i] = map.getOrDefault(nums1[i],-1);
            }
        return res;
        }
    }
    

    503. 下一个更大元素 II中等

    给定一个循环数组(最后一个元素的下一个元素是数组的第一个元素),输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序,这个数字之后的第一个比它更大的数,这意味着你应该循环地搜索它的下一个更大的数。如果不存在,则输出 -1。
    示例 1:
    输入: [1,2,1]
    输出: [2,-1,2]
    解释: 第一个 1 的下一个更大的数是 2;
    数字 2 找不到下一个更大的数;
    第二个 1 的下一个最大的数需要循环搜索,结果也是 2。
    注意: 输入数组的长度不会超过 10000。

    思路:单调栈+HashMap

    496. 下一个更大元素 I区别在于数组是循环数组,因此复制两倍数组,另外单调栈中存的是数组下标。

    class Solution {//执行用时:18 ms, 在所有 Java 提交中击败了36.06%的用户
        public int[] nextGreaterElements(int[] nums) {
            Stack<Integer> stack = new Stack<>();
            HashMap<Integer,Integer> map = new HashMap<>();
            int len = nums.length;
            int[] res = new int[len];
    
            int[] doubleNums = new int[len * 2];
            //复制一份新的数组
            for (int i = 0; i < 2; i++) {
                for (int j = 0; j < len; j++) {
                    doubleNums[len * i + j] = nums[j];
                }
            }
    
            for(int i=0; i < len * 2; i++){
                while(!stack.isEmpty() && doubleNums[stack.peek()] < doubleNums[i]){
                     map.put(stack.pop(), doubleNums[i]);
                }
                stack.push(i);
            }
            for(int i=0;i<len;i++){
                res[i] = map.getOrDefault(i,-1);
            }
        return res;
    
        }
    }
    

    682. 棒球比赛简单

    你现在是棒球比赛记录员。
    给定一个字符串列表,每个字符串可以是以下四种类型之一:
    整数(一轮的得分):直接表示您在本轮中获得的积分数。
    "+"(一轮的得分):表示本轮获得的得分是前两轮有效 回合得分的总和。
    "D"(一轮的得分):表示本轮获得的得分是前一轮有效 回合得分的两倍。
    "C"(一个操作,这不是一个回合的分数):表示您获得的最后一个有效 回合的分数是无效的,应该被移除。
    每一轮的操作都是永久性的,可能会对前一轮和后一轮产生影响。
    你需要返回你在所有回合中得分的总和。
    示例 1:
    输入: ["5","2","C","D","+"],输出: 30
    解释:
    第1轮:你可以得到5分。总和是:5。
    第2轮:你可以得到2分。总和是:7。
    操作1:第2轮的数据无效。总和是:5。
    第3轮:你可以得到10分(第2轮的数据已被删除)。总数是:15。
    第4轮:你可以得到5 + 10 = 15分。总数是:30。

    思路:辅助栈

    保持栈上每个有效回合的值。

    class Solution {
        public int calPoints(String[] ops) {
            Stack<Integer> stack = new Stack<>();
            int sum = 0;
            for(String s:ops){
                //表示您获得的最后一个有效 回合的分数是无效的,应该被移除
                if(s.equals("C")){
                    sum -= stack.peek();
                    stack.pop();
                //表示本轮获得的得分是前一轮有效 回合得分的两倍
                }else if(s.equals("D")){
                    sum += 2 * stack.peek();
                    stack.push(2*stack.peek());
                //表示本轮获得的得分是前两轮有效回合得分的总和
                }else if(s.equals("+")){
                    int top1 = stack.peek() ;
                    stack.pop() ;
                    int top2 = stack.peek() ;
                    sum += top1 + top2 ;
                    stack.push(top1) ;
                    stack.push(top1 + top2) ;
                }else{//直接表示您在本轮中获得的积分数
                    sum += Integer.valueOf(s);
                    stack.push(Integer.valueOf(s));
                }
            }
        return sum;
        }
    }
    

    相关文章

      网友评论

          本文标题:3.栈(三)

          本文链接:https://www.haomeiwen.com/subject/ybpmfktx.html