请人做网站收费多少,深圳电商网站建设公司,基层科普网站建设的现状,网站制作公司 顺的Problem: 921. 使括号有效的最少添加 文章目录 题目描述思路及解法复杂度Code 题目描述 思路及解法 1.定义int变量res、need分别记录需要插入的左括号数和所需与左括号配对的右括号数#xff1b; 2.遍历字符串#xff1a; 2.1.若当为左括号#xff0c;则need#xff0c;表示… Problem: 921. 使括号有效的最少添加 文章目录 题目描述思路及解法复杂度Code 题目描述 思路及解法 1.定义int变量res、need分别记录需要插入的左括号数和所需与左括号配对的右括号数 2.遍历字符串 2.1.若当为左括号则need表示需要一个右括号与当前左括号配对 2.2.若当前为右括号则need–表示已经有一个右括号与左括号配对 2.2.1.若发现当前need -1则表示需要插入一个左括号即res 3.返回最后需要插入的左括号数和需要和当前左括号配对的右括号数即res need 复杂度
时间复杂度: O ( n ) O(n) O(n);其中 n n n为给定字符串的长度 空间复杂度: O ( 1 ) O(1) O(1) Code
class Solution {/*** Minimum Add to Make Parentheses Valid** param s Given string* return int*/public int minAddToMakeValid(String s) {// Record the number of left bracket insertion requirementsint res 0;int need 0;for (int i 0; i s.length(); i) {if (s.charAt(i) () {// Add one to the required number of right parenthesesneed;}if (s.charAt(i) )) {// Add one to the required number of left parenthesesneed--;if (need -1) {need 0;//Subtract one to the required number of right parenthesesres;}}}return need res;}
}
