C++刷leetcode（921. 使括号有效的最少添加）【数据结构】

糖逗

题目描述：

1. 给定一个由 '(' 和 ')' 括号组成的字符串 S，我们需要添加最少的括号（ '(' 或是 ')'，可以在任何位置），以使得到的括号字符串有效。
   
2. 
   
3. 从形式上讲，只有满足下面几点之一，括号字符串才是有效的：
   
4. 
   
5. 它是一个空字符串，或者
   
6. 它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者
   
7. 它可以被写作 (A)，其中 A 是有效字符串。
   
8. 给定一个括号字符串，返回为使结果字符串有效而必须添加的最少括号数。
   
9. 
   
10.  
    
11. 
    
12. 示例 1：
    
13. 
    
14. 输入："())"
    
15. 输出：1
    
16. 示例 2：
    
17. 
    
18. 输入："((("
    
19. 输出：3
    
20. 示例 3：
    
21. 
    
22. 输入："()"
    
23. 输出：0
    
24. 示例 4：
    
25. 
    
26. 输入："()))(("
    
27. 输出：4
    
28.  
    
29. 
    
30. 提示：
    
31. 
    
32. S.length <= 1000
    
33. S 只包含&#160;'(' 和&#160;')'&#160;字符。
    
34. 
    
35. 来源：力扣（LeetCode）
    
36. 链接：https://leetcode-cn.com/problems/minimum-add-to-make-parentheses-valid
    
37. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     int minAddToMakeValid(string S) {
   
4.         map<char, int> store;
   
5.         int len = S.size();
   
6.         for(int i = 0 ; i < len; i++){
   
7.             if(S[i] == '('){
   
8.                 store['(']++;
   
9.             }else if(S[i] == ')'){
   
10.                 if(store.find('(') != store.end() && store['('] > 0){
    
11.                     store['(']--;
    
12.                 }else{
    
13.                     store[')']++;
    
14.                 }
    
15.             }
    
16.         }
    
17.         int res = 0;
    
18.         res = store['('] + store[')'];
    
19.         return res;
    
20.     }
    
21. };

复制代码

糖逗

一次过