精华内容
下载资源
问答
  • 题目给定一个只包括 '(', ')', '{', '}', '[', ']'的字符串,判断字符串是否有效。有效字符串需满足:左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。示例...

    前言

    今天给大家分享一道 bilibili 今年的笔试真题,也是一道关于栈的经典面试题。上题目!!!

    题目

    给定一个只包括 '('')''{''}''['']' 的字符串,判断字符串是否有效。

    有效字符串需满足:

    • 左括号必须用相同类型的右括号闭合。
    • 左括号必须以正确的顺序闭合。
    • 注意空字符串可被认为是有效字符串。

    示例 1:

    输入: "()"

    输出: true

    示例 2:

    输入: "()[]{}"

    输出: true

    示例 3:

    输入: "(]"

    输出: false

    示例 4:

    输入: "([)]" 输出: false

    示例 5:

    输入: "{[]}"

    输出: true

    LeetCode 地址:https://leetcode-cn.com/problems/valid-parentheses

    解题思路

    这道题考察的是就是验证括号的对称性,比如“([{}])”这种字符串就是正确的,应该返回 true,而“([{})]”这种字符串就是错误的,应该返回 false。

    从上面的题目可以看出,括号总共分为三类:小括号、中括号和大括号,那么我们可以利用栈先进后出的特性,将所有左边的括号(“(”、“[”、“{”)先入栈,然后再碰到右括号时,让它与栈顶的元素进行匹配,比如当遇到“)”时,如果栈顶是“(”,则说明匹配成功,栈顶元素出栈再继续字符串循环的流程,如果匹配错误就直接返回 false。

    假设我们要匹配字符串“(([]))”是否合法?那么执行流程就是这样的。

    首先遇到左边括号,先入栈:

    cf07d2d7737580a913135f23ea367e9a.png

    接下来又是左边括号,继续入栈:

    dddd08069a9dc7a1cc295167223ccd47.png

    然后又是左边括号,继续入栈:

    3bf8f2b53ff5a9fcf3d92b56c5aa5511.png

    接下来是右边括号,与栈顶元素匹配,“[]”为一对合法的括号,匹配成功栈顶元素出栈:

    ce6ad550dc3c798338d0e6cb0d2e1533.png

    接下来又是右边括号,与栈顶元素匹配,“()”为一对合法的括号,匹配成功栈顶元素出栈:

    05da10b5476204c85508368f630a537e.png

    接下来又是右边括号,与栈顶元素匹配,“()”为一对合法的括号,匹配成功栈顶元素出栈:

    7353c217840ad51ca1b91bb807f04431.png

    当字符串循环结束并且栈为空栈时,则证明此字符串的括号匹配合法,最终的效果如下图所示:

    84ec087fc1e211838fbcd3984a1168ea.png

    那么接下来我们就用代码来实现一下整个过程...

    实现代码一

    public boolean isValid(String s) {
        int slen = s.length(); // 括号的长度
        if (slen % 2 == 1) { // 括号不是成对出现直接返回 false
            return false;
        }
        // 把所有对比的括号存入 map,对比时用
        Map map = new HashMap<>();
        map.put(')''(');
        map.put('}''{');
        map.put(']''[');// 定义栈,用于存取括号(辅助比较)
        Stack stack = new Stack<>();for (int i = 0; i // 循环所有字符char c = s.charAt(i);if (map.containsKey(c)) { // 为右边的括号,如 ')'、'}' 等if (stack.isEmpty() || stack.peek() != map.get(c)) { // 栈为空或括号不匹配return false;
                }
                stack.pop(); // 是一对括号,执行出栈(消除左右括号)
            } else { // 左边括号,直接入栈
                stack.push(c);
            }
        }return stack.isEmpty();
    }

    我们在 LeetCode 中提交一下代码,执行结果如下:

    9379cdf47f0b8341aa82e295c9dd2406.png

    代码解析

    以上代码的 map 集合是用于定义括号的匹配规则,比如“)”对应的匹配值是“(”,“]”的匹配值是“[”等,然后我们再去循环待验证的字符串,遇到左括号直接入栈,遇到右括号让它与栈顶元素匹配,等到整个字符串循环结束,如果栈为空则说明字符串的括号合法。

    复杂度分析

    时间复杂度:O(n),遍历了一遍整个字符串。空间复杂度:O(n)。

    实现代码二

    除了使用栈之外,我们还可以使用借助 Java 中的 replace 方法来实现,我们可以循环的消除字符串中的括号,比如将“()”或“[]”或“{}”循环得替换为空,最后在执行完成之后如果字符串为空,则说明字符串中的括号是合法的,具体实现代码如下:

    public boolean isValid(String s) {
            int len;
            do {
                len = s.length();
                // 消除成双成对的符号
                s = s.replace("()""").replace("[]""").
                        replace("{}""");
            } while (len != s.length()); // 不能再进行替换了,replace 方法没有替换任何字符
            return s.length() == 0;
        }

    我们在 LeetCode 中提交一下代码,执行结果如下:

    22e6fabdb991a580afa2baffb0b12a6c.png

    从运行结果来看,二者的执行效率相差还是很明显的:

    705f9856c62c5d5e164f1f8a754220a4.png

    最后

    本文我们讲了一道 bilibili 的笔试真题,同时它也是栈的经典面试题,我们可以借助栈的特性(先进后出)将所有的左括号入栈,当遇到右括号时让它与栈顶元素进行匹配,当字符串循环结束栈为空时,则说明此字符串的括号是合法的。当然我们在实际面试中,也可以使用 Java 的 replace 方法作为一个保底的实现方案,因为 replace 方法的实现相对更简单一些,只是性能不怎么好。

    分享技术,稳住,我们能赢?!

    展开全文
  • 6、vb6打开任意类型的文件.txt 7、vb6打开网页.txt 8、vb6单击按钮复制文本框内的内容.txt 9、vb6单击按钮最小化窗体.txt 10、vb6点击最大化最小化和关闭(有上角的)触发什么事件.txt 11、vb6调用API函数模拟按下...
  • 通过vb6将word文本(wordApp.ActiveDocument.Range().text,选择题答案,比如A)导入sql一表中,另一表手工录入学生答案(比如A),将两者字符进行比较判断答案正误并获得相应分值时,出现无法解决的问题:个别题目...
  • VB的程序代码是允许换行书写的,只要在每次换行的最后一个字符加上换行字符“_”就可以了。例如: 引用: Sub PicMove() Frm.Picture2.Left = Frm.Picture1.Left + _ ’加上换行符 Frm.Picture1.Width End ...
  • 7、在KeyPress事件中,如何取消用户刚键入的字符? 8、静态数组与动态数组的区别是什么?在声明静态数组、重定义动态数组时的下标都可以用变量来表示吗? 9、函数过程和子过程的区别是什么? 10、子过程调用有哪两种...
  • 实例129 判断字符串中某一字符是否大写 实例130 判断字符串是否为日期或时间 实例131 判断获得字符串中大写字符的个数 实例132 巧截字符串的数字 实例133 计算字符串中子字符串出现的次数 实例134 判断某一...
  • 实例129 判断字符串中某一字符是否大写 实例130 判断字符串是否为日期或时间 实例131 判断获得字符串中大写字符的个数 实例132 巧截字符串的数字 实例133 计算字符串中子字符串出现的次数 实例134 判断某一...
  • 类似于VB中的doevents功能 DELPHI下的多线程程序设计 用Delphi 3.0编制MP3音乐点歌台 用Delphi开发windows95屏幕保护预览程序 判断一个程序是否dos版本 Delphi自定义消息应用一例 显示密码编辑框中的密码 也...
  • DELPHI专题--程序应用

    2010-04-06 01:11:54
    类似于VB中的doevents功能 DELPHI下的多线程程序设计 用Delphi 3.0编制MP3音乐点歌台 用Delphi开发windows95屏幕保护预览程序 判断一个程序是否dos版本 Delphi自定义消息应用一例 显示密码编辑框中的密码 也...
  • Java-PHP-C#

    2012-11-27 15:13:36
    正如上面说的,正则表达式看起来非常复杂,让人害怕,大多数的PHP初学者都会跳过这里,继续下面的学习,但是PHP中的正则表达式有着可以利用模式匹配找到符合条件的字符串、判断字符串是否合乎条件或者用指定的字符...
  • 这里的长度以char作为一个长度,假如传入的类型是int类型,则长度为4,如果定义的是字符串,一个中文字符占用2个长度。最后一个参数,是网络发送或读取时的超时时间。 三、为Connect()接口添加源代码,看起来如下: ...
  • GetCharacterPlacement 该函数用于了解如何用一个给定的字符显示一个字串 GetCharWidth 调查字体中一个或多个字符的宽度 GetFontData 接收一种可缩放字体文件的数据 GetFontLanguageInfo 返回目前选入指定设备...
  • 实例150 解决查询过程中字段类型不同的问题 257 实例151 把查询结果生成表 258 实例152 追加查询结果到已存在的表中 259 实例153 用VB实现SQL Server 2000存储过程 调用 260 实例154 动态创建Access数据库及...
  • 实例150 解决查询过程中字段类型不同的问题 257 实例151 把查询结果生成表 258 实例152 追加查询结果到已存在的表中 259 实例153 用VB实现SQL Server 2000存储过程 调用 260 实例154 动态创建Access数据库及...
  • 5.1.2 如何攻击序列号保护 5.1.3 字符串比较形式 5.1.4 注册机制作 5.2 警告(NAG)窗口 5.3 时间限制 5.3.1 计时器 5.3.2 时间限制 5.3.3 拆解时间限制保护 5.4 菜单功能限制 5.4.1 相关函数 5.4.2 拆解菜单限制...
  • Excel_VBA程序设计.pdf

    热门讨论 2009-08-31 23:05:20
    第八节 判断语句 2 第九节 循环语句 3 第十节 其他类语句和错误语句处理 4 第十一节 过程和函数 5 一.Sub过程 5 二.Function函数 5 三.Property属性过程和Event事件过程 5 第十二节内部函数 6 一.测试函数 6 二...
  • Excel VBA程序设计.doc

    2009-07-06 22:16:12
    第八节 判断语句 2 第九节 循环语句 3 第十节 其他类语句和错误语句处理 4 第十一节 过程和函数 5 一.Sub过程 5 二.Function函数 5 三.Property属性过程和Event事件过程 5 第十二节内部函数 6 一.测试函数 6 二...
  • 第八节 判断语句 2 第九节 循环语句 3 第十节 其他类语句和错误语句处理 4 第十一节 过程和函数 4 一.Sub过程 4 二.Function函数 5 三.Property属性过程和Event事件过程 5 第十二节内部函数 5 一.测试函数 5 二...
  • 习题精选:章末均安排了大量的习题与编程实践题,方便检验学习效果,其中选择题、判断题、填空题、问答题答案附于书后,实践题的完整范例代码可从网站下载 书中所有165个完整范倒的源代码 书后所有实践题的源代码 ...
  • 习题精选:章末均安排了大量的习题与编程实践题,方便检验学习效果,其中选择题、判断题、填空题、问答题答案附于书后,实践题的完整范例代码可从网站下载 书中所有165个完整范倒的源代码 书后所有实践题的源代码 ...
  • 另外还提供了WinSock的详细开发步骤,以及如何响应网络超时,网络断开的事件方法以及在VC,VB调用该控件的方法。 一、MFC ActiveX控件开发步骤(VC 6.0): New->Projects->MFC ActiveX ControlWizard,然后输入...
  • asp.net知识库

    2015-06-18 08:45:45
    如何判断ArrayList,Hashtable,SortedList 这类对象是否相等 帮助解决网页和JS文件中的中文编码问题的小工具 慎用const关键字 装箱,拆箱以及反射 动态调用对象的属性和方法——性能和灵活性兼备的方法 消除由try/...
  • Excel_VBA教程

    2014-09-22 11:36:34
    第八节 判断语句 2 第九节 循环语句 3 第十节 其他类语句和错误语句处理 4 第十一节 过程和函数 4 一.Sub过程 4 二.Function函数 5 三.Property属性过程和Event事件过程 5 第十二节内部函数 5 一.测试函数 5 二...
  • ExcelVBA程序设计.doc

    2011-04-05 21:32:51
    第八节 判断语句 2 第九节 循环语句 3 第十节 其他类语句和错误语句处理 4 第十一节 过程和函数 4 一.Sub过程 4 二.Function函数 5 三.Property属性过程和Event事件过程 5 第十二节内部函数 5 一.测试函数 5 二...
  • 2.3.2 字符数据类型 46 2.3.3 整型修饰符 47 2.3.4 布尔类型 48 2.3.5 浮点类型 48 2.3.6 ISO/ANSI C++中的基本类型 49 2.3.7 字面值 50 2.3.8 定义数据类型的同义词 50 2.3.9 具有特定值集的变量 ...
  • Java开发技术大全(500个源代码).

    热门讨论 2012-12-02 19:55:48
    HelloNative.obj 用VB编译生成的目标文件 HelloNativeTest.java 测试本地化是否成功的类文件 instanceVar.java 定义一个实例成员变量 invokeByObject.java 对象实参传递示例程序 invokeByValue.java 传值调用...
  • 打冰雹游戏源程序

    2013-06-16 00:07:04
    本次课程设计利用《软件设计基础-VB》课程中所学到的编程知识和编程技巧,完成具有一定难度和工作量的程序设计题目,帮助学生掌握编程、调试的基本技能,独立完成所布置的任务。 要求: 1、对系统进行功能需求分析 2...
  • java源码包---java 源码 大量 实例

    千次下载 热门讨论 2013-04-18 23:15:26
     Java生成密钥、保存密钥的实例源码,通过本源码可以了解到Java如何产生单钥加密的密钥(myKey)、产生双钥的密钥对(keyPair)、如何保存公钥的字节数组、保存私钥到文件privateKey.dat、如何用Java对象序列化保存私钥...
  • java源码包2

    千次下载 热门讨论 2013-04-20 11:28:17
     Java生成密钥、保存密钥的实例源码,通过本源码可以了解到Java如何产生单钥加密的密钥(myKey)、产生双钥的密钥对(keyPair)、如何保存公钥的字节数组、保存私钥到文件privateKey.dat、如何用Java对象序列化保存私钥...

空空如也

空空如也

1 2
收藏数 39
精华内容 15
关键字:

vb如何判断字符类型