[day6] [LeetCode] [title20,21]

20. 有效的括号

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

有效字符串需满足:

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例 1:

输入:        "()"         输出:        true

示例 2:

输入:        "()[]{}"      输出:       true

示例 3:

输入:          "(]"         输出:        false

示例 4:

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

示例 5:

输入:         "{[]}"          输出:       true

错误的代码


错误代码Part 1


错误代码Part 2



正确的答案(能做出来真不容易啊~~~~~)


Part 1
Part 2

时间复杂度


时间复杂度

1.本题采用的方法是,寻找能够匹配的字符(最内层的字符),再删除匹配了的数组元素,然后数组下标减一(即稍微外层的字符),又开始匹配,依次匹配,如果未匹配成功,则直接返回false,如果执行完循环后,则返回true

2.本题输入的是字符串,无法直接删除指定的元素,于是先把字符串赋值为List,用list可以直接删除特定的元素。

3.一组字符匹配成功,需要删除匹配成功的数组元素,在删除的过程中遇到了问题,原问题程序是:

if ss[i+1] == ')':

                    del ss[i]

                    del ss[i+1]

                    continue

问题在于,第ss[i]与s[i+1]分别是'('和')',当删除第i个元素后,后面的元素会自动补齐上来。于是第i+1个元素不再是')',第i个元素是')'。于是要删除的不是ss[i+1],而是del ss[i]。当删除完这两个元素之后,下面就需要返回上一层,如果直接continue,则不能返回上一层,无法继续匹配。所以应该在continue前加i-=1。达到返回上一层的目的。

正确的程序应该为:

if ss[i+1] == ')':

                    del ss[i]

                    del ss[i]

                    i -= 1

                    continue

21.合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例:

输入: 1->2->4, 1->3->4

输出:1->1->2->3->4->4


合并两个有序链表
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 第2章 基本语法 2.1 概述 基本句法和变量 语句 JavaScript程序的执行单位为行(line),也就是一...
    悟名先生阅读 4,195评论 0 13
  • Spring Cloud为开发人员提供了快速构建分布式系统中一些常见模式的工具(例如配置管理,服务发现,断路器,智...
    卡卡罗2017阅读 134,854评论 18 139
  • 一、Python简介和环境搭建以及pip的安装 4课时实验课主要内容 【Python简介】: Python 是一个...
    _小老虎_阅读 5,803评论 0 10
  • 4月2日训练 最近一直感冒,今天锻炼完,感觉不错,冲了个热水澡。 我的目标是减肥,每周至少三次跑步,结合keep。...
    轶羽诗阅读 184评论 0 0
  • 佛说:世间和出世间的恩德有四种:第一种就是父母恩,第二种是众生恩,第三种是国王恩,第四种是三宝恩,这四种恩,每个众...
    在五台山闲逛的日子阅读 225评论 0 0