用栈实现队列
232. 用栈实现队列 - 力扣（LeetCode）
用两个栈实现先入先出队列
在Go中用切片模拟栈，一个输入栈，一个输出栈
- 入队：存入输入栈
- 出队：弹出输出栈顶，若输出栈为空，将输入栈所有数据存入输出栈
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
|
type MyQueue struct {
stackIn []int // 输入栈
stackOut []int // 输出栈
}
func Constructor() MyQueue {
return MyQueue{
stackIn: make([]int, 0),
stackOut: make([]int, 0),
}
}
// 入队
func (this *MyQueue) Push(x int) {
this.stackIn = append(this.stackIn, x) // 往输入栈追加
}
// 出队
func (this *MyQueue) Pop() int {
if len(this.stackOut) == 0 { // 输出栈为空
if len(this.stackIn) == 0 { // 输入栈也为空
return -1
}
for i := len(this.stackIn) - 1; i >= 0; i-- { // 从输入栈顶逐个取元素存入输出栈
this.stackOut = append(this.stackOut, this.stackIn[i]) // 输入栈元素存入输出栈
}
this.stackIn = []int{} // 清空输入栈
}
res := this.stackOut[len(this.stackOut)-1] // 取出出栈元素
this.stackOut = this.stackOut[:len(this.stackOut)-1] // 更新输出栈
return res
}
// 获取队头值
func (this *MyQueue) Peek() int {
res := this.Pop() // 出队
if res == -1 { // 队空
return -1
}
this.stackOut = append(this.stackOut, res) // 放回输出栈
return res
}
// 判队空
func (this *MyQueue) Empty() bool {
return len(this.stackOut) == 0 && len(this.stackIn) == 0
}
|
- 时间复杂度: push和empty为O(1)，pop和peek为O(n)
- 空间复杂度: O(n)
用队列实现栈
225. 用队列实现栈 - 力扣（LeetCode）
用两个队列实现一个后入先出（LIFO）的栈
其实这道题目就是用一个队列就够了，一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部，此时再去弹出对头元素就是栈的顺序了
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
|
type MyStack struct {
queue []int
}
func Constructor() MyStack {
return MyStack{
queue: make([]int, 0),
}
}
// 进栈
func (this *MyStack) Push(x int) {
this.queue = append(this.queue, x) // 追加到队列尾
}
// 出栈
func (this *MyStack) Pop() int {
// count:队首到倒数第二个元素的个数
for count := len(this.queue) - 1; count != 0; count-- { // 除了最后一个元素其余元素重新加到队尾
val := this.queue[0] // 取一个队首元素
this.queue = this.queue[1:] // 队首后面的元素前移
this.queue = append(this.queue, val) // 重新加到队尾
}
res := this.queue[0] // 取队首元素
this.queue = this.queue[1:len(this.queue)] // 更新队列
return res
}
// 获取栈顶值
func (this *MyStack) Top() int {
res := this.Pop() // 栈顶出栈
this.queue = append(this.queue, res) // 重新加到队尾
return res
}
// 判栈空
func (this *MyStack) Empty() bool {
return len(this.queue) == 0
}
|
- 时间复杂度: pop为O(n)，其他为O(1)
- 空间复杂度: O(n)
有效的括号
20. 有效的括号 - 力扣（LeetCode）
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
遍历字符串，遇到左括号加入栈，遇到右括号就弹出栈顶元素（左括号），若不匹配，则返回false，遍历结束后，若栈内还剩左括号，返回false
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
func isValid(s string) bool {
stack := make([]rune, 0)
for _, v := range s {
if v == '(' || v == '[' || v == '{' { // 遍历到左括号
stack = append(stack, v) // 入栈
} else { // 遍历到右括号
if len(stack) <= 0 { // 没有左括号
return false
}
if v == ')' && stack[len(stack)-1] != '(' { // 左括号不匹配
return false
} else if v == ']' && stack[len(stack)-1] != '[' { // 左括号不匹配
return false
} else if v == '}' && stack[len(stack)-1] != '{' { // 左括号不匹配
return false
}
stack = stack[:len(stack)-1] // 出栈
}
}
if len(stack) > 0 { // 还剩左括号未匹配
return false
}
return true
}
|
优化代码：哈希表，返回判断结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
func isValid(s string) bool {
hash := map[rune]rune{')': '(', ']': '[', '}': '{'}
stack := make([]rune, 0)
for _, v := range s {
if v == '(' || v == '[' || v == '{' { // 遍历到左括号
stack = append(stack, v) // 入栈
} else if len(stack) > 0 && stack[len(stack)-1] == hash[v] { // 遍历到右括号栈非空且匹配成功
stack = stack[:len(stack)-1] // 出栈
} else { // 遍历到右括号栈空或匹配不成功
return false
}
}
return len(stack) == 0
}
|
删除字符串中的所有相邻重复项
1047. 删除字符串中的所有相邻重复项 - 力扣（LeetCode）
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。在 S 上反复执行重复项删除操作，直到无法继续删除。
遍历字符串，若栈为空或与栈顶元素不同，则入栈，若与栈顶元素不同，则栈顶元素出栈，遍历结束后，将栈中元素拼接为字符串返回
1
2
3
4
5
6
7
8
9
10
11
|
func removeDuplicates(s string) string {
stack := make([]rune, 0)
for _, v := range s {
if len(stack) == 0 || stack[len(stack)-1] != v { // 栈为空或与栈顶元素不同
stack = append(stack, v) // 入栈
} else { // 栈非空且与栈顶元素相同
stack = stack[:len(stack)-1] // 出栈
}
}
return string(stack)
}
|
逆波兰表达式求值
150. 逆波兰表达式求值 - 力扣（LeetCode）
给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
注意：
- 有效的算符为
'+'、'-'、'*' 和 '/' 。
- 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
- 两个整数之间的除法总是 向零截断 。
- 表达式中不含除零运算。
- 输入是一个根据逆波兰表示法表示的算术表达式。
- 答案及所有中间计算结果可以用 32 位 整数表示。
遍历给定字符串，遇到运算符就将栈顶两个元素取出用该运算符处理，结果再入栈，遍历结束返回栈中的运算结果
注意：除法中栈顶元素是除数
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
|
func evalRPN(tokens []string) int {
stack := make([]int, 0)
for _, v := range tokens {
if v == "+" { // 遍历到运算符
val := stack[len(stack)-2] + stack[len(stack)-1] // 获取运算结果
stack = stack[:len(stack)-1] // 更新栈
stack[len(stack)-1] = val // 结果入栈
} else if v == "-" { // 遍历到运算符
val := stack[len(stack)-2] - stack[len(stack)-1] // 获取运算结果
stack = stack[:len(stack)-1] // 更新栈
stack[len(stack)-1] = val // 结果入栈
} else if v == "*" { // 遍历到运算符
val := stack[len(stack)-2] * stack[len(stack)-1] // 获取运算结果
stack = stack[:len(stack)-1] // 更新栈
stack[len(stack)-1] = val // 结果入栈
} else if v == "/" { // 遍历到运算符
val := stack[len(stack)-2] / stack[len(stack)-1] // 获取运算结果
stack = stack[:len(stack)-1] // 更新栈
stack[len(stack)-1] = val // 结果入栈
} else { // 遇到数字
val, _ := strconv.Atoi(v)
stack = append(stack, val) // 入栈
}
}
return stack[0]
}
|
压缩代码：swich
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
func evalRPN(tokens []string) int {
stack := make([]int, 0)
for _, v := range tokens {
val, err := strconv.Atoi(v) // 转为数字
if err == nil { // 说明是数字
stack = append(stack, val) // 数字入栈
} else { // 说明是运算符
switch v {
case "+": stack[len(stack)-2] = stack[len(stack)-2] + stack[len(stack)-1] // 运算结果入栈
case "-": stack[len(stack)-2] = stack[len(stack)-2] - stack[len(stack)-1] // 运算结果入栈
case "*": stack[len(stack)-2] = stack[len(stack)-2] * stack[len(stack)-1] // 运算结果入栈
case "/": stack[len(stack)-2] = stack[len(stack)-2] / stack[len(stack)-1] // 运算结果入栈
}
stack = stack[:len(stack)-1] // 更新栈
}
}
return stack[0]
}
|
滑动窗口最大值
239. 滑动窗口最大值 - 力扣（LeetCode）
给定一个数组和整数k，用k作为滑动窗口大小，窗口从最左侧移动到最右侧，每次移动一位，返回每次窗口移动后的最大值
单调队列：队首出队，队尾入队，队内元素单调；
- pop(value)：若窗口移除的元素等于单调队列的队首元素，则队列弹出元素，否则不用任何操作
- push(value)：若push的元素大于队尾元素，则弹出队尾元素，直到push的元素小于等于队尾元素或队空
保持如上规则，每次窗口移动的时候，只要取队首即可
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
|
type MyQueue struct {
queue []int
}
func Constructor() *MyQueue {
return &MyQueue{
queue: make([]int, 0),
}
}
// 获取队首元素
func (m *MyQueue) Front() int {
return m.queue[0]
}
// 获取队尾元素
func (m *MyQueue) Back() int {
return m.queue[len(m.queue)-1]
}
// 判队空
func (m *MyQueue) Empty() bool {
return len(m.queue) == 0
}
// 入队
func (m *MyQueue) Push(val int) {
for !m.Empty() && val > m.Back() { // 队非空且入队元素大于队尾元素
m.queue = m.queue[:len(m.queue)-1] // 弹出队尾元素
}
m.queue = append(m.queue, val) // 入队尾
}
// 出队
func (m *MyQueue) Pop(val int) {
if !m.Empty() && val == m.Front() { // 队非空且出队元素等于队首元素
m.queue = m.queue[1:] // 队首出队
}
}
func maxSlidingWindow(nums []int, k int) []int {
queue := Constructor()
res := make([]int, 0)
for i := 0; i < k; i++ { // 前k个元素入队
queue.Push(nums[i]) // 入队
}
res = append(res, queue.Front()) // 记录前k个元素的最大值
for i := k; i < len(nums); i++ { // 遍历数组
queue.Pop(nums[i-k]) // 滑动窗口移除最前面的元素
queue.Push(nums[i]) // 滑动窗口添加最后面的元素
res = append(res, queue.Front()) // 记录最大值
}
return res
}
|
前 K 个高频元素
347. 前 K 个高频元素 - 力扣（LeetCode）
给定一个数组和一个整数 k ，返回数组中出现频率前 k 高的元素
先统计频率，再对频率排序；统计元素出现的频率可以用map；对频率进行排序，可以用快排和堆
快排
用map统计完频率后，收集不重复的元素，利用字典值对不重复的元素排序，最后返回前k个不重复的元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
func topKFrequent(nums []int, k int) []int {
res := make([]int, 0)
mp := make(map[int]int)
for _, v := range nums { // 遍历数组
mp[v]++ // 字典值(频率)加一
}
for key := range mp { // 遍历字典key
res = append(res, key) // 记录不重复的元素
}
sort.Slice(res, func(a, b int) bool {
return mp[res[a]] > mp[res[b]] // 降序
})
return res[:k]
}
|
- 时间复杂度: O(nlogn)
- 空间复杂度: O(n)
用map统计完频率后，构建小顶堆
堆是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。 如果是父结点大于等于左右孩子那就是大顶堆，小于等于左右孩子就是小顶堆。大顶堆（堆头是最大元素），小顶堆（堆头是最小元素），用小顶堆每次将最小的元素弹出，最后小顶堆里积累的就是前k个最大元素
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
93
94
95
96
97
|
type Heap [][2]int // 二维表示元素及其频率
// 交换两个节点
func (h Heap) swap(i, j int) {
h[i], h[j] = h[j], h[i]
}
// 比较两个节点
func (h Heap) less(i, j int) bool {
return h[i][1] < h[j][1] // 比较频率 如果实现的是大顶堆，修改这里的判断即可
}
// 节点向上比较交换
func (h Heap) up(i int) {
for {
f := (i - 1) / 2 // 父节点在数组中的位置
if i == f || h.less(f, i) { // 当前节点为根节点或父节点小于当前节点
break
}
h.swap(f, i) // 交换当前节点和父节点的值
i = f // 更新当前节点索引继续向上比较
}
}
// 注意go中所有参数都是值传递 所以要让h的变化在函数外也起作用 此处要传指针
// 添加节点
func (h *Heap) Push(x [2]int) {
*h = append(*h, x) // 加入末尾
h.up(len(*h) - 1) // 向上比较交换
}
// 节点向下比较交换
func (h Heap) down(i int) {
for {
l := 2*i + 1 // 左孩子
r := 2*i + 2 // 右孩子
if l >= len(h) { // 当前节点已经是叶子节点
break
}
minChild := l // 默认左孩子值小于右孩子值
if r < len(h) && h.less(r, l) { // 右孩子存在且小于左孩子
minChild = r // 更新当前节点的最小子节点
}
if h.less(i, minChild) { // 当前节点小于最小子节点
break
}
h.swap(i, minChild) // 交换当前节点和最小子节点位置
i = minChild // 更新当前节点索引继续向下比较
}
}
// 删除堆中位置为i的节点 返回被删节点的值
func (h *Heap) Remove(i int) ([2]int, bool) {
if i < 0 || i > len(*h)-1 { // 索引越界
return [2]int{0, 0}, false
}
n := len(*h) - 1 // 最后一个节点的索引
h.swap(i, n) // 交换要被删除节点和最后的节点
x := (*h)[n] // 保存最后节点值
*h = (*h)[0:n] // 删除最后节点
h.down(i) // 被交换的当前节点向下比较交换
return x, true
}
// 弹出堆顶的元素，并返回其值
func (h *Heap) Pop() [2]int {
x, _ := h.Remove(0)
return x
}
// 根据传入的切片建堆
func BuildHeap(arr [][2]int) Heap {
h := Heap(arr) // 获取给定切片
for i := len(h)/2 - 1; i >= 0; i-- { // 从堆中末尾节点的父节点到根节点
h.down(i) // 向下比较交换
}
return h
}
func topKFrequent(nums []int, k int) []int {
mp := map[int]int{}
res := make([]int, 0)
for _, v := range nums { // 遍历数组
mp[v]++ // 字典值(频率)加一
}
h := BuildHeap([][2]int{}) // 初始化堆
for key, value := range mp { // 遍历字典
h.Push([2]int{key, value}) // 元素入堆
if len(h) > k { // 堆的节点数超过k个
h.Pop() // 删除顶点(min)
}
}
for i := 0; i < k; i++ { // 遍历堆
res = append(res, h.Pop()[0])
}
return res
}
|
- 时间复杂度: O(nlogk)
- 空间复杂度: O(n)
使用go中标准库提供的heap，需要先实现两个接口定义的五个方法：
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
|
type Heap [][2]int // 二维表示元素及其频率
func (h Heap) Len() int {
return len(h)
}
// 比较两个节点
func (h Heap) Less(i, j int) bool {
return h[i][1] < h[j][1] // 按照频率排序节点
}
// 交换两个节点
func (h Heap) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
}
// go中所有参数都是值传递 所以要让h的变化在函数外也起作用 此处要传指针
// 添加节点
func (h *Heap) Push(x interface{}) {
*h = append(*h, x.([2]int)) // 向末尾添加节点
}
// 删除节点
func (h *Heap) Pop() interface{} {
old := *h // 保存当前根
n := len(old) // 节点数
x := old[n-1] // 保存最后一个节点
*h = old[0 : n-1] // 删除最后一个节点
return x // 返回删除的节点
}
func topKFrequent(nums []int, k int) []int {
mp := map[int]int{}
res := make([]int, k)
for _, v := range nums { // 遍历数组
mp[v]++ // 字典值(频率)加一
}
h := &Heap{} // 初始化堆
heap.Init(h) // 用go标准库提供的heap
for key, value := range mp { // 遍历字典
heap.Push(h, [2]int{key, value}) // 元素入堆
if h.Len() > k { // 堆的节点数超过k个
heap.Pop(h) // 删除顶点(min)
}
}
for i := 0; i < k; i++ { // 遍历堆
res[k-i-1] = heap.Pop(h).([2]int)[0] // 将堆中排序后的元素加入结果集
}
return res
}
|
附加
最小栈
155. 最小栈 - 力扣（LeetCode）
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈
思路一：维护一个整型量保存最小值，在push和pop时更新最小值属性，若pop了最小值，则要遍历栈更新最小值（不推荐）
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
|
type MinStack struct {
minVal int
stack []int
}
func Constructor() MinStack {
return MinStack{
minVal: math.MaxInt,
stack: make([]int, 0)}
}
func (this *MinStack) Push(val int) {
this.stack = append(this.stack, val)
if val < this.minVal {
this.minVal = val
}
}
func (this *MinStack) Pop() {
if this.Top() == this.minVal {
this.minVal = math.MaxInt
for i := 0; i < len(this.stack)-1; i++ {
if this.stack[i] < this.minVal {
this.minVal = this.stack[i]
}
}
}
this.stack = this.stack[:len(this.stack)-1]
}
func (this *MinStack) Top() int {
return this.stack[len(this.stack)-1]
}
func (this *MinStack) GetMin() int {
return this.minVal
}
|
思路二：维护一个最小栈，保证栈顶一定是最小值，若push元素大于最小值，则向最小栈push最小值，pop正常。保证每次pushpop后最小栈顶一定最小
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
|
type MinStack struct {
min []int
stack []int
}
func Constructor() MinStack {
return MinStack{
min: make([]int, 0),
stack: make([]int, 0)}
}
func (this *MinStack) Push(val int) {
minVal := this.GetMin()
if val < minVal {
this.min = append(this.min, val)
} else {
this.min = append(this.min, minVal)
}
this.stack = append(this.stack, val)
}
func (this *MinStack) Pop() {
this.min = this.min[:len(this.min)-1]
this.stack = this.stack[:len(this.stack)-1]
}
func (this *MinStack) Top() int {
return this.stack[len(this.stack)-1]
}
func (this *MinStack) GetMin() int {
if len(this.min) != 0 {
return this.min[len(this.min)-1]
}
return 1 << 31 // 最小整型值
}
|
字符串解码
394. 字符串解码 - 力扣（LeetCode）
给定一个字符串，将括号里的字符重复括号前数字的次数，最终返回一个字符串
思路：遍历字符串入栈，遇到右括号时，不断弹栈，保存括号里的字符和括号前的数字，将括号里字符重复入栈给定次数
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
|
func decodeString(s string) string {
stack := make([]rune, 0)
for _, v := range s {
// 解码
if v == ']' {
temp := make([]rune, 0)
// 逆序取出括号中的字符串
for stack[len(stack)-1] != '[' {
temp = append(temp, stack[len(stack)-1])
stack = stack[:len(stack)-1]
}
// 弹出'['
stack = stack[:len(stack)-1]
// 保存重复次数(rune -> int)
countSlice := make([]rune, 0)
// 逆序取出数字
for len(stack) != 0 && stack[len(stack)-1] <= '9' && stack[len(stack)-1] >= '0' {
countSlice = append(countSlice, stack[len(stack)-1])
stack = stack[:len(stack)-1]
}
// 翻转
for i, j := 0, len(countSlice)-1; i < j; i, j = i+1, j-1 {
countSlice[i], countSlice[j] = countSlice[j], countSlice[i]
}
count, _ := strconv.Atoi(string(countSlice))
// 重复字符入栈
for range count {
// 逆序遍历括号中字符
for i := len(temp) - 1; i >= 0; i-- {
stack = append(stack, temp[i])
}
}
} else {
stack = append(stack, v)
}
}
return string(stack)
}
|
克隆图
133. 克隆图 - 力扣（LeetCode）
给定无向连通图中一个节点的引用，返回该图的深拷贝（克隆）
思路一：非递归，用栈实现（不推荐）
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
|
func cloneGraph(node *Node) *Node {
if node == nil {
return node
}
stack := make([]*Node, 0)
newStack := make([]*Node, 0)
mp := make(map[int]*Node)
temp := make(map[int]bool)
// 给定节点入栈
stack = append(stack, node)
temp[node.Val] = true
// 遍历所有旧节点创建对应新节点
for len(stack) != 0 {
// 取出一个节点作为当前节点
cur := stack[len(stack)-1]
stack = stack[:len(stack)-1]
// 将当前节点的邻居节点入栈
for _, v := range cur.Neighbors {
// 未遍历过该节点
if !temp[v.Val] {
stack = append(stack, v)
temp[v.Val] = true
}
}
// 构造当前节点的拷贝
newNode := &Node{
Val: cur.Val,
Neighbors: cur.Neighbors,
}
// 将新节点存入字典
mp[newNode.Val] = newNode
// 将新节点存入新栈
newStack = append(newStack, newNode)
}
for len(newStack) != 0 {
// 取出一个节点作为当前节点
cur := newStack[len(newStack)-1]
newStack = newStack[:len(newStack)-1]
// 保存当前节点的新邻居节点
temp := make([]*Node, 0)
// 遍历当前节点的邻居节点
for i := 0; i < len(cur.Neighbors); i++ {
// 在字典中找到对应的新节点
if v, ok := mp[cur.Neighbors[i].Val]; ok {
// 保存当前节点的新邻居节点
temp = append(temp, v)
}
}
// 修改所有邻居节点为新节点
cur.Neighbors = nil
cur.Neighbors = append(cur.Neighbors, temp...)
}
// 字典中找给定节点对应的新节点
if v, ok := mp[node.Val]; ok {
return v
}
return nil
}
|
思路二：递归
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
|
func cloneGraph(node *Node) *Node {
// 记录旧->新节点的对应
mp := make(map[*Node]*Node)
return clone(node, mp)
}
func clone(cur *Node, mp map[*Node]*Node) *Node {
if cur == nil {
return cur
}
// 字典中存在该节点对应的新节点
if v, ok := mp[cur]; ok {
return v
}
// 构建新节点
newNode := &Node{
Val: cur.Val,
Neighbors: make([]*Node, len(cur.Neighbors)),
}
// 更新字典:旧节点->新节点
mp[cur] = newNode
// 遍历当前节点的邻居节点
for i := 0; i < len(cur.Neighbors); i++ {
newNode.Neighbors[i] = clone(cur.Neighbors[i], mp)
}
return newNode
}
|
01 矩阵
542. 01 矩阵 - 力扣（LeetCode）
思路一：对每个元素BFS（超时）
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
|
func updateMatrix(mat [][]int) [][]int {
// 遍历给定矩阵
for i := 0; i < len(mat); i++ {
for j := 0; j < len(mat[0]); j++ {
// 遇到元素1
if mat[i][j] == 1 {
queue := make([][2]int, 0)
// 当前元素入队
queue = append(queue, [2]int{i, j})
// 记录距离
dist := 0
// 标记是否找到最近元素0
isFind := false
// 标记该坐标是否被遍历过
mp := make(map[[2]int]bool)
// BFS
for len(queue) != 0 && !isFind {
// 记录本层元素数
count := len(queue)
// 遍历本层所有元素
for k := 0; k < count && !isFind; k++ {
// 记录队首元素后出队
curI, curJ := queue[0][0], queue[0][1]
queue = queue[1:]
// 标记当前元素已遍历过
mp[[2]int{curI, curJ}] = true
// 找到元素0
if mat[curI][curJ] == 0 {
// 修改矩阵对应元素为距离
mat[i][j] = dist
// 标记找到最近元素0
isFind = true
}
// 上方元素入队
if curI != 0 && !mp[[2]int{curI - 1, curJ}] {
queue = append(queue, [2]int{curI - 1, curJ})
}
// 下方元素入队
if curI != len(mat)-1 && !mp[[2]int{curI + 1, curJ}] {
queue = append(queue, [2]int{curI + 1, curJ})
}
// 左方元素入队
if curJ != 0 && !mp[[2]int{curI, curJ - 1}] {
queue = append(queue, [2]int{curI, curJ - 1})
}
// 右方元素入队
if curJ != len(mat[0])-1 && !mp[[2]int{curI, curJ + 1}] {
queue = append(queue, [2]int{curI, curJ + 1})
}
}
// 距离+1
dist++
}
}
}
}
return mat
}
|
思路二BFS：更新每个元素0四周需要更新的元素，再更新每个更新过的元素四周需要更新的元素，每次都更新完一级四周需要更新的元素
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
|
func updateMatrix(mat [][]int) [][]int {
queue := make([][2]int, 0)
// 遍历给定矩阵
for i := 0; i < len(mat); i++ {
for j := 0; j < len(mat[0]); j++ {
// 遇到元素0
if mat[i][j] == 0 {
// 坐标入队
queue = append(queue, [2]int{i, j})
} else {
// 标记当前元素需要更新
mat[i][j] = -1
}
}
}
// 设置四周偏移量
ds := [4][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
// 遍历队列
for len(queue) != 0 {
// 保存队首后出队
x, y := queue[0][0], queue[0][1]
queue = queue[1:]
// 遍历当前元素的四周
for _, offset := range ds {
// 给当前元素下标设置偏移量
curX := x + offset[0]
curY := y + offset[1]
// 坐标有效且对应元素需要更新
if curX >= 0 && curY >= 0 && curX < len(mat) && curY < len(mat[0]) && mat[curX][curY] == -1 {
// 更新元素值
mat[curX][curY] = mat[x][y] + 1
// 更新后元素的下标入队
queue = append(queue, [2]int{curX, curY})
}
}
}
return mat
}
|