当前位置:首页 » 《资源分享》 » 正文

【Code皮皮虾】双栈 + 贪心 思路讲解、代码实现——>【有效的括号字符串】_Code皮皮虾的博客

23 人参与  2021年10月27日 14:03  分类 : 《资源分享》  评论

点击全文阅读


文章目录

    • 😉毛遂自荐
    • ✨题目
    • 🌝解题
      • 双栈
        • 思路
        • 代码实现
      • 贪心
        • 思路
        • 代码实现
    • 💖最后

Code皮皮虾 一个沙雕而又有趣的憨憨少年,和大多数小伙伴们一样喜欢听歌、游戏,当然除此之外还有写作的兴趣,emm…,日子还很长,让我们一起加油努力叭🌈

🚀🚀🚀话不多说,直达底部有粉丝专享福利!!!


😉毛遂自荐

毛遂自荐一下,给大家推荐一下自己的专栏😁,欢迎小伙伴们收藏关注😊

大厂面试题专栏

Java专栏

爬虫专栏

更多专栏尽在主页,点我😁!!!

在这里插入图片描述


✨题目

image.png



🌝解题


双栈


思路

因为题目有*的存在,而且*既可以为左括号,也可以为右括号或者空字符串,所以需要使用两个栈来实现

leftStack栈存储左括号的索引,starStack栈存储星号的索引

在遍历过程中,如果遇到右括号

  1. 优先匹配左括号,即对leftStack进行pop
  2. 如果leftStack为空,则对starStack进行pop
  3. 如果starStack为空,说明匹配不了了,直接return false

在遍历完成之后,可能存在leftStack 和 starStack不为空的情况,那么此时,就需要将*当作右括号,从而对括号进行匹配。

最后,如果leftStack为空,说明匹配完成,return true,否则,return false


代码实现

class Solution {
    public boolean checkValidString(String s) {
        
        //存储左括号索引
        Deque<Integer> leftStack = new LinkedList<>();
        //存储*索引
        Deque<Integer> starStack = new LinkedList<>();
        
        int n = s.length();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (c == '(') {
                leftStack.push(i);
            } else if (c == '*') {
                starStack.push(i);
            } else {
                if (!leftStack.isEmpty()) {
                    leftStack.pop();
                } else if (!starStack.isEmpty()) {
                    starStack.pop();
                } else return false;
            }
        }


        while (!leftStack.isEmpty() && !starStack.isEmpty()) {
            
            //把*当成右括号,但是必须右括号的索引 > 左括号才能匹配
            //因为是栈结构,所以根据遍历,栈顶元素的索引是最大的索引,如果不满足就return false
            if (leftStack.pop() > starStack.pop()) {
                return false;
            }
        }
        return leftStack.isEmpty();
    }
}

贪心


思路

因为题目有*的存在,而*既可以为左括号,也可以为右括号或者空字符串

所以我们可以维护一个未匹配左括号的范围,即[min,max],遍历完成后,直接return min == 0

🔥怎么维护???

  1. 遇到左括号,则min++ , max++
  2. 遇到右括号,则min-- , max--,如果max == 0了,说了没有可以匹配的了,那么直接return false
  3. 遇到*号,则min-- , max++,因为*既可以为左括号,也可以为右括号

代码实现

class Solution {

    public boolean checkValidString(String s) {
        
        int min = 0, max = 0; // 维护当前左括号的数量范围:[min, max]
        char[] chars = s.toCharArray();
        for(char i : chars) {
            if(i == '(') {
                min++;
                max++;
            }else if(i == ')') {
                //min > 0才--
                if(min > 0) min--;
                if(max-- == 0) return false;
            }else {
                //min > 0才--
                if(min > 0) min--;
                max++;
            }
        }
        return min == 0;
    }

}



💖最后

我是 Code皮皮虾,一个热爱分享知识的 皮皮虾爱好者,未来的日子里会不断更新出对大家有益的博文,期待大家的关注!!!

创作不易,如果这篇博文对各位有帮助,希望各位小伙伴可以一键三连哦!,感谢支持,我们下次再见~~~

公众号干货内容输出,囊括Java、Python爬虫、力扣题解、大厂面试题 四大系列,更有长时间总结的干货资源分享,后台回复:面试资料即可领取


最后,祝各位步步高升🚀🚀🚀

                                                   粉丝福利👇🏻👇🏻👇🏻


点击全文阅读


本文链接:http://m.zhangshiyu.com/post/30181.html

括号  匹配  索引  
<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • 完结文毁容的姐姐和瞎眼的我离开后,姜家两兄弟悔哭了+后续列表_完结文毁容的姐姐和瞎眼的我离开后,姜家两兄弟悔哭了+后续(林梦婉)
  • 妻子辱我爸受贿自杀,我掏出一等军功章节选推荐_[陈素云辰朋友]小说精彩章节分享
  • 全书浏览苔藓爬满旧日诺言新上(顾砚廷慕晚夏)_苔藓爬满旧日诺言新上(顾砚廷慕晚夏)全书结局
  • 顾尘傅雅宁(神女老婆,却在背地承欢作乐+后续+结局)结局_(顾尘傅雅宁神女老婆,却在背地承欢作乐+后续+结局全书结局)结局列表_笔趣阁(顾尘傅雅宁)
  • 「老婆怀上助理的孩子后,助理要求我净身出户」章节限时抢先看‌_「黄秋雅秋雅姐刘嘉铭」后续完结版
  • 此去经年人未还,沈青禾霍沉洲_此去经年人未还,沈青禾霍沉洲
  • 我爸娶了九十九个媳妇都死了,这次准备娶我的女同学小说精彩章节免费试读_[小梅娶媳妇孤儿]全文免费在线阅读
  • 此去经年人未还结局+番外文章简述(沈青禾霍沉洲)列表_此去经年人未还结局+番外文章简述
  • 完结文寻你寻不到归期结局+完结列表_完结文寻你寻不到归期结局+完结(姜昭意盛西)
  • 江以蓁的潮起时问归期高分佳作江以蓁秦司礼全书在线
  • 「亲手逼死儿子后,男人悔不当初」后续全文免费阅读_[傅司衍轩轩佳佳]最新章节免费阅读
  • (番外)+(全书)寻你寻不到归期+后续+结局(姜昭意盛西辞)全书在线_寻你寻不到归期+后续+结局免费列表_笔趣阁(姜昭意盛西辞)

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1