Commit04d3b40

committed

parentheses

1 parenta8093ee commit04d3b40Copy full SHA for 04d3b40

File tree

+55

-0

lines changed

+55

-0

lines changed

Lines changed: 55 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,55 @@`
	`1`	`+packageAlgorithms.string;`
	`2`	`+`
	`3`	`+importjava.util.Stack;`
	`4`	`+`
	`5`	`+publicclassLongestValidParentheses {`
	`6`	`+publicstaticvoidmain(String[]strs) {`
	`7`	`+System.out.println(longestValidParentheses("(()()())"));`
	`8`	`+ }`
	`9`	`+`
	`10`	`+publicintlongestValidParentheses(Strings) {`
	`11`	`+if (s ==null) {`
	`12`	`+return0;`
	`13`	`+ }`
	`14`	`+`
	`15`	`+Stack<Integer>stk =newStack<Integer>();`
	`16`	`+intsum =0;`
	`17`	`+inttmp =0;`
	`18`	`+`
	`19`	`+intmax =0;`
	`20`	`+`
	`21`	`+for (inti =0;i <s.length();i++) {`
	`22`	`+charc =s.charAt(i);`
	`23`	`+`
	`24`	`+if (c =='(') {`
	`25`	`+stk.push(i);`
	`26`	`+ }else {`
	`27`	`+if (stk.isEmpty()) {`
	`28`	`+// 栈中没有'(',出现')', 则必须重置计算`
	`29`	`+sum =0;`
	`30`	`+continue;`
	`31`	`+ }`
	`32`	`+`
	`33`	`+// count the temporary lenght:`
	`34`	`+// like: (()()()`
	`35`	`+// tmp = 2.`
	`36`	`+tmp =i -stk.pop() +1;`
	`37`	`+if (stk.isEmpty()) {`
	`38`	`+// 有一套完整的括号集，可以加到前面的一整套括号集上`
	`39`	`+// () (()())`
	`40`	`+// 1 2 第二套括号集可以加过来`
	`41`	`+sum +=tmp;`
	`42`	`+max =Math.max(sum,max);`
	`43`	`+ }else {`
	`44`	`+// 也可能是一个未完成的括号集，比如：`
	`45`	`+// () (()() 在这里 ()() 是一个未完成的括号集，可以独立出来计算，作为`
	`46`	`+// 阶段性的结果`
	`47`	`+tmp =i -stk.peek();`
	`48`	`+max =Math.max(tmp,max);`
	`49`	`+ }`
	`50`	`+ }`
	`51`	`+ }`
	`52`	`+`
	`53`	`+returnmax;`
	`54`	`+ }`
	`55`	`+}`

Comments

(0)