当前位置：首页 > news >正文

括号有效配对题型问题解法

news 来源：原创 2023/2/1 16:47:10

问题描述：

问题一：怎么判断一个括号字符串有效？

问题二：如果一个括号字符串无效，返回至少填几个字符能让其整体有效。

问题三：返回一个括号字符串中，最长的括号有效子串的长度。

问题四：保证括号字符串有效的前提下，求括号嵌套的深度。

问题描述：

括号有效配对是指：

1）任何一个左括号都能找到和其正确配对的右括号，

2）任何一个右括号都能找到和其正确配对的左括号有效的：

(()) ()() (()()) 等无效的： (() )( 等。

问题一：怎么判断一个括号字符串有效？

定义一个变量count，从左遍历字符串到最右，出现左括号时count加一，出现右括号时count减一。若整个字符串有效时，遍历过程中count值不会出现负值，并且最后count的值一定为0。

    public static boolean isValid(String str) {
        if (str == null || str.length() == 0) {
            return false;
        }
        char[] c = str.toCharArray();
        int n = c.length;
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (c[i] == '(') {
                count++;
            } else {
                count--;
            }
            if (count < 0) {
                return false;
            }
        }
        return count == 0;
    }

问题二：如果一个括号字符串无效，返回至少填几个字符能让其整体有效。

在上一个问题的基础上新增变量need用来统计需要添加的字符数量。在从字符串最左遍历到最右的过程中，若count出现了负值（只可能出现的负值为-1），则表明从该字符开始字符串失效，需要添加一个左括号让其变为有效值，need加一。遍历到字符串的最右时还可能count不为0，所以我们最后需要添加的字符串中还需要加上最后count中的值。

    public static int needParentheses(String str) {
        char[] c = str.toCharArray();
        int n = c.length;
        int count = 0;
        int need = 0;
        for (int i = 0; i < n; i++) {
            if (c[i] == '(') {
                count++;
            } else {
                count--;
            }
            if (count == -1) {
                need++;
                count = 0;
            }
        }
        return need + count;
    }

    public static int needParentheses2(String str) {
        char[] c = str.toCharArray();
        int n = c.length;
        int count = 0;
        int need = 0;
        for (int i = 0; i < n; i++) {
            if (c[i] == '(') {
                count++;
            } else {
                if (count == 0) {
                    need++;
                } else {
                    count--;
                }
            }
        }
        return need + count;
    }

问题三：返回一个括号字符串中，最长的括号有效子串的长度。

