当前位置:网站首页>921. Minimum additions to make parentheses valid
921. Minimum additions to make parentheses valid
2022-07-06 16:08:00 【mrbone9】
Address :
Power button https://leetcode-cn.com/problems/minimum-add-to-make-parentheses-valid/
subject :
Given a by '(' and ')' A string of parentheses S, We need to add at least parentheses ( '(' or ')', Can be anywhere ), To make the resulting parenthesis string valid .
In form , Only meet one of the following , Bracket strings are valid :
It's an empty string , perhaps
It can be written as AB (A And B Connect ), among A and B Are valid strings , perhaps
It can be written (A), among A Is a valid string .
Given a bracket string , Returns the minimum number of parentheses that must be added to make the result string valid .
Example 1:
Input :"())" Output :1 |
Example 2:
Input :"(((" Output :3 |
Example 3:
Input :"()" Output :0 |
Example 4:
Input :"()))((" Output :4 |
Tips :
S.length <= 1000 S Contains only '(' and ')' character . |
source : Power button (LeetCode)
link :https://leetcode-cn.com/problems/minimum-add-to-make-parentheses-valid
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
Ideas :
The given string has only Left parenthesis , Right bracket , If the quantity matches, it doesn't mean the expected result
such as :)))(((
Because I met Right bracket
If there is no left parenthesis in front , You must add left parentheses to match
If there is an open parenthesis in front , Then subtract one from the number of left parentheses
Meet the left bracket , We need the following characters to see if there is , So count the next number
Finally back to Left parenthesis , Right bracket ( We use it to calculate the new quantity ) The sum of
Method 1 、 Traversal Statistics
int minAddToMakeValid(char * s){
int lnum = 0, rnum = 0;
int i = 0;
while(s[i])
{
if(s[i] == '(')
lnum++;
else
{
if(lnum > 0)
{
lnum--;
}
else
rnum++;
}
i++;
}
return lnum + rnum;
}
边栏推荐
- [exercise-5] (UVA 839) not so mobile (balance)
- Truck History
- Perform general operations on iptables
- 【练习-9】Zombie’s Treasure Chest
- Luogu P1102 A-B number pair (dichotomy, map, double pointer)
- C language learning notes
- Information security - threat detection engine - common rule engine base performance comparison
- Alice and Bob (2021牛客暑期多校训练营1)
- STM32 how to use stlink download program: light LED running light (Library version)
- Understand what is a programming language in a popular way
猜你喜欢
渗透测试 ( 4 ) --- Meterpreter 命令详解
Analyse du format protobuf du rideau en temps réel et du rideau historique de la station B
信息安全-安全编排自动化与响应 (SOAR) 技术解析
渗透测试 ( 8 ) --- Burp Suite Pro 官方文档
Borg Maze (BFS+最小生成树)(解题报告)
Nodejs+vue online fresh flower shop sales information system express+mysql
Pyside6 signal, slot
Determine the Photo Position
树莓派4B安装opencv3.4.0
Determine the Photo Position
随机推荐
Interesting drink
[exercise-6] (UVA 725) division = = violence
HDU-6025-Coprime Sequence(女生赛)
Auto. Getting started with JS
【练习-7】(Uva 10976)Fractions Again?!(分数拆分)
Research Report of exterior wall insulation system (ewis) industry - market status analysis and development prospect prediction
【练习4-1】Cake Distribution(分配蛋糕)
Opencv learning log 24 -- Hough transform 2 (maximum interval and minimum length can be limited)
Opencv learning log 26 -- detect circular holes and mark them
Ball Dropping
Opencv learning log 12 binarization of Otsu method
Ball Dropping
Analyse du format protobuf du rideau en temps réel et du rideau historique de la station B
【练习-9】Zombie’s Treasure Chest
渗透测试 ( 4 ) --- Meterpreter 命令详解
[exercise-4] (UVA 11988) broken keyboard = = (linked list)
Find 3-friendly Integers
Path problem before dynamic planning
[exercise-9] Zombie's Treasury test
E. Breaking the Wall