• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

LeetCode 1541 .平衡括号字符串的最少插入次数


Recommended Posts

原题链接在这里:https://leet代码。com/problems/minimum-inserts-to-balance-a-parents-string/

题目:

给定一个只包含字符"("和")"的括号字符串。括号字符串是balancedif:

任何左括号"("必须有相应的两个连续的右括号"))"。

左括号"("必须在相应的两个连续的右括号"))"之前。

换句话说,我们将'('视为左括号,而'))'视为右括号。

比如"())"、"())(()))"、"(()))))"是平衡的,"())"、"()))"是不平衡的。

如果需要,可以在字符串的任何位置插入字符'('和')',以平衡字符串。

返回使平衡所需的最小插入数。

示例1:

Input: s='(()))' .

输出: 1

解释:第二个'('有两个匹配的')',但第一个'('只有')'匹配。我们需要在字符串的末尾再加一个")"成为"(())))",这样就平衡了。

示例2:

输入: s='())'

输出: 0

解释:弦已经平衡。

示例3:

Input: s='))())('

输出: 3

解释:添加"('匹配第一个"))",添加"))"匹配最后一个"("。

约束:

1=标准长度=105

仅由"("和")"组成。

题解:

数数是遇到的(的数量。

当我们遇到一个(,简单地做计数。

当我们遇到一个)。首先我们需要检查是否有2个连续的)。

如果是,我们需要将索引和减计数移动1。

如果没有,那么它是一个简单的),我们需要使它连续2))并减去计数1。

时间复杂度北:号.n=标准长度()。

空间: O(1).

AC Java:

一类解决方案{

2个公共int min插入(字符串){

3 if(s==null || s.length()==0){

四返回0;

5 }

6

7 int count=0;

8 int RES=0;

9 for(int I=0;国际标准长度();i ){

10 char c=s . charat(I);

11 if(c=='('){

12计数;

13 }其他{

14 if(国际标准长度()-1s。charat(I 1)=)'){

15i

16如果(计数0){

17计数-;

18 }其他{

19决议

20 }

21 }其他{

22分辨率

23如果(计数0){

24计数-;

25 }其他{

26分辨率

27 }

28 }

29 }

30 }

31

32返回结果计数* 2;

33 }

34 }

类似使括号有效的最小加法。

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now