动态规划，生成一个记录位置结尾的形成的最长子串的数组。假设我们现在求i位置的最长有效子串的长度，我们已经知道i-1位置的最长有效子串长度为l，如果此时i位置时左括号，那么此时以i位置结尾不可能形成有效子串，则有效子串长度为0，若是以右括号结尾的那么我们可以看此时从i位置向前推l的长度的前一个位置是否是一个左括号，若不是则以i位置结尾的最长子串长度为0，若是那么我们可以确定以i位置结尾的最长子串的最小长度是l+2，还能不能更长我们要看此时最少形成的子串的开头位置的前一个位置为结尾的子串的长度相加。

    public static int maxParenthesesLen(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        char[] c = str.toCharArray();
        int n = c.length;
        int[] dp = new int[n];
        dp[0] = 0;
        int max = 0;
        for (int i = 1; i < n; i++) {
            if (c[i] == ')') {
                if (i - dp[i - 1] - 1 >= 0) {
                    dp[i] = c[i - dp[i - 1] - 1] == '(' ? dp[i - 1] + 2 : 0;
                }
                if (i - dp[i - 1] - 2 >= 0) {
                    dp[i] = dp[i] + dp[i - dp[i - 1] - 2];
                }
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }

问题四：保证括号字符串有效的前提下，求括号嵌套的深度。

一个变量count用于遍历过程中的左括号加一，右括号减一。max记录每一次遍历过程中count值，抓取到遍历过程中count的最大值。

    public static int deep(String str) {
        char[] c = str.toCharArray();
        int max = 0;
        int count = 0;
        for (int i = 0; i < c.length; i++) {
            count = c[i] == '(' ? count + 1 : count - 1;
            max = Math.max(max, count);
        }
        return max;
    }

python导入安装包

主要分两种方式：在线安装和离线安装在线安装因为我公司开发是在云桌面，里面是没有外网的。之前是只能离线安装，后面搭了一个内部镜像环境。 1.添加配置文件进行换源 2.检查requirements.txt配置 3.直接使用pycahrm工具install 换源 …...

编程日记 2023/2/1 16:38:41

POJ - 2406 Power Strings next数组应用循环节

题目链接：点击查看 Language:Default Power Strings Time Limit: 3000MS Memory Limit: 65536KTotal Submissions: 61784 Accepted: 25534Description Given two strings a and b we define a*b to be their concatenation. For example, if a "abc" and…...

编程日记 2023/2/1 16:30:54

JS中 [] == ![]结果为true，而 {} == !{}却为false，追根刨底

转载自 JS中 [] ![]结果为true，而 {} !{}却为false， 追根刨底 console.log( [] ![] ) // true console.log( {} !{} ) // false 在比较字符串、数值和布尔值的相等性时，问题还比较简单。但在涉及到对象的比较时，问题就变…...

编程日记 2023/2/1 16:29:24

Spring Boot 自动配置的 “魔法” 是如何实现的？

转载自 Spring Boot 自动配置的 “魔法” 是如何实现的？ Spring Boot是Spring旗下众多的子项目之一，其理念是约定优于配置，它通过实现了自动配置（大多数用户平时习惯设置的配置作为默认配置）的功能来为用户快速构建出…...

编程日记 2023/2/1 16:27:24

每天五分钟机器学习：超平面分离定理和凸优化

凸集和凸函数在点集拓扑学与欧几里得空间中，凸集是一个点集，其中每两点之间的直线上的点都落在该点集中。如下所示：函数任意两点(x,f(x))和(y,f(y))连线上的值大于(x,y)区间内任意一点m的值f(m)，那么这个函数就是一个凸函数：超平面分离定理空间中存在两类样本，…...

编程日记 2023/2/1 16:26:54

AcWing 848. 有向图的拓扑序列

原题链接：AcWing 848. 有向图的拓扑序列给定一个 n 个点 m 条边的有向图，点的编号是 1 到 n，图中可能存在重边和自环。请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 −1。若一个由图中所有点…...

编程日记 2023/2/1 16:26:30

数论一些小总结

1.对于任意一个素数p, n!中含有p的个数为 (n/p n/p^2 n/p^3 ......). 2.c(n,k) n! / ( k! * (n-k)! ). 3.c(n,k)(n-k1)/k*c(n,k-1). 4.任意一个数n可以写成若干个素数的乘积，即 p1^a1 * p2^a2*......*pn^an， 它的的约数的个数为 (a11)*(a21)*..…...

编程日记 2023/2/1 16:24:48

Spring MVC竟然有5种参数绑定的方式？你知道几种？

转载自 Spring MVC竟然有5种参数绑定的方式？你知道几种？ SpringMVC参数绑定，简单来说就是将客户端请求的key/value数据绑定到controller方法的形参上，然后就可以在controller中使用该参数了下面通过5个常用的注解演示下如何进行参…...

编程日记 2023/2/1 16:24:21

接口测试那些事儿

什么是接口？ 首先，在讲接口测试之前，我们先要搞清楚接口类型的概念。接口：可能是系统与系统（包括服务与服务）之间的调用，像A系统（服务）给B系统（服务&#x…...

编程日记 2023/2/1 16:22:57

mysql重置Root密码

方法一: 在my.ini的[mysqld]字段加入： skip-grant-tables 重启mysql服务，这时的mysql不需要密码即可登录数据库然后进入mysql mysql>use mysql; mysql>更新 user set passwordpassword(新密码) WHERE Userroot; mysql>flush privileges; 运…...

编程日记 2023/2/1 16:19:30

Google Swift 与 DC 传输

网络拥塞，默认指转发节点出现了严重的排队现象，甚至队列溢出而丢包。、但接收端也是一个统计复用系统(通用 OS 均为统计复用系统，比如 Linux)，但凡统计复用系统就是潜在拥塞点，即可套用排队论模型。人们很少将最后…...

编程日记 2023/2/1 16:16:16

每天一个adb命令：wm命令详解

wm命令可以用于获取屏幕分辨率、像素密度等。前提：Android4.3及以上 usage: wm [subcommand] [options]wm size [reset|WxH]wm density [reset|DENSITY]wm overscan [reset|LEFT,TOP,RIGHT,BOTTOM]wm size: return or override display size.wm density: overrid…...

编程日记 2023/2/1 15:56:19

idea插件开发入门

前言：最近想研究一款自动在idea中定位缺陷及发送JIRA的快捷工具，方便提升报自动化脚本的bug的效率。因为idea插件学习是必不可少了，沉淀小结如下。 idea插件开发入门插件用途工程创建配置文件Action实现开发语法常用对象常用方法运行效果打包…...

编程日记 2023/2/1 15:47:46

读王安石变法

今天早上读到王安石变法，王安的变法确实充满理想化。以现代金融的办法进行国家的经济改革。但最终却并未走向成功，其中值得我们反思。思想太过超前，在没有实际土壤的环境下，再好的策略都难免不可能实现，这让我想起来摩…...

编程日记 2023/2/1 15:36:10

2017 ICPC Asia Urumqi I. A Possible Tree 带权并查集

题目链接：https://nanti.jisuanke.com/t/40520 题解：因为他们都是联通的且只有唯一路径，所以不用管之前怎么连的，直接按照他给的查询，带权并查集判断即可 #include <bits/stdc.h> using namespace std; const …...

编程日记 2023/2/1 15:36:04

基于数据驱动的接口自动化测试解决方案

总结一下我么项目中使用的基于数据驱动的接口自动化测试解决方案，仅供大家参考。1.接口框架设计结构 2.接口测试脚本设计原则 3.持续集成这块用jenkins就可以了，就不介绍了，目前我们项目的集成规则介绍一下： 1.脚本job与应用对…...

编程日记 2023/2/1 15:25:31

JavaFX其他事件

一、其他事件 InputMethodEvent.InputMethodTextChanged 文本输入改变 ContextMenuEvent.CONTEXT_MENU_REQUESTED 上下文菜单请求二、用法 node.setOnXX(event->{//do something });node.addEventFilter(XXEvent.XX, event -> {//do something});...

编程日记 2023/2/1 15:03:36

SpringBoot开启事务

Transactional 直接在想要启动事务的方法或者类上添加Transactional注解即可，在类上添加注解，默认类下的所有方法都会使用事务。在类上添加注解 Transactional Service public class UserServiceImpl implements UserService { } 在方法上添加注解 …...

编程日记 2023/2/1 15:01:53

深入探索 Java 热部署

转载自深入探索 Java 热部署简介在 Java 开发领域，热部署一直是一个难以解决的问题，目前的 Java 虚拟机只能实现方法体的修改热部署，对于整个类的结构修改，仍然需要重启虚拟机，对类重新加载才能完成更新操作。对…...

编程日记 2023/2/1 14:56:14

C++设计模式

管理变化， 提高复用两种手段：分解抽象八大原则：https://blog.csdn.net/mmk27_word/article/details/108521903 重构技法： 静态 -> 动态早绑定 -> 晚绑定继承 -> 组合编译时依赖 -> 运行时依赖紧耦合 ->…...

编程日记 2023/2/1 14:55:24

spring boot深入及启动原理探究

围绕spring boot 的优点，本文我们来探究一下spring boot具体是如何实现这些特性的。自动配置：针对很多Spring应用程序和常见的应用功能，Spring boot能自动提供相关配置；起步依赖：告诉Spring boot需要什么功能,它就能引…...

编程日记 2023/2/1 14:55:20

为什么大公司一定要使用DevOps

转载自为什么大公司一定要使用DevOps 0 DevOps的意图究竟什么是DevOps? 要想回答这个问题，首先要明确DevOps这个过程参与的人员是谁？即开发团队和IT运维团队！那么，DevOps的意图是什么呢？即在两个团队之间&#…...

编程日记 2023/2/1 14:54:44

JfreeChart柱状图饼图

JfreeChart画出柱状图饼图的代码片段及详细的注释，附件为JfreeChart中文API一览表，和生成的柱状图，饼图图片 import java.awt.Font; import java.io.FileOutputStream; import java.io.IOException; import org.jfree.chart.C…...

编程日记 2023/2/1 14:54:01

自动装配的底层实现

public void autowire(Object o, Map<String, String> map) throws Exception { // 获得map 所有key Set<String> keys map.keySet(); // 获得Object中所有属性 // 获得Class对象 Class c o.getClass(); // 获得…...

编程日记 2023/2/1 14:53:01

文件上传，你还存储在应用服务器?

文章目录前言一、准备工作1. 开通腾讯云对象存储服务2. 创建存储桶3. 密钥管理，创建密钥三、整合步骤1. 添加maven依赖2. yml文件增加配置3. 新建 COS 配置类4. 新建 COS 上传工具类5. 新建 Controller 上传接口6. 测试总结前言嗨，大家好，我…...

编程日记 2023/2/1 14:29:46

Java异常打印输出中常见方法的分析

Java异常是在Java应用中的警报器，在出现异常的情况下，可以帮助我们程序猿们快速定位问题的类型以及位置。但是一般在我们的项目中，由于经验阅历等多方面的原因，依然有若干的童鞋在代码中没有正确的使用异常打印方法，导…...

编程日记 2023/2/1 14:21:39

Mysql调优你不知道这几点，就太可惜了

转载自 Mysql调优你不知道这几点，就太可惜了一、Mysql的逻辑分层 Mysql分为：连接层、服务层、引擎层、存储层。当客户端向服务端发起操作请求的时候，执行过程是这样的： 1、客户端端与Mysql服务端的连接层建立连接&#xff…...

编程日记 2023/2/1 13:34:30

数据可视化之汽车销量，截止到2022年目前中国汽车保有量是3.02亿辆

汽车在我们日常生活中是必不可少的代步工具，随着中国的经济发展，截止到2022年目前中国汽车保有量是3.02亿辆，2021年全国新注册登记机动车就已达3674万辆。现在居民的生活越来越好，小编通过数据可视化分析整理了一些工业汽车的产销…...

编程日记 2023/2/1 13:31:48

八大设计模式原则

1.依赖倒置原则高层模块不依赖底层模块，二者都应该依赖抽象抽象不依赖实现细节，实现细节应该依赖于抽象这一原则与下面的针对接口编程而不是针对实现编程是一个道理，我们设计一个程序，我们应该先想好我们想要抽象什么&#x…...

编程日记 2023/2/1 13:26:31

每天一个adb命令：input 命令详解

input命令可以用于向键盘发送一些指令，先看看input的官方说明： Usage: input [<source>] <command> [<arg>...]The sources are:mousekeyboardjoysticktouchnavigationtouchpadtrackballstylusdpadtouchscreengamepadThe commands an…...

编程日记 2023/2/1 13:25:04

CSDN 编程竞赛·第八期总结

CSDN 编程竞赛第八期总结1.代写匿名信2.小艺改编字符串3.开学趣闻之美食诱惑4.争抢糖豆CSDN 编程竞赛第八期为笔者参加的第三次 CSDN 编程竞赛，本来报名了第七期的，因为时间和二十大撞了，就错过了，第八期成绩似乎不错，…...

编程日记 2023/2/1 13:22:45

写给工程师的10条精进原则

转载自写给工程师的10条精进原则引言时间回到8年前，我人生中的第一份实习工作，是在某互联网公司的无线搜索部做一个C工程师。当时的我可谓意气风发，想要大干一场，结果第一次上线就写了人生中第一个CaseStudy。由于对部署环境…...

编程日记 2023/2/1 13:18:29

基于java的开源车牌识别源码

真正的大师,永远都怀着一颗学徒的心！ 有没有发现昨天断更了一天年底各种写文档准备项目验收刚好也快放假啦忙完这几天要回老家过年了可能要断更一段时间啦年后会继续的今天给大家推荐一个开源的车牌识别的demo源码技术选型软件架构 B/S 架构&…...

编程日记 2023/2/1 13:11:07

matlab图形功能

//...

编程日记 2023/2/1 13:08:45

程序员着装的改变

是什么力量，让任何地方的程序员都享有「免于体面的自由」？ 在今天的社会里，工程师往往代表着知识水平和社会地位。每当普通人听到这个头衔，总会报之以敬仰的目光： 但有一种工程师，虽然也是如假包换的高级技…...

编程日记 2023/2/1 12:48:05

你真的很熟分布式和事务吗？

转载自你真的很熟分布式和事务吗？ 微吐槽 hello,world. 不想了，我等码农，还是看看怎么来处理分布式系统中的事务这个老大难吧！ 本文略长，读者需要有一定耐心，如果你是高级码农或者架构师级别&#xf…...

编程日记 2023/2/1 12:33:56

组合数总结

转自：国特震哥点击查看链接对于求C(n,m) 1.如果是对于小范围内的n和m（不是很难）就不说了差不多用java的大数就可以了 2.当n在1e10^5范围左右，往往是会有取模，设这个数为mod（往往mod为质数&#xff0…...

编程日记 2023/2/1 12:32:33

HDU 5667 Sequence 矩阵快速幂 + 费马小定理

olion August will eat every thing he has found. Now there are many foods,but he does not want to eat all of them at once,so he find a sequence. fn⎧⎩⎨⎪⎪1,ab,abfcn−1fn−2,n1n2otherwise He gives you 5 numbers n,a,b,c,p,and he will eat fn foods.B…...

编程日记 2023/2/1 12:07:15

ACID中C与CAP定理中C的区别

转载自 ACID中C与CAP定理中C的区别 ACID和CAP定理中都有C，代表Consistent一致性，很多人容易将这两个C混为一谈，其实这两个一致性是有区别的。事务的定义是一系列操作要么全部成功，要么全部不成功，数据库的事务机制是…...

编程日记 2023/2/1 11:42:12

Gym - 100589A Queries on the Tree 树状数组+分块

题目链接：https://vjudge.net/problem/Gym-100589A 题意：n个点，根节点为1的树，两种操作，1 L y 与根节点距离为L的节点权值全部加上y，2 x x子树的权值总和题解：对于更新操作，因为更…...

编程日记 2023/2/1 11:38:47

CodeForces - 1073C Vasya and Robot

Vasya has got a robot which is situated on an infinite Cartesian plane, initially in the cell (0,0) . Robot can perform the following four kinds of operations: U — move from (x,y) to (x,y1) ;D — move from (x,y)to (x,y−1);L — move from (x,y)to (x−1,…...

编程日记 2023/2/1 11:37:58

问题描述：

问题一：怎么判断一个括号字符串有效？

问题二：如果一个括号字符串无效，返回至少填几个字符能让其整体有效。

问题三：返回一个括号字符串中，最长的括号有效子串的长度。

问题四：保证括号字符串有效的前提下，求括号嵌套的深度。

相关文章：