#递归 #栈
题目描述
给定一个平衡括号字符串 S，按下述规则计算该字符串的分数：
() 得 1 分。
AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。
(A) 得 2 * A 分，其中 A 是平衡括号字符串。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| 示例 1:
输入："()"
输出：1
示例 2：
输入："(())"
输出：2
示例 3：
输入："()()"
输出：2
示例 4：
输入："(()(()))"
输出：6
提示：
1. S 是平衡括号字符串，且只含有 ( 和 ) 。
2. 2 <= S.length <= 50
|
解题思路
(1). 考虑采用递归 + 栈来解题。括号问题首先天然就会想到使用栈，由于本题不需要考虑括号字符串的合法性，所以栈可以当作一个状态的保存，在栈内部进行递归；
(2). 对于嵌套的括号，采用递归的策略，出递归前将递归栈中分数*2 即可；
(3). 注意遍历字符串要使用指针以及出递归的条件。
时间复杂度
O(N).
解题代码
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
| func scoreOfParentheses(s string) int {
var scoreCount func(start *int) int
scoreCount = func(start *int) int {
ss := []byte{}
sc := 0
for ; *start<len(s); (*start)++ {
i := *start
if len(ss) == 0 && s[i] == '(' {
ss = append(ss, '(')
} else if s[i] == ')' && len(ss) == 0 {
break
} else if s[i] == ')' && ss[len(ss)-1] == '(' {
sc++
ss = ss[:len(ss)-1]
} else if s[i] == '(' && len(ss) != 0 {
sc += 2*scoreCount(start)
ss = ss[:len(ss)-1]
}
}
return sc
}
score := 0
stack := []byte{}
for i:=0; i<len(s); i++ {
if len(stack) == 0 {
stack = append(stack, '(')
} else if s[i] == ')' && stack[len(stack)-1] == '(' {
stack = stack[:len(stack)-1]
score++
} else {
score += 2*scoreCount(&i)
stack = stack[:len(stack)-1]
}
}
return score
}
|
#优先队列
题目描述
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
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
| 示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
示例 2：
输入：lists = []
输出：[]
示例 3：
输入：lists = [[]]
输出：[]
提示：
k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的总和不超过 10^4
|
解题思路
优先队列，直接看代码吧
时间复杂度
O(Nlog(N))，取决于堆排序的时间复杂度
解题代码
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
|
import "container/heap"
type IntHeap []int
var a []int
func (h IntHeap) Len() int {
return len(h)
}
func (h IntHeap) Less(i,j int) bool {
return a[h[i]]<a[h[j]]
}
func (h IntHeap) Swap(i,j int) {
h[i], h[j] = h[j], h[i]
}
func (h *IntHeap) Push(x interface{}) {
*h = append(*h, x.(int))
}
func (h *IntHeap) Pop() interface{} {
old := *h
n := len(*h)
x := old[n-1]
*h = old[:n-1]
return x
}
func mergeKLists(lists []*ListNode) *ListNode {
l := len(lists)
if l == 0 {
return nil
}
var h IntHeap
a = make([]int, l)
for i:=0; i<l; i++ {
if lists[i] == nil {
a[i] = -1
} else {
a[i] = lists[i].Val
heap.Push(&h, i)
}
}
if len(h) == 0 {
return nil
}
first := heap.Pop(&h).(int)
head := lists[first]
a[first] = math.MaxInt32
p := head
lists[first] = head.Next
p.Next = nil
if lists[first] != nil {
a[first] = lists[first].Val
heap.Push(&h, first)
}
for len(h) > 0 {
i := heap.Pop(&h).(int)
a[i] = math.MaxInt32
p.Next = lists[i]
p = p.Next
lists[i] = lists[i].Next
if lists[i] != nil {
a[i] = lists[i].Val
heap.Push(&h, i)
}
p.Next = nil
}
return head
}
|
