括号类

各种括号题 基本上算是栈的经典应用了

难度值1:
删除最外层的括号
难度值3:
括号的分数
移除无效的括号

例1

括号的分数
原题链接
https://leetcode.cn/problems/score-of-parentheses/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
package main

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func scoreOfParentheses(s string) int {
	stk := make([]int, 1)
	for _, ch := range s {
		if ch == '(' {
			stk = append(stk, 0)
		} else {
			v := max(1, stk[len(stk)-1]*2)
			stk = stk[:len(stk)-1]
			stk[len(stk)-1] += v
		}

	}

	return stk[len(stk)-1]
}

例2

删除最外层的括号
原题链接:
https://leetcode.cn/problems/remove-outermost-parentheses/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
package main

import "strings"

/**
其实就是找到所有刚好配对的括号
然后 再将这些刚好匹配的括号的最外层去掉
*/
func removeOuterParentheses(s string) string {
	stk := 0
	ans := make([]string, 0)
	tmp := []rune("")
	for _, ch := range s {
		if ch == '(' {
			tmp = append(tmp, ch)
			stk++
		} else {
			stk = stk - 1
			tmp = append(tmp, ch)
			if stk == 0 {
				tmp = tmp[1 : len(tmp)-1]
				ans = append(ans, string(tmp))
                tmp = tmp[0:0]
			}
		}
	}

	return strings.Join(ans,"")
}

例3

移除无效括号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
package main

/**
先遍历一遍 贪心原则维持左右括号相同
最后如果还是左括号太多 则删除多余的左括号即可
*/
func minRemoveToMakeValid(s string) string {
	tmp := []rune("")
	stk := 0
	for _, ch := range s {
		if ch == '(' {
			stk = stk + 1
			tmp = append(tmp, ch)
		} else if ch == ')' {
			if stk <= 0 {
                continue
			}
            tmp = append(tmp,ch)
            stk = stk - 1
		} else {
			tmp = append(tmp, ch)
		}
	}

	if stk > 0 {
		ans := []rune("")
		for i := len(tmp) - 1; i >= 0 ; i--{
            if stk > 0 && tmp[i] == '('{
               stk = stk - 1
               continue 
            }
            ans = append(ans,tmp[i])
        }
        
        for i,j := 0,len(ans) - 1 ; i < j ; i,j = i + 1,j - 1{
            ans[i],ans[j] = ans[j],ans[i]
        }
		return string(ans)

	} else {
		return string(tmp)
	}
}