Emove

  • 首页
  • 归档
  • 分类
  • 标签

  • 搜索
context 反射 channel LRU BeanDefinition JVM 装饰者模式 MyBatis 快慢指针 归并排序 链表 hash表 栈 回溯 贪心 主从复制 二分查找 双指针 动态规划 AOF RDB 规范 BASE理论 CAP B树 RocketMQ Sentinel Ribbon Eureka 命令模式 访问者模式 迭代器模式 中介者模式 备忘录模式 解释器模式 状态模式 策略模式 职责链模式 模板方法模式 代理模式 享元模式 桥接模式 外观模式 组合模式 适配器模式 建造者模式 原型模式 工场模式 单例 UML 锁 事务 sql 索引

有效括号

发表于 2020-04-18 | 分类于 算法题 | 0 | 阅读次数 199

题目:四数之和

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

有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。

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

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

解题思路:

  1. 对于有效的括号,总是成对出现,且左括号必须先于右括号出现
  2. 对于案例"()[]{}"分析,其中的“(”在第一位,")"在最后一位,也就是说,对括号的匹配有先后顺序,且对于“([{”,来说,总是先进先出,故可以使用栈来辅助匹配的实现,每个右括号前必须有左括号与之匹配。
  3. 在栈中,如果栈的长度大于s长度的二分之一,即可以视为不匹配,因为匹配到最后总会有多余的符号无法匹配。
  4. 同理,如果s的长度为奇数,尽管绝大多数的括号可以匹配,但至少会有一个括号是无法匹配的

题解代码如下:

class Solution {
    public boolean isValid(String s) {
        if (null == s || s.length() % 2 == 1) {
            return false;
        }
        if (s.startsWith(")") || s.startsWith("]") || s.startsWith("}")) {
            return false;
        }
        char[] chars = s.toCharArray();
        int len = chars.length;
        Stack<Character> stack = new Stack<>();
        for (char aChar : chars) {
            if ('(' == aChar) {
                stack.push(')');
            } else if ('[' == aChar) {
                stack.push(']');
            } else if ('{' == aChar) {
                stack.push('}');
            } else if (stack.isEmpty() || aChar != stack.pop()) {
                return false;
            }
            if (stack.size() > len / 2) {
                return false;
            }
        }
        return stack.isEmpty();
    }
}
# context # 反射 # channel # LRU # BeanDefinition # JVM # 装饰者模式 # MyBatis # 快慢指针 # 归并排序 # 链表 # hash表 # 栈 # 回溯 # 贪心 # 主从复制 # 二分查找 # 双指针 # 动态规划 # AOF # RDB # 规范 # BASE理论 # CAP # B树 # RocketMQ # Sentinel # Ribbon # Eureka # 命令模式 # 访问者模式 # 迭代器模式 # 中介者模式 # 备忘录模式 # 解释器模式 # 状态模式 # 策略模式 # 职责链模式 # 模板方法模式 # 代理模式 # 享元模式 # 桥接模式 # 外观模式 # 组合模式 # 适配器模式 # 建造者模式 # 原型模式 # 工场模式 # 单例 # UML # 锁 # 事务 # sql # 索引
删除链表的倒数第N个节点
网站推荐
  • 文章目录
  •   |  
  • 概览
林亦庭

林亦庭

less can be more

87 文章
11 分类
54 标签
RSS
Github
Creative Commons
© 2021 林亦庭
粤ICP备20029050号