# Go CodeTop 题解

#### 3. 无重复字符的最长子串

[3. 无重复字符的最长子串 - 力扣（LeetCode）](https://leetcode.cn/problems/longest-substring-without-repeating-characters/)

使用滑动窗口的思想，用一个 Map 来存储目前遇到的字符。

```go
package main

import (
	"fmt"
	"math"
)

func lengthOfLongestSubstring(s string) int {
	if len(s) <= 0 {
		return 0
	}

	h := make(map[byte]int, 0)
	r, l, res := 0, 0, math.MinInt64

	for r < len(s) {
		c := s[r]
		r++
		h[c]++
		for h[c] > 1 {
			d := s[l]
			l++
			h[d]--
		}
		res = max(res, r-l)
	}
	if res == math.MinInt64 {
		return 0
	}
	return res
}

func main() {
	var s string
	fmt.Scanln(&s)
	fmt.Println(lengthOfLongestSubstring(s))
}
```

#### 206. 反转链表

[206. 反转链表 - 力扣（LeetCode）](https://leetcode.cn/problems/reverse-linked-list/)

```go
package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

func reverseList(head *ListNode) *ListNode {
	if head == nil {
		return head
	}

	a, b := head, head.Next
	for b != nil {
		t := b.Next
		b.Next = a
		a = b
		b = t
	}
	head.Next = nil
	return a
}

func main() {
	head := &ListNode{
		Val: 5,
		Next: &ListNode{
			Val: 4,
			Next: &ListNode{
				Val: 3,
				Next: &ListNode{
					Val: 2,
					Next: &ListNode{
						Val:  1,
						Next: nil,
					},
				},
			},
		},
	}
	head = reverseList(head)
	for head != nil {
		fmt.Printf("%d ", head.Val)
		head = head.Next
	}
}
// 1 2 3 4 5
```

#### 146. LRU 缓存

[146. LRU 缓存 - 力扣（LeetCode）](https://leetcode.cn/problems/lru-cache/)

```go
package main

import (
	"container/list"
	"fmt"
)

type entry struct {
	key int
	val int
}

type LRUCache struct {
	capacity int
	list     *list.List
	k2N      map[int]*list.Element
}

func (c *LRUCache) Get(key int) int {
	node := c.k2N[key]
	if node == nil {
		return -1
	}
	c.list.MoveToFront(node)
	return node.Value.(entry).val
}

func (c *LRUCache) Put(key int, value int) {
	if node := c.k2N[key]; node != nil {
		node.Value = entry{key, value}
		c.list.MoveToFront(node)
		return
	}
	c.k2N[key] = c.list.PushFront(entry{key, value})
	if len(c.k2N) > c.capacity {
		delete(c.k2N, c.list.Remove(c.list.Back()).(entry).key)
	}
}

func main() {
	lru := LRUCache{3, list.New(), map[int]*list.Element{}}
	lru.Put(1, 1)
	lru.Put(2, 1)
	lru.Put(3, 1)
	lru.Put(1, 2)
	lru.Put(4, 1)
	fmt.Println(lru.Get(4), lru.Get(1))
}
// 1 2
```

#### 215. 数组中的第 K 个最大元素

[215. 数组中的第K个最大元素 - 力扣（LeetCode）](https://leetcode.cn/problems/kth-largest-element-in-an-array/)

用快速排序完成

```go
package main

import "fmt"

func quick_sort(nums []int, l, r int) {
	if l >= r {
		return
	}
	i, j, x := l, r, nums[(l+r)/2]
	for i <= j {
		for i <= r && nums[i] < x {
			i++
		}
		for j >= l && nums[j] > x {
			j--
		}
		if i <= j {
			nums[i], nums[j] = nums[j], nums[i]
			i++
			j--
		}
	}
	quick_sort(nums, l, j)
	quick_sort(nums, i, r)
}

func main() {
	nums := []int{3, 1, 2, 4, 5}
	quick_sort(nums, 0, len(nums)-1)
	fmt.Println(nums)
}
// 1 2 3 4 5
```

#### 25. K 个一组翻转链表

[25. K 个一组翻转链表 - 力扣（LeetCode）](https://leetcode.cn/problems/reverse-nodes-in-k-group/description/)

每次调用翻转链表翻转 K 个节点，接着递归下去即可。

```go
package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

func reverseKGroup(head *ListNode, k int) *ListNode {
	if head == nil {
		return head
	}
	a, b := head, head
	for i := 0; i < k; i++ {
		if b == nil {
			return head
		}
		b = b.Next
	}
	newHead := reverseList(a, b)
	a.Next = reverseKGroup(b, k)
	return newHead
}

func reverseList(h1, h2 *ListNode) *ListNode {
	a, b := h1, h1.Next
	for b != h2 {
		t := b.Next
		b.Next = a
		a = b
		b = t
	}
	h1.Next = h2
	return a
}

func main() {
	head := &ListNode{
		Val: 5,
		Next: &ListNode{
			Val: 4,
			Next: &ListNode{
				Val: 3,
				Next: &ListNode{
					Val: 2,
					Next: &ListNode{
						Val:  1,
						Next: nil,
					},
				},
			},
		},
	}
	head = reverseKGroup(head, 2)
	for head != nil {
		fmt.Printf("%d ", head.Val)
		head = head.Next
	}
}
// 4 5 2 3 1
```

#### 15. 三数之和

[15. 三数之和 - 力扣（LeetCode）](https://leetcode.cn/problems/3sum/description/)

```go
package main

import (
	"fmt"
	"sort"
)

func threeSum(nums []int) [][]int {
	sort.Ints(nums)
	var res [][]int
	for i := 0; i < len(nums); i++ {
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		for j, k := i+1, len(nums)-1; j < k; j++ {
			if j > i+1 && nums[j] == nums[j-1] {
				continue
			}
			for j < k-1 && nums[i]+nums[j]+nums[k-1] >= 0 {
				k--
			}
			if nums[i]+nums[j]+nums[k] == 0 {
				res = append(res, []int{nums[i], nums[j], nums[k]})
			}
		}
	}
	return res
}

func main() {
	res := threeSum([]int{-1, 0, 1, 2, -1, -4})
	fmt.Println(res)
}
// [[-1 -1 2] [-1 0 1]]
```

#### 53. 最大子数组和

[53. 最大子数组和 - 力扣（LeetCode）](https://leetcode.cn/problems/maximum-subarray/description/)

用滑动窗口的思想来做，需要在第二个 for 循环之前将 res 赋值。

```go
package main

import (
	"fmt"
	"math"
)

func maxSubArray(nums []int) int {
	r, l, sum := 0, 0, 0
	res := math.MinInt
	for r < len(nums) {
		sum += nums[r]
		r++
		res = max(res, sum)
		for sum < 0 {
			sum -= nums[l]
			l++
		}
	}
	return res
}

func main() {
	res := maxSubArray([]int{-2, 1, -3, 4, -1, 2, 1, -5, 4})
	fmt.Println(res)
}
// 连续子数组 [4,-1,2,1] 的和最大，为 6
```

#### 补充题：手撕快速排序

\[912. 排序数组 - 力扣（LeetCode）]\(<https://leetcode.cn/problems/sort-an-array/description/>

```go
package main

import "fmt"

func quick_sort(nums []int, l, r int) {
	if l >= r {
		return
	}
	i, j, x := l, r, nums[(l+r)/2]
	for i <= j {
		for i <= r && nums[i] < x {
			i++
		}
		for j >= l && nums[j] > x {
			j--
		}
		if i <= j {
			nums[i], nums[j] = nums[j], nums[i]
			i++
			j--
		}
	}
	quick_sort(nums, l, j)
	quick_sort(nums, i, r)
}

func main() {
	nums := []int{3, 1, 2, 4, 5}
	quick_sort(nums, 0, len(nums)-1)
	fmt.Println(nums)
}
// 1 2 3 4 5
```

#### 21. 合并两个有序链表

[21. 合并两个有序链表 - 力扣（LeetCode）](https://leetcode.cn/problems/merge-two-sorted-lists/description/)

```go
package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
	dummy := &ListNode{}
	p := dummy
	for list1 != nil && list2 != nil {
		if list1.Val < list2.Val {
			p.Next = list1
			p = p.Next
			list1 = list1.Next
		} else {
			p.Next = list2
			p = p.Next
			list2 = list2.Next
		}
	}
	if list1 != nil {
		p.Next = list1
	}
	if list2 != nil {
		p.Next = list2
	}
	return dummy.Next
}

func main() {
	l1 := &ListNode{
		Val: 1,
		Next: &ListNode{
			Val:  3,
			Next: nil,
		},
	}
	l2 := &ListNode{
		Val: 2,
		Next: &ListNode{
			Val:  4,
			Next: nil,
		},
	}
	newList := mergeTwoLists(l1, l2)
	for newList != nil {
		fmt.Println(newList.Val)
		newList = newList.Next
	}
}
// 1 2 3 4
```

#### 1. 两数之和

[1. 两数之和 - 力扣（LeetCode）](https://leetcode.cn/problems/two-sum/description/)

```go
package main

import "fmt"

func twoSum(nums []int, target int) []int {
	m := make(map[int]int, 0)
	for i := 0; i < len(nums); i++ {
		if _, ok := m[target-nums[i]]; ok {
			return []int{i, m[target-nums[i]]}
		} else {
			m[nums[i]] = i
		}
	}
	return []int{}
}

func main() {
	fmt.Println(twoSum([]int{2, 7, 11, 15}, 9))
}
// 0 1
```

#### 5. 最长回文子串

[5. 最长回文子串 - 力扣（LeetCode）](https://leetcode.cn/problems/longest-palindromic-substring/description/)

```go
package main

import "fmt"

func longestPalindrome(s string) string {
	res := ""
	for i := 0; i < len(s); i++ {
		s1 := match(s, i, i)
		if len(s1) > len(res) {
			res = s1
		}
		s2 := match(s, i, i+1)
		if len(s2) > len(res) {
			res = s2
		}
	}
	return res
}

func match(s string, l, r int) string {
	for l >= 0 && r < len(s) && s[l] == s[r] {
		l--
		r++
	}
	return s[l+1 : r]
}

func main() {
	fmt.Println(longestPalindrome("cbbd"))
}
// bb
```

#### 102. 二叉树的层序遍历

[102. 二叉树的层序遍历 - 力扣（LeetCode）](https://leetcode.cn/problems/binary-tree-level-order-traversal/description/)

```go
package main

import "fmt"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func levelOrder(root *TreeNode) [][]int {
	res := [][]int{}
	if root == nil {
		return res
	}
	q := []*TreeNode{root}
	for len(q) > 0 {
		l := len(q)
		path := []int{}
		for i := 0; i < l; i++ {
			node := q[0]
			q = q[1:]
			path = append(path, node.Val)
			if node.Left != nil {
				q = append(q, node.Left)
			}
			if node.Right != nil {
				q = append(q, node.Right)
			}
		}
		res = append(res, path)
	}
	return res
}

func main() {
	tree := &TreeNode{
		Val: 3,
		Left: &TreeNode{
			Val: 9,
		},
		Right: &TreeNode{
			Val: 20,
			Left: &TreeNode{
				Val: 15,
			},
			Right: &TreeNode{
				Val: 7,
			},
		},
	}
	fmt.Println(levelOrder(tree))
}
// [[3] [9 20] [15 7]]
```

#### 33. 搜索旋转排序数组

[33. 搜索旋转排序数组 - 力扣（LeetCode）](https://leetcode.cn/problems/search-in-rotated-sorted-array/)

```go
package main

import "fmt"

func search(nums []int, target int) int {
	l, r := 0, len(nums)-1
	for l < r {
		mid := (l + r + 1) / 2
		if nums[mid] >= nums[0] {
			l = mid
		} else {
			r = mid - 1
		}
	}

	if target >= nums[0] {
		l = 0
	} else {
		l = r + 1
		r = len(nums) - 1
	}

	for l < r {
		mid := (l + r) / 2
		if nums[mid] >= target {
			r = mid
		} else {
			l = mid + 1
		}
	}

	if nums[r] != target {
		return -1
	}
	return r
}

func main() {
	fmt.Println(search([]int{4, 5, 6, 7, 0, 1, 2}, 0))
}
// 4
```

#### 200. 岛屿数量

[200. 岛屿数量 - 力扣（LeetCode）](https://leetcode.cn/problems/number-of-islands/)

```go
package main

import "fmt"

type Solution struct {
	dx, dy []int
	g      [][]byte
}

func numIslands(grid [][]byte) int {
	sol := Solution{
		dx: []int{0, 1, 0, -1},
		dy: []int{1, 0, -1, 0},
		g:  grid,
	}
	res := 0
	m, n := len(sol.g), len(sol.g[0])
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if sol.g[i][j] == '1' {
				sol.dfs(i, j)
				res++
			}
		}
	}
	return res
}

func (sol *Solution) dfs(x, y int) {
	sol.g[x][y] = '0'
	for i := 0; i < 4; i++ {
		a, b := x+sol.dx[i], y+sol.dy[i]
		if a >= 0 && b >= 0 && a < len(sol.g) && b < len(sol.g[0]) && sol.g[a][b] == '1' {
			sol.dfs(a, b)
		}
	}
}

func main() {
	grid := [][]byte{
		{'1', '1', '1', '1', '0'},
		{'1', '1', '0', '1', '0'},
		{'1', '1', '0', '0', '0'},
		{'0', '0', '0', '1', '0'},
	}
	fmt.Println(numIslands(grid))
}
// 2
```

#### 121. 买卖股票的最佳时机

[121. 买卖股票的最佳时机 - 力扣（LeetCode）](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/)

```go
package main

import "fmt"

func maxProfit(prices []int) int {
	dp := make([][]int, len(prices))
	for i := range dp {
		dp[i] = make([]int, 2)
	}

	dp[0][0] = 0
	dp[0][1] = -prices[0]

	for i := 1; i < len(prices); i++ {
		dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
		dp[i][1] = max(dp[i-1][1], -prices[i])
	}

	return dp[len(prices)-1][0]
}

func main() {
	fmt.Println(maxProfit([]int{7, 1, 5, 3, 6, 4}))
}
// 5
```

#### 20. 有效的括号

[20. 有效的括号 - 力扣（LeetCode）](https://leetcode.cn/problems/valid-parentheses/description/)

```go
package main

import (
	"fmt"
)

func isValid(s string) bool {
    stk := []rune{}
    for _, v := range s {
        if v == '(' || v == '[' || v == '{' {
            stk = append(stk, v)
        } else if len(stk) > 0 && math.Abs(float64(v) - float64(stk[len(stk) - 1])) < 3 {
            stk = stk[:len(stk) - 1]
        } else {
            return false
        }
    }
    return len(stk) == 0
}

func main() {
	fmt.Println(isValid("{}[]()"))
	fmt.Println(isValid("([)]"))
}
// ture false
```

#### 141. 环形链表

[141. 环形链表 - 力扣（LeetCode）](https://leetcode.cn/problems/linked-list-cycle/description/)

```go
package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

func hasCycle(head *ListNode) bool {
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		fast = fast.Next.Next
		slow = slow.Next
		if fast == slow {
			return true
		}
	}
	return false
}

func main() {
	head := &ListNode{
		Val: 3,
		Next: &ListNode{
			Val: 2,
			Next: &ListNode{
				Val: 0,
				Next: &ListNode{
					Val: -4,
				},
			},
		},
	}
	head.Next.Next.Next.Next = head.Next
	fmt.Println(hasCycle(head))
}
// true
```

#### 88. 合并两个有序数组

[88. 合并两个有序数组 - 力扣（LeetCode）](https://leetcode.cn/problems/merge-sorted-array/description/)

```go
package main

import "fmt"

func merge(nums1 []int, m int, nums2 []int, n int) {
	i, j, k := m-1, n-1, m+n-1
	for i >= 0 && j >= 0 {
		if nums1[i] < nums2[j] {
			nums1[k] = nums2[j]
			j--
		} else {
			nums1[k] = nums1[i]
			i--
		}
		k--
	}
	for j >= 0 {
		nums1[k] = nums2[j]
		j--
		k--
	}
}

func main() {
	nums1 := []int{1, 2, 3, 0, 0, 0}
	nums2 := []int{2, 5, 6}
	merge(nums1, 3, nums2, 3)
	fmt.Println(nums1)
}
// 1 2 2 3 5 6
```

#### 236. 二叉树的最近公共祖先

[236. 二叉树的最近公共祖先 - 力扣（LeetCode）](https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/)

```go
package main

import "fmt"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	if root == p || root == q || root == nil {
		return root
	}
	l := lowestCommonAncestor(root.Left, p, q)
	r := lowestCommonAncestor(root.Right, p, q)
	if l == nil {
		return r
	}
	if r == nil {
		return l
	}
	return root
}

func main() {
	root := &TreeNode{
		Val:   1,
		Left:  &TreeNode{Val: 2},
		Right: nil,
	}
	res := lowestCommonAncestor(root, root, root.Left)
	fmt.Println(res.Val)
}
// 1
```

#### 46. 全排列

[46. 全排列 - 力扣（LeetCode）](https://leetcode.cn/problems/permutations/description/)

```go
package main

import "fmt"

var (
	res  [][]int
	path []int
	st   []bool
)

func permute(nums []int) [][]int {
	res = [][]int{}
	path = []int{}
	st = make([]bool, len(nums))

	dfs(nums, 0)
	return res
}

func dfs(nums []int, u int) {
	if u == len(nums) {
		tmp := make([]int, len(path)) // 构建新的slice，避免后续操作影响已保存结果
		copy(tmp, path)
		res = append(res, tmp)
		return
	}

	for i := 0; i < len(nums); i++ {
		if !st[i] {
			st[i] = true
			path = append(path, nums[i])
			dfs(nums, u+1)
			path = path[:len(path)-1]
			st[i] = false
		}
	}
}

func main() {
	nums := []int{1, 2, 3}
	res := permute(nums)
	for _, r := range res {
		fmt.Println(r)
	}
}
// [1 2 3]
// [1 3 2]
// [2 1 3]
// [2 3 1]
// [3 1 2]
// [3 2 1]
```

#### 103. 二叉树的锯齿形层序遍历

[103. 二叉树的锯齿形层序遍历 - 力扣（LeetCode）](https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/description/)

```go
package main

import (
	"fmt"
	"slices"
)

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func zigzagLevelOrder(root *TreeNode) [][]int {
	res := [][]int{}
	if root == nil {
		return res
	}
	count := 1
	q := []*TreeNode{root}
	for len(q) > 0 {
		l := len(q)
		path := []int{}
		for i := 0; i < l; i++ {
			node := q[0]
			q = q[1:]
			path = append(path, node.Val)
			if node.Left != nil {
				q = append(q, node.Left)
			}
			if node.Right != nil {
				q = append(q, node.Right)
			}
		}
		if count%2 == 0 {
			slices.Reverse(path)
		}
		count++
		res = append(res, path)
	}
	return res
}

func main() {
	tree := &TreeNode{
		Val: 3,
		Left: &TreeNode{
			Val: 9,
		},
		Right: &TreeNode{
			Val: 20,
			Left: &TreeNode{
				Val: 15,
			},
			Right: &TreeNode{
				Val: 7,
			},
		},
	}
	fmt.Println(zigzagLevelOrder(tree))
}
// [[3] [20 9] [15 7]]
```

#### 92. 反转链表 II

[92. 反转链表 II - 力扣（LeetCode）](https://leetcode.cn/problems/reverse-linked-list-ii/description/)

```go
package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

func reverseBetween(head *ListNode, left int, right int) *ListNode {
	if head == nil {
		return head
	}
	// 创建 dummy 节点
	dummy := &ListNode{Next: head}
	p := dummy
	// 移动到反转的起点位置
	for i := 0; i < left-1; i++ {
		p = p.Next
	}
	a, b := p.Next, p.Next.Next
	// 反转链表
	for i := 0; i < right-left; i++ {
		t := b.Next
		b.Next = a
		a = b
		b = t
	}
	p.Next.Next = b
	p.Next = a
	return dummy.Next
}

func main() {
	head := &ListNode{
		Val: 5,
		Next: &ListNode{
			Val: 4,
			Next: &ListNode{
				Val: 3,
				Next: &ListNode{
					Val: 2,
					Next: &ListNode{
						Val:  1,
						Next: nil,
					},
				},
			},
		},
	}
	head = reverseBetween(head, 2, 4)
	for head != nil {
		fmt.Printf("%d ", head.Val)
		head = head.Next
	}
}
// 5 2 3 4 1
```

#### 54. 螺旋矩阵

[54. 螺旋矩阵 - 力扣（LeetCode）](https://leetcode.cn/problems/spiral-matrix/description/)

```go
package main

import "fmt"

type Solution struct {
	dx []int
	dy []int
}

func spiralOrder(matrix [][]int) []int {
	s := Solution{dx: []int{0, 1, 0, -1}, dy: []int{1, 0, -1, 0}}
	m, n := len(matrix), len(matrix[0])
	st := make([][]bool, m)
	for i := 0; i < m; i++ {
		st[i] = make([]bool, n)
	}
	res := make([]int, m*n)
	x, y, d := 0, 0, 0 // 初始位置及方向
	for i := 0; i < m*n; i++ {
		res[i] = matrix[x][y]
		st[x][y] = true
		a, b := x+s.dx[d], y+s.dy[d]
		if a < 0 || a >= m || b < 0 || b >= n || st[a][b] {
			d = (d + 1) % 4 // 改变方向
			a, b = x+s.dx[d], y+s.dy[d]
		}
		x, y = a, b
	}
	return res
}

func main() {
	res := spiralOrder([][]int{
		{1, 2, 3},
		{4, 5, 6},
		{7, 8, 9},
	})
	fmt.Println(res)
}
// [1 2 3 6 9 8 7 4 5]
```

#### 23. 合并 K 个升序链表

[23. 合并 K 个升序链表 - 力扣（LeetCode）](https://leetcode.cn/problems/merge-k-sorted-lists/description/)

```go
package main

import (
	"container/heap"
	"fmt"
)

type ListNode struct {
	Val  int
	Next *ListNode
}

type hp []*ListNode

func (h hp) Len() int           { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].Val < h[j].Val } // 最小堆
func (h hp) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any)        { *h = append(*h, v.(*ListNode)) }
func (h *hp) Pop() any          { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }

func mergeKLists(lists []*ListNode) *ListNode {
	h := hp{}
	for _, head := range lists {
		if head != nil {
			h = append(h, head)
		}
	}
	heap.Init(&h) // 堆化

	dummy := &ListNode{} // 哨兵节点，作为合并后链表头节点的前一个节点
	cur := dummy
	for len(h) > 0 {
		node := heap.Pop(&h).(*ListNode)
		if node.Next != nil {
			heap.Push(&h, node.Next)
		}
		cur.Next = node
		cur = cur.Next
	}
	return dummy.Next
}

func main() {
	lists := []*ListNode{
		{Val: 1, Next: &ListNode{Val: 4, Next: &ListNode{Val: 5}}},
		{Val: 1, Next: &ListNode{Val: 3, Next: &ListNode{Val: 4}}},
		{Val: 2, Next: &ListNode{Val: 6, Next: nil}},
	}
	res := mergeKLists(lists)
	for res != nil {
		fmt.Printf("%d ", res.Val)
		res = res.Next
	}
}
// 1 1 2 3 4 4 5 6
```

#### 160. 相交链表

[160. 相交链表 - 力扣（LeetCode）](https://leetcode.cn/problems/intersection-of-two-linked-lists/description/)

```go
package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

func getIntersectionNode(headA, headB *ListNode) *ListNode {
	a, b := headA, headB
	for a != b {
		if a != nil {
			a = a.Next
		} else {
			a = headB
		}
		if b != nil {
			b = b.Next
		} else {
			b = headA
		}
	}
	return a
}

func main() {
	a := &ListNode{
		Val: 4,
		Next: &ListNode{
			Val: 1,
			Next: &ListNode{
				Val:  8,
				Next: nil,
			},
		},
	}
	b := &ListNode{Val: 3}
	b.Next = a.Next.Next
	fmt.Println(getIntersectionNode(a, b).Val)
}
// 8
```

#### 300. 最长递增子序列

[300. 最长递增子序列 - 力扣（LeetCode）](https://leetcode.cn/problems/longest-increasing-subsequence/submissions/524569158/)

```go
package main

import "fmt"

func lengthOfLIS(nums []int) int {
	dp := make([]int, len(nums))
	for i := range dp {
		dp[i] = 1
	}
	res := 0
	for i := 0; i < len(nums); i++ {
		for j := 0; j < i; j++ {
			if nums[j] < nums[i] {
				dp[i] = max(dp[i], dp[j]+1)
			}
		}
		res = max(res, dp[i])
	}
	return res
}

func main() {
	fmt.Println(lengthOfLIS([]int{0, 1, 0, 3, 2, 3}))
}
// 4
```

#### 415. 字符串相加

[415. 字符串相加 - 力扣（LeetCode）](https://leetcode.cn/problems/add-strings/description/)

```go
package main

import (
	"fmt"
	"strconv"
)

func addStrings(num1 string, num2 string) string {
	var A, B []int

	for i := len(num1) - 1; i >= 0; i-- {
		A = append(A, int(num1[i]-'0'))
	}
	for i := len(num2) - 1; i >= 0; i-- {
		B = append(B, int(num2[i]-'0'))
	}

	C := add(A, B)

	var res string
	for i := len(C) - 1; i >= 0; i-- {
		res += strconv.Itoa(C[i])
	}
	return res
}

func add(A []int, B []int) []int {
	var C []int
	t := 0

	for i := 0; i < len(A) || i < len(B) || t > 0; i++ {
		if i < len(A) {
			t += A[i]
		}
		if i < len(B) {
			t += B[i]
		}
		C = append(C, t%10)
		t /= 10
	}
	return C
}

func main() {
	fmt.Println(addStrings("123", "456"))
}
// 579
```

#### 143. 重排链表

[143. 重排链表 - 力扣（LeetCode）](https://leetcode.cn/problems/reorder-list/description/)

```go
package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

func reorderList(head *ListNode) {
	if head == nil {
		return
	}
	mid := findMid(head)
	l1, l2 := head, mid.Next
	mid.Next = nil
	l2 = reverseList(l2)
	merge(l1, l2)
}

func findMid(head *ListNode) *ListNode {
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}
	return slow
}

func reverseList(head *ListNode) *ListNode {
	if head == nil {
		return head
	}
	a, b := head, head.Next
	for b != nil {
		t := b.Next
		b.Next = a
		a = b
		b = t
	}
	head.Next = nil
	return a
}

func merge(l1 *ListNode, l2 *ListNode) {
	for l1 != nil && l2 != nil {
		t1 := l1.Next
		t2 := l2.Next
		l1.Next = l2
		l1 = t1
		l2.Next = l1
		l2 = t2
	}
}

func main() {
	head := &ListNode{Val: 1, Next: &ListNode{Val: 2, Next: &ListNode{Val: 3, Next: &ListNode{Val: 4, Next: nil}}}}
	reorderList(head)
	for head != nil {
		fmt.Printf("%d ", head.Val)
		head = head.Next
	}
}
// 1 4 2 3
```

#### 42. 接雨水

[42. 接雨水 - 力扣（LeetCode）](https://leetcode.cn/problems/trapping-rain-water/description/)

```go
package main

import "fmt"

func trap(height []int) int {
	lh, rh, res, l, r := 0, 0, 0, 0, len(height)-1
	for l < r {
		lh = max(lh, height[l])
		rh = max(rh, height[r])
		if lh < rh {
			res += lh - height[l]
			l++
		} else {
			res += rh - height[r]
			r--
		}
	}
	return res
}

func main() {
	fmt.Println(trap([]int{4, 2, 0, 3, 2, 5}))
}
// 9
```

#### 142. 环形链表 II

[142. 环形链表 II - 力扣（LeetCode）](https://leetcode.cn/problems/linked-list-cycle-ii/)

```go
package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

func detectCycle(head *ListNode) *ListNode {
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		fast = fast.Next.Next
		slow = slow.Next
		if slow == fast {
			break
		}
	}
	if fast == nil || fast.Next == nil {
		return nil
	}
	slow = head
	for slow != fast {
		slow = slow.Next
		fast = fast.Next
	}
	return slow
}

func main() {
	head := &ListNode{Val: 1, Next: &ListNode{Val: 2}}
	head.Next.Next = head
	fmt.Println(detectCycle(head).Val)
}
// 1
```

#### 56. 合并区间

[56. 合并区间 - 力扣（LeetCode）](https://leetcode.cn/problems/merge-intervals/description/)

```go
package main

import (
	"fmt"
	"sort"
)

func merge(intervals [][]int) (res [][]int) {
	sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] })
	for i := 0; i < len(intervals); i++ {
		if len(res) == 0 || res[len(res)-1][1] < intervals[i][0] {
			res = append(res, intervals[i])
		} else {
			res[len(res)-1][1] = max(res[len(res)-1][1], intervals[i][1])
		}
	}
	return
}

func main() {
	fmt.Println(merge([][]int{
		{1, 3},
		{2, 6},
		{8, 10},
		{15, 18},
	}))
}
// [[1 6] [8 10] [15 18]]
```

#### 124. 二叉树中的最大路径和

[124. 二叉树中的最大路径和 - 力扣（LeetCode）](https://leetcode.cn/problems/binary-tree-maximum-path-sum/description/)

```go
package main

import (
	"fmt"
	"math"
)

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

var res int

func maxPathSum(root *TreeNode) int {
	res = math.MinInt
	dfs(root)
	return res
}

func dfs(root *TreeNode) int {
	if root == nil {
		return 0
	}
	l := max(0, dfs(root.Left))
	r := max(0, dfs(root.Right))
	res = max(res, l+r+root.Val)
	return max(l, r) + root.Val
}

func main() {
	root := &TreeNode{
		Val:   1,
		Left:  &TreeNode{Val: 2},
		Right: &TreeNode{Val: 3},
	}
	fmt.Println(maxPathSum(root))
}
// 6
```

#### 72. 编辑距离

[72. 编辑距离 - 力扣（LeetCode）](https://leetcode.cn/problems/edit-distance/)

```go
package main

import "fmt"

func minDistance(word1, word2 string) int {
	m, n := len(word1), len(word2)
	memo := make([][]int, m+1)
	for i := range memo {
		memo[i] = make([]int, n+1)
		for j := range memo[i] {
			memo[i][j] = -1
		}
	}
	return dp(word1, m-1, word2, n-1, memo)
}

func dp(word1 string, m int, word2 string, n int, memo [][]int) int {
	if m == -1 {
		return n + 1
	}
	if n == -1 {
		return m + 1
	}
	if memo[m][n] != -1 {
		return memo[m][n]
	}
	if word1[m] == word2[n] {
		memo[m][n] = dp(word1, m-1, word2, n-1, memo)
	} else {
		memo[m][n] = min(dp(word1, m-1, word2, n-1, memo)+1, min(dp(word1, m-1, word2, n, memo)+1, dp(word1, m, word2, n-1, memo)+1))
	}
	return memo[m][n]
}

func main() {
	fmt.Println(minDistance("horse", "ros"))
}
// 3
```

#### 19. 删除链表的倒数第 N 个结点

[19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）](https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/)

```go
package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

func removeNthFromEnd(head *ListNode, n int) *ListNode {
	if head == nil {
		return nil
	}
	dummy := &ListNode{Next: head}
	p, q := dummy, dummy
	for i := 0; i < n+1; i++ {
		p = p.Next
	}
	for p != nil {
		p = p.Next
		q = q.Next
	}
	q.Next = q.Next.Next
	return dummy.Next
}

func main() {
	head := &ListNode{Val: 1, Next: &ListNode{Val: 2, Next: &ListNode{Val: 3, Next: &ListNode{Val: 4, Next: &ListNode{Val: 5, Next: nil}}}}}
	removeNthFromEnd(head, 2)
	for head != nil {
		fmt.Printf("%d ", head.Val)
		head = head.Next
	}
}
// 1 2 3 5
```

#### 93. 复原 IP 地址

[93. 复原 IP 地址 - 力扣（LeetCode）](https://leetcode.cn/problems/restore-ip-addresses/description/)

```go
package main

import (
	"fmt"
	"strconv"
	"strings"
)

var res []string

func restoreIpAddresses(s string) []string {
	res = []string{}
	dfs(s, 0, 0, "")
	return res
}

func dfs(s string, u int, k int, path string) {
	if u == len(s) {
		if k == 4 {
			path = strings.TrimSuffix(path, ".")
			res = append(res, path)
		}
		return
	}
	if k == 4 {
		return
	}

	t := 0
	for i := u; i < len(s); i++ {
		if i > u && s[u] == '0' {
			break
		}
		t = t*10 + int(s[i]-'0')
		if t > 255 {
			break
		}
		dfs(s, i+1, k+1, path+strconv.Itoa(t)+".")
	}
	return
}

func main() {
	fmt.Println(restoreIpAddresses("25525511135"))
}
// [255.255.11.135 255.255.111.35]
```

#### 1143. 最长公共子序列

[1143. 最长公共子序列 - 力扣（LeetCode）](https://leetcode.cn/problems/longest-common-subsequence/description/)

```go
package main

import (
	"fmt"
)

func longestCommonSubsequence(text1 string, text2 string) int {
	m, n := len(text1), len(text2)
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}
	res := 0
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if text1[i-1] == text2[j-1] {
				dp[i][j] = dp[i-1][j-1] + 1
			} else {
				dp[i][j] = max(dp[i-1][j], dp[i][j-1])
			}
			res = max(res, dp[i][j])
		}
	}
	return res
}

func main() {
	fmt.Println(longestCommonSubsequence("abcde", "ace"))
}
// 3
```

#### 94. 二叉树的中序遍历

[94. 二叉树的中序遍历 - 力扣（LeetCode）](https://leetcode.cn/problems/binary-tree-inorder-traversal/description/)

```go
package main

import "fmt"

type TreeNode struct {
	Val         int
	Left, Right *TreeNode
}

func inorderTraversal(root *TreeNode) []int {
	var res []int
	var stack []*TreeNode

	for root != nil || len(stack) > 0 {
		for root != nil {
			stack = append(stack, root)
			root = root.Left
		}
		index := len(stack) - 1 // 栈顶
		root = stack[index]
		stack = stack[:index] // 出栈

		res = append(res, root.Val)
		root = root.Right
	}
	return res
}
func main() {
	root := &TreeNode{Val: 1, Left: nil, Right: &TreeNode{Val: 2, Left: &TreeNode{Val: 3}}}
	fmt.Println(inorderTraversal(root))
}
// 1 3 2
```

#### 82. 删除排序链表中的重复元素 II

[82. 删除排序链表中的重复元素 II - 力扣（LeetCode）](https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/description/)

```go
package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

func deleteDuplicates(head *ListNode) *ListNode {
	if head == nil {
		return head
	}
	dummy := &ListNode{Next: head}
	p := dummy
	for p.Next != nil {
		q := p.Next.Next
		for q != nil && q.Val == p.Next.Val {
			q = q.Next
		}
		if q == p.Next.Next {
			p = p.Next
		}
		p.Next = q
	}
	return dummy.Next
}

func main() {
	head := &ListNode{Val: 1, Next: &ListNode{Val: 2, Next: &ListNode{Val: 3, Next: &ListNode{Val: 3, Next: &ListNode{Val: 4, Next: &ListNode{Val: 4, Next: &ListNode{Val: 5, Next: nil}}}}}}}
	res := deleteDuplicates(head)
	for res != nil {
		fmt.Printf("%d ", res.Val)
		res = res.Next
	}
}
// 1 2 5
```

#### 199. 二叉树的右视图

[199. 二叉树的右视图 - 力扣（LeetCode）](https://leetcode.cn/problems/binary-tree-right-side-view/description/)

```go
package main

import "fmt"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func rightSideView(root *TreeNode) []int {
	res := []int{}
	if root == nil {
		return res
	}
	q := []*TreeNode{root}
	for len(q) > 0 {
		l := len(q)
		for i := 0; i < l; i++ {
			node := q[0]
			q = q[1:]
			if node.Left != nil {
				q = append(q, node.Left)
			}
			if node.Right != nil {
				q = append(q, node.Right)
			}
			if i == l-1 {
				res = append(res, node.Val)
			}
		}
	}
	return res
}

func main() {
	tree := &TreeNode{
		Val: 3,
		Left: &TreeNode{
			Val: 9,
		},
		Right: &TreeNode{
			Val: 20,
			Left: &TreeNode{
				Val: 15,
			},
			Right: &TreeNode{
				Val: 7,
			},
		},
	}
	fmt.Println(rightSideView(tree))
}
// 3 20 7
```

#### 704. 二分查找

[704. 二分查找 - 力扣（LeetCode）](https://leetcode.cn/problems/binary-search/description/)

```go
package main

import "fmt"

func search(nums []int, target int) int {
	l, r := 0, len(nums)-1
	for l < r {
		mid := (l + r) / 2
		if nums[mid] >= target {
			r = mid
		} else {
			l = mid + 1
		}
	}
	if nums[r] != target {
		return -1
	}
	return r
}

func main() {
	fmt.Println(search([]int{-1, 0, 3, 5, 9, 12}, 9))
}
// 4
```

#### 232. 用栈实现队列

[232. 用栈实现队列 - 力扣（LeetCode）](https://leetcode.cn/problems/implement-queue-using-stacks/description/)

```go
package main

import "fmt"

type MyQueue struct {
	stk1 []int
	stk2 []int
}

func Constructor() MyQueue {
	return MyQueue{[]int{}, []int{}}
}

func (this *MyQueue) Push(x int) {
	this.stk1 = append(this.stk1, x)
}

func (this *MyQueue) Pop() int {
	this.move()
	ans := this.stk2[len(this.stk2)-1]
	this.stk2 = this.stk2[:len(this.stk2)-1]
	return ans
}

func (this *MyQueue) Peek() int {
	this.move()
	return this.stk2[len(this.stk2)-1]
}

func (this *MyQueue) Empty() bool {
	return len(this.stk1) == 0 && len(this.stk2) == 0
}

func (this *MyQueue) move() {
	if len(this.stk2) == 0 {
		for len(this.stk1) > 0 {
			this.stk2 = append(this.stk2, this.stk1[len(this.stk1)-1])
			this.stk1 = this.stk1[:len(this.stk1)-1]
		}
	}
}

func main() {
	obj := Constructor()
	obj.Push(2)
	obj.Push(3)
	fmt.Println(obj.Peek())
	obj.Pop()
	fmt.Println(obj.Peek())
}
// 2 3
```

#### 4. 寻找两个正序数组的中位数

[4. 寻找两个正序数组的中位数 - 力扣（LeetCode）](https://leetcode.cn/problems/median-of-two-sorted-arrays/)

```go
package main

import "fmt"

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	i, j, k, pre, cur := 0, 0, 0, 0, 0
	n1, n2 := len(nums1), len(nums2)
	m := n1 + n2
	mid := m / 2
	for k <= mid {
		pre = cur
		if i < n1 && j < n2 {
			if nums1[i] < nums2[j] {
				cur = nums1[i]
				i++
			} else {
				cur = nums2[j]
				j++
			}
		} else if i < n1 {
			cur = nums1[i]
			i++
		} else {
			cur = nums2[j]
			j++
		}
		k++
	}
	if m%2 == 0 {
		return float64(pre+cur) / 2
	}
	return float64(cur)
}

func main() {
	fmt.Println(findMedianSortedArrays([]int{1, 3}, []int{2}))
}
// 2
```

#### 148. 排序链表

[148. 排序链表 - 力扣（LeetCode）](https://leetcode.cn/problems/sort-list/description/)

```go
package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

func sortList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	slow, fast := head, head
	var preS *ListNode
	for fast != nil && fast.Next != nil {
		fast = fast.Next.Next
		preS = slow
		slow = slow.Next
	}
	preS.Next = nil
	l, r := sortList(head), sortList(slow)
	return merge(l, r)
}

func merge(l *ListNode, r *ListNode) *ListNode {
	dummy := &ListNode{}
	p := dummy
	for l != nil && r != nil {
		if l.Val < r.Val {
			p.Next = l
			p = p.Next
			l = l.Next
		} else {
			p.Next = r
			p = p.Next
			r = r.Next
		}
	}
	if l != nil {
		p.Next = l
	}
	if r != nil {
		p.Next = r
	}
	return dummy.Next
}

func main() {
	head := &ListNode{Val: 4, Next: &ListNode{Val: 2, Next: &ListNode{Val: 1, Next: &ListNode{Val: 3, Next: nil}}}}
	res := sortList(head)
	for res != nil {
		fmt.Printf("%d ", res.Val)
		res = res.Next
	}
}
// 1 2 3 4
```

#### 69. x 的平方根

[69. x 的平方根 - 力扣（LeetCode）](https://leetcode.cn/problems/sqrtx/description/)

```go
package main

import "fmt"

func mySqrt(x int) int {
	l, r := 0, x
	for l < r {
		mid := (l + r + 1) / 2
		if x >= mid*mid {
			l = mid
		} else {
			r = mid - 1
		}
	}
	return r
}

func main() {
	fmt.Println(mySqrt(4))
}
// 2
```

#### 8. 字符串转换整数

[8. 字符串转换整数 (atoi) - 力扣（LeetCode）](https://leetcode.cn/problems/string-to-integer-atoi/description/)

```go
// 简易版本 未截断i32
func myAtoi(s string) int {
	res, flag, i := 0, 1, 0
	for s[i] == ' ' {
		i ++
	}
	if s[i] == '-' {
		flag = -1
		i ++
	} else if s[i] == '+' {
		i ++
	}
	for i < len(s) && s[i] >= '0' && s[i] <= '9' {
		res = res * 10 + int(s[i] - '0')
		i ++
	}
	return res * flag
}
// AC 版本
func myAtoi(s string) int {
    res, flag, i := 0, 1, 0
    for i < len(s) && s[i] == ' ' {
        i ++
    }
    if i < len(s) && s[i] == '-' {
        flag = -1
        i ++
    } else if i < len(s) && s[i] == '+' {
        i ++
    }
    for i < len(s) && s[i] >= '0' && s[i] <= '9' {
        if res > (1<<31 - 1 - int(s[i]-'0')) / 10 {
            if flag == -1 {
                return -1 << 31
            }
            return 1<<31 - 1
        }
        res = res * 10 + int(s[i] - '0')
        i ++
    }
    return res * flag
}
```

#### 31. 下一个排列

[31. 下一个排列 - 力扣（LeetCode）](https://leetcode.cn/problems/next-permutation/description/)

```go
package main

import (
	"fmt"
	"slices"
)

func nextPermutation(nums []int) {
	n := len(nums) - 1
	for n > 0 && nums[n] <= nums[n-1] {
		n--
	}
	if n == 0 {
		slices.Reverse(nums)
	} else {
		t := n
		for t < len(nums) && nums[t] > nums[n-1] {
			t++
		}
		nums[n-1], nums[t-1] = nums[t-1], nums[n-1]
		slices.Reverse(nums[n:])
	}
}

func main() {
	s := []int{1, 2, 3}
	nextPermutation(s)
	fmt.Println(s)
}
// 1 3 2
```

#### 22. 括号生成

[22. 括号生成 - 力扣（LeetCode）](https://leetcode.cn/problems/generate-parentheses/description/)

```go
package main

import "fmt"

var (
	result []string
	path   string
)

func generateParenthesis(n int) []string {
	result = make([]string, 0)
	path = ""
	dfs(n, n)
	return result
}

func dfs(l, r int) {
	if l < 0 || r < 0 || l > r {
		return
	}
	if l == 0 && r == 0 {
		result = append(result, path)
		return
	}

	path = path + "("
	dfs(l-1, r)
	path = path[:len(path)-1]

	path = path + ")"
	dfs(l, r-1)
	path = path[:len(path)-1]
}

func main() {
	fmt.Println(generateParenthesis(2))
}
// [(()) ()()]
```

#### 2. 两数相加

[2. 两数相加 - 力扣（LeetCode）](https://leetcode.cn/problems/add-two-numbers/description/)

```go
package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	dummy := &ListNode{}
	p := dummy
	t := 0
	for t != 0 || l1 != nil || l2 != nil {
		if l1 != nil {
			t += l1.Val
			l1 = l1.Next
		}
		if l2 != nil {
			t += l2.Val
			l2 = l2.Next
		}
		p.Next = &ListNode{Val: t % 10}
		p = p.Next
		t /= 10
	}
	return dummy.Next
}

func main() {
	l1 := &ListNode{1, &ListNode{3, nil}}
	l2 := &ListNode{2, &ListNode{3, nil}}
	res := addTwoNumbers(l1, l2)
	for res != nil {
		fmt.Printf("%d", res.Val)
		res = res.Next
	}
}
// 36
```

#### 70. 爬楼梯

[70. 爬楼梯 - 力扣（LeetCode）](https://leetcode.cn/problems/climbing-stairs/description/)

```go
package main

import "fmt"

var memo []int

func climbStairs(n int) int {
	memo = make([]int, n+1)
	for i := range memo {
		memo[i] = -1
	}
	return dp(n)
}

func dp(n int) int {
	if n == 1 || n == 2 {
		return n
	}
	if memo[n] != -1 {
		return memo[n]
	}
	memo[n] = dp(n-1) + dp(n-2)
	return memo[n]
}

func main() {
	fmt.Println(climbStairs(3))
}
// 3
```

#### 165. 比较版本号

[165. 比较版本号 - 力扣（LeetCode）](https://leetcode.cn/problems/compare-version-numbers/)

```go
package main

import (
	"fmt"
	"strconv"
	"strings"
)

func compareVersion(version1 string, version2 string) int {
	s1 := strings.Split(version1, ".")
	s2 := strings.Split(version2, ".")

	for i := 0; i < len(s1) || i < len(s2); i++ {
		v1, v2 := 0, 0
		if i < len(s1) {
			v1, _ = strconv.Atoi(s1[i])
		}
		if i < len(s2) {
			v2, _ = strconv.Atoi(s2[i])
		}
		if v1 > v2 {
			return 1
		}
		if v1 < v2 {
			return -1
		}
	}
	return 0
}

func main() {
	fmt.Println(compareVersion("1.1", "0.1"))
}
// 1
```

#### 239. 滑动窗口最大值

[239. 滑动窗口最大值 - 力扣（LeetCode）](https://leetcode.cn/problems/sliding-window-maximum/)

```go
package main

import (
	"fmt"
)

func maxSlidingWindow(nums []int, k int) []int {
	ans := make([]int, 0, len(nums)-k+1) // 预先分配好空间
	q := []int{}
	for i, x := range nums {
		for len(q) > 0 && nums[q[len(q)-1]] <= x {
			q = q[:len(q)-1] // 维护 q 的单调性
		}
		q = append(q, i) // 入队
		if i-q[0] >= k { // 队首已经离开窗口了
			q = q[1:]
		}
		if i >= k-1 {
			ans = append(ans, nums[q[0]])
		}
	}
	return ans
}

func main() {
	fmt.Println(maxSlidingWindow([]int{1, 3, -1, -3, 5, 3, 6, 7}, 3))
}
// 3 3 5 5 6 7
```

#### 41. 缺失的第一个正数

[41. 缺失的第一个正数 - 力扣（LeetCode）](https://leetcode.cn/problems/first-missing-positive/)

```go
package main

import (
	"fmt"
)

func firstMissingPositive(nums []int) int {
	n := len(nums)
	for i := 0; i < n; i++ {
		for nums[i] > 0 && nums[i] <= n && nums[nums[i]-1] != nums[i] {
			nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]
		}
	}
	for i := 0; i < n; i++ {
		if nums[i] != i+1 {
			return i + 1
		}
	}
	return n + 1
}

func main() {
	fmt.Println(firstMissingPositive([]int{3, 4, -1, 1}))
}
// 2
```

#### 322. 零钱兑换

[322. 零钱兑换 - 力扣（LeetCode）](https://leetcode.cn/problems/coin-change/description/)

```go
package main

import (
	"fmt"
)

func coinChange(coins []int, amount int) int {
	dp := make([]int, amount+1)
	for i := range dp {
		dp[i] = amount + 1
	}
	dp[0] = 0
	for i := 1; i < len(dp); i++ {
		for _, coin := range coins {
			if i >= coin {
				dp[i] = min(dp[i], dp[i-coin]+1)
			}
		}
	}
	if dp[amount] == amount+1 {
		return -1
	}
	return dp[amount]
}

func main() {
	fmt.Println(coinChange([]int{1, 2, 5}, 11))
}
// 3
```

#### 76. 最小覆盖子串

[76. 最小覆盖子串 - 力扣（LeetCode）](https://leetcode.cn/problems/minimum-window-substring/description/)

```go
package main

import (
	"fmt"
	"math"
)

func minWindow(s string, t string) string {
	win, need := map[rune]int{}, map[rune]int{}
	for _, c := range t {
		need[c]++
	}
	l, r, st, vl, length := 0, 0, 0, 0, math.MaxInt
	for r < len(s) {
		c := rune(s[r])
		r++
		if _, ok := need[c]; ok {
			win[c]++
			if win[c] == need[c] {
				vl++
			}
		}
		for vl == len(need) {
			if r-l < length {
				st = l
				length = r - l
			}
			d := rune(s[l])
			l++
			if _, ok := need[d]; ok {
				if win[d] == need[d] {
					vl--
				}
				win[d]--
			}
		}
	}

	if length == math.MaxInt {
		return ""
	}
	return s[st : st+length]
}

func main() {
	fmt.Println(minWindow("ADOBECODEBANC", "ABC"))
}
// BANC
```

#### 78. 子集

[78. 子集 - 力扣（LeetCode）](https://leetcode.cn/problems/subsets/description/)

```go
package main

import (
	"fmt"
)

var (
	res  [][]int
	path []int
)

func subsets(nums []int) [][]int {
	res = [][]int{}
	dfs(nums, 0)
	return res
}

func dfs(nums []int, u int) {
	if u == len(nums) {
		temp := make([]int, len(path))
		copy(temp, path)
		res = append(res, temp)
		return
	}

	dfs(nums, u+1)
	path = append(path, nums[u])
	dfs(nums, u+1)
	path = path[:len(path)-1]
}

func main() {
	fmt.Println(subsets([]int{1, 2, 3}))
}
// [[] [3] [2] [2 3] [1] [1 3] [1 2] [1 2 3]]
```

#### 105. 从前序与中序遍历序列构造二叉树

[105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）](https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/)

```go
func buildTree(preorder []int, inorder []int) *TreeNode {
	return dfs(preorder, 0, len(preorder)-1, inorder, 0, len(inorder)-1)
}

func dfs(preorder []int, pst int, ped int, inorder []int, ist int, ied int) *TreeNode {
	if pst > ped {
		return nil
	}
	val := preorder[pst]
	var idx int
	root := &TreeNode{Val: val}
	for i := ist; i <= ied; i++ {
		if inorder[i] == val {
			idx = i
			break
		}
	}
	root.Left = dfs(preorder, pst+1, pst+idx-ist, inorder, ist, idx-1)
	root.Right = dfs(preorder, pst+idx-ist+1, ped, inorder, idx+1, ied)
	return root
}
```

#### 155. 最小栈

[155. 最小栈 - 力扣（LeetCode）](https://leetcode.cn/problems/min-stack/description/)

```go
package main

import (
	"fmt"
	"math"
)

type MinStack struct {
	stk, minS []int
}

func Constructor() MinStack {
	return MinStack{stk: []int{}, minS: []int{math.MaxInt}}
}

func (s *MinStack) Push(val int) {
	s.stk = append(s.stk, val)
	s.minS = append(s.minS, min(val, s.minS[len(s.minS)-1]))
}

func (s *MinStack) Pop() {
	s.stk = s.stk[:len(s.stk)-1]
	s.minS = s.minS[:len(s.minS)-1]
}

func (s *MinStack) Top() int {
	return s.stk[len(s.stk)-1]
}

func (s *MinStack) GetMin() int {
	return s.minS[len(s.minS)-1]
}

func main() {
	obj := Constructor()
	obj.Push(11)
	obj.Push(2)
	fmt.Println(obj.GetMin())
}
// 2
```

#### 32. 最长有效括号

[32. 最长有效括号 - 力扣（LeetCode）](https://leetcode.cn/problems/longest-valid-parentheses/description/)

```go
package main

import "fmt"

func longestValidParentheses(s string) int {
	var stack []int
	dp := make([]int, len(s)+1)
	max := 0
	for i := 0; i < len(s); i++ {
		if string(s[i]) == "(" {
			stack = append(stack, i)
		} else {
			if len(stack) == 0 {
				continue
			} else {
				lidx := stack[len(stack)-1]
				stack = stack[:len(stack)-1]
				dp[i+1] = i + 1 - lidx + dp[lidx]
			}
		}
		if dp[i+1] > max {
			max = dp[i+1]
		}
	}
	return max
}

func main() {
	fmt.Println(longestValidParentheses(")()())"))
}
// 4
```

#### 43. 字符串相乘

[43. 字符串相乘 - 力扣（LeetCode）](https://leetcode.cn/problems/multiply-strings/description/)

```go
package main

import (
	"fmt"
	"strconv"
)

func multiply(num1 string, num2 string) string {
	if num1 == "0" || num2 == "0" {
		return "0"
	}
	m, n := len(num1), len(num2)
	res := make([]int, m+n)

	for i := m - 1; i >= 0; i-- {
		for j := n - 1; j >= 0; j-- {
			mul := int(num1[i]-'0') * int(num2[j]-'0')
			r1, r2 := i+j, i+j+1
			sum := mul + res[r2]
			res[r1] += sum / 10
			res[r2] = sum % 10
		}
	}

	for i := 0; i < len(res); i++ {
		if res[i] != 0 {
			res = res[i:]
			break
		}
	}
	var result string
	for _, v := range res {
		result += strconv.Itoa(v)
	}
	return result
}

func main() {
	fmt.Println(multiply("12", "13"))
}
// 156
```

#### 151. 反转字符串中的单词

[151. 反转字符串中的单词 - 力扣（LeetCode）](https://leetcode.cn/problems/reverse-words-in-a-string/description/)

```go
package main

import (
	"fmt"
	"strings"
)

func reverseWords(s string) string {
	words := strings.Fields(s)
	for i := 0; i < len(words)/2; i++ {
		words[i], words[len(words)-1-i] = words[len(words)-1-i], words[i]
	}
	res := strings.Join(words, " ")
	return res
}

func main() {
	fmt.Println(reverseWords("the sky is blue"))
}
// blue is sky the
```

#### 129. 求根节点到叶节点数字之和

[129. 求根节点到叶节点数字之和 - 力扣（LeetCode）](https://leetcode.cn/problems/sum-root-to-leaf-numbers/)

```go
package main

import "fmt"

type TreeNode struct {
	Val         int
	Left, Right *TreeNode
}

var res int

func sumNumbers(root *TreeNode) int {
	res = 0
	dfs(root, 0)
	return res
}

func dfs(root *TreeNode, sum int) {
	if root == nil {
		return
	}
	sum = sum*10 + root.Val
	if root.Left == nil && root.Right == nil {
		res += sum
		return
	}
	dfs(root.Left, sum)
	dfs(root.Right, sum)
}

func main() {
	root := &TreeNode{
		Val:   1,
		Left:  &TreeNode{Val: 2},
		Right: &TreeNode{Val: 3},
	}
	fmt.Println(sumNumbers(root))
}
// 25
```

#### 104. 二叉树的最大深度

[104. 二叉树的最大深度 - 力扣（LeetCode）](https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/)

```go
package main

import "fmt"

type TreeNode struct {
	Val         int
	Left, Right *TreeNode
}

func maxDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	l := maxDepth(root.Left)
	r := maxDepth(root.Right)
	return max(l, r) + 1
}

func main() {
	root := &TreeNode{
		Val:   1,
		Left:  &TreeNode{Val: 2},
		Right: &TreeNode{Val: 3},
	}
	fmt.Println(maxDepth(root))
}
// 2
```

#### 101. 对称二叉树

[101. 对称二叉树 - 力扣（LeetCode）](https://leetcode.cn/problems/symmetric-tree/description/)

```go
package main

import "fmt"

type TreeNode struct {
	Val         int
	Left, Right *TreeNode
}

func isSymmetric(root *TreeNode) bool {
	return dfs(root.Left, root.Right)
}

func dfs(left, right *TreeNode) bool {
	if left == nil && right == nil {
		return true
	}
	if left == nil || right == nil {
		return false
	}
	if left.Val != right.Val {
		return false
	}
	return dfs(left.Left, right.Right) && dfs(left.Right, right.Left)
}

func main() {
	root := &TreeNode{
		Val:   1,
		Left:  &TreeNode{Val: 2},
		Right: &TreeNode{Val: 2},
	}
	fmt.Println(isSymmetric(root))
}
// true
```

#### 144. 二叉树的前序遍历

[144. 二叉树的前序遍历 - 力扣（LeetCode）](https://leetcode.cn/problems/binary-tree-preorder-traversal/description/)

```go
package main

import "fmt"

type TreeNode struct {
	Val         int
	Left, Right *TreeNode
}

func preorderTraversal(root *TreeNode) []int {
	var res []int
	var stack []*TreeNode

	for root != nil || len(stack) > 0 {
		for root != nil {
			stack = append(stack, root)
			res = append(res, root.Val)
			root = root.Left
		}
		index := len(stack) - 1 // 栈顶
		root = stack[index]
		stack = stack[:index] // 出栈
		root = root.Right
	}
	return res
}

func main() {
	root := &TreeNode{Val: 1, Left: nil, Right: &TreeNode{Val: 2, Left: &TreeNode{Val: 3}}}
	fmt.Println(preorderTraversal(root))
}
// 1 2 3
```

#### 543. 二叉树的直径

[543. 二叉树的直径 - 力扣（LeetCode）](https://leetcode.cn/problems/diameter-of-binary-tree/description/)

```go
package main

import "fmt"

type TreeNode struct {
	Val         int
	Left, Right *TreeNode
}

var res int

func diameterOfBinaryTree(root *TreeNode) int {
	res = 0
	dfs(root)
	return res
}

func dfs(root *TreeNode) {
	if root == nil {
		return
	}
	l := maxD(root.Left)
	r := maxD(root.Right)
	res = max(res, l+r)
	dfs(root.Left)
	dfs(root.Right)
}

func maxD(root *TreeNode) int {
	if root == nil {
		return 0
	}
	l := maxD(root.Left)
	r := maxD(root.Right)
	return max(l, r) + 1
}

func main() {
	root := &TreeNode{Val: 1, Left: nil, Right: &TreeNode{Val: 2, Left: &TreeNode{Val: 3}}}
	fmt.Println(diameterOfBinaryTree(root))
}
// 2
```

#### 98. 验证二叉搜索树

[98. 验证二叉搜索树 - 力扣（LeetCode）](https://leetcode.cn/problems/validate-binary-search-tree/description/)

```go
package main

import "fmt"

type TreeNode struct {
	Val         int
	Left, Right *TreeNode
}

func isValidBST(root *TreeNode) bool {
	return dfs(root, nil, nil)
}

func dfs(root, min, max *TreeNode) bool {
	if root == nil {
		return true
	}
	if max != nil && max.Val <= root.Val || min != nil && min.Val >= root.Val {
		return false
	}
	return dfs(root.Left, min, root) && dfs(root.Right, root, max)
}

func main() {
	root := &TreeNode{Val: 2, Left: &TreeNode{Val: 1}, Right: &TreeNode{Val: 3}}
	fmt.Println(isValidBST(root))
}
// true
```

#### 470. 用 Rand7() 实现 Rand10()

[470. 用 Rand7() 实现 Rand10() - 力扣（LeetCode）](https://leetcode.cn/problems/implement-rand10-using-rand7/description/)

```go
func rand10() int {
    t := (rand7() - 1) * 7 + rand7()
    if t > 40 {
        return rand10()
    }
    return (t - 1) % 10 + 1
}
```

#### 34. 在排序数组中查找元素的第一个和最后一个位置

[34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）](https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/)

```go
package main

import "fmt"

func searchRange(nums []int, target int) []int {
	if len(nums) == 0 {
		return []int{-1, -1}
	}
	l, r := 0, len(nums)-1
	for l < r {
		mid := (l + r + 1) >> 1
		if nums[mid] <= target {
			l = mid
		} else {
			r = mid - 1
		}
	}
	var i, j int
	if nums[r] == target {
		i = r
	} else {
		return []int{-1, -1}
	}
	l, r = 0, len(nums)-1
	for l < r {
		mid := (l + r) >> 1
		if nums[mid] >= target {
			r = mid
		} else {
			l = mid + 1
		}
	}
	if nums[r] == target {
		j = r
	} else {
		return []int{-1, -1}
	}
	return []int{j, i}
}

func main() {
	fmt.Println(searchRange([]int{5, 7, 7, 8, 8, 10}, 8))
}
// 3 4
```

#### 64. 最小路径和

[34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）](https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/)

```go
package main

import (
	"fmt"
	"math"
)

func minPathSum(grid [][]int) int {
	m, n := len(grid), len(grid[0])
	memo := make([][]int, m)
	for i := range memo {
		memo[i] = make([]int, n)
		for j := range memo[i] {
			memo[i][j] = -1
		}
	}
	return dp(grid, m-1, n-1, memo)
}

func dp(grid [][]int, m, n int, memo [][]int) int {
	if m == 0 && n == 0 {
		return grid[0][0]
	}
	if m < 0 || n < 0 {
		return math.MaxInt
	}
	if memo[m][n] != -1 {
		return memo[m][n]
	}
	memo[m][n] = min(dp(grid, m-1, n, memo), dp(grid, m, n-1, memo)) + grid[m][n]
	return memo[m][n]
}

func main() {
	fmt.Println(minPathSum([][]int{
		{1, 3, 1},
		{1, 5, 1},
		{4, 2, 1},
	}))
}
// 7
```

#### 48. 旋转图像

[48. 旋转图像 - 力扣（LeetCode）](https://leetcode.cn/problems/rotate-image/description/)

```go
package main

import "fmt"

func rotate(matrix [][]int) {
	m := len(matrix)
	for i, j := 0, m-1; i < j; i, j = i+1, j-1 {
		matrix[i], matrix[j] = matrix[j], matrix[i]
	}
	for i := 0; i < m; i++ {
		for j := i + 1; j < m; j++ {
			matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
		}
	}
}

func main() {
	m := [][]int{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}
	rotate(m)
	fmt.Println(m)
}
// [[7 4 1] [8 5 2] [9 6 3]]
```

#### 39. 组合总数

[39. 组合总和 - 力扣（LeetCode）](https://leetcode.cn/problems/combination-sum/description/)

```go
package main

import "fmt"

var (
	res  [][]int
	path []int
)

func combinationSum(candidates []int, target int) [][]int {
	res = [][]int{}
	path = []int{}
	dfs(candidates, target, 0)
	return res
}

func dfs(candidates []int, target int, u int) {
	if target == 0 {
		tmp := make([]int, len(path))
		copy(tmp, path)
		res = append(res, tmp)
		return
	} else if target < 0 {
		return
	}

	for i := u; i < len(candidates); i++ {
		path = append(path, candidates[i])
		dfs(candidates, target-candidates[i], i)
		path = path[:len(path)-1]
	}
}

func main() {
	fmt.Println(combinationSum([]int{2, 3, 6, 7}, 7))
}
// [[2 2 3] [7]]
```

#### 113. 路径之和 II

[113. 路径总和 II - 力扣（LeetCode）](https://leetcode.cn/problems/path-sum-ii/description/)

```go
package main

import "fmt"

type TreeNode struct {
	Val         int
	Left, Right *TreeNode
}

var res [][]int
var path []int

func pathSum(root *TreeNode, targetSum int) [][]int {
	res = [][]int{}
	path = []int{}
	dfs(root, targetSum)
	return res
}

func dfs(root *TreeNode, targetSum int) {
	if root == nil {
		return
	}
	path = append(path, root.Val)
	targetSum -= root.Val
	if root.Left == nil && root.Right == nil && targetSum == 0 {
		tmp := make([]int, len(path))
		copy(tmp, path)
		res = append(res, tmp)
	}
	if root.Left != nil {
		dfs(root.Left, targetSum)
	}
	if root.Right != nil {
		dfs(root.Right, targetSum)
	}
	path = path[:len(path)-1]
}

func main() {
	root := &TreeNode{
		Val:   3,
		Left:  &TreeNode{Val: 2},
		Right: &TreeNode{Val: 1},
	}
	fmt.Println(pathSum(root, 5))
}
// [3 2]
```

#### 394. 字符串解码

[394. 字符串解码 - 力扣（LeetCode）](https://leetcode.cn/problems/decode-string/description/)

```go
package main

import (
	"fmt"
	"strings"
)

func decodeString(s string) string {
	numStack, strStack, num, result := []int{}, []string{}, 0, ""
	for _, ch := range s {
		if ch >= '0' && ch <= '9' {
			num = num*10 + int(ch-'0')
		} else if ch == '[' {
			numStack, strStack, num, result = append(numStack, num), append(strStack, result), 0, ""
		} else if ch == ']' {
			result, num = strStack[len(strStack)-1]+strings.Repeat(result, numStack[len(numStack)-1]), 0
			strStack, numStack = strStack[:len(strStack)-1], numStack[:len(numStack)-1]
		} else {
			result += string(ch)
		}
	}
	return result
}

func main() {
	fmt.Println(decodeString("3[a]2[bc]"))
}
// aaabcbc
```

#### 240. 搜索二维矩阵

[240. 搜索二维矩阵 II - 力扣（LeetCode）](https://leetcode.cn/problems/search-a-2d-matrix-ii/description/)

```go
package main

import (
	"fmt"
)

func searchMatrix(matrix [][]int, target int) bool {
	i, j := 0, len(matrix[0])-1
	for i < len(matrix) && j >= 0 {
		if matrix[i][j] > target {
			j--
		} else if matrix[i][j] < target {
			i++
		} else {
			return true
		}
	}
	return false
}

func main() {
	fmt.Println(searchMatrix([][]int{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}, 5))
}
// true
```

#### 221. 最大正方形

[221. 最大正方形 - 力扣（LeetCode）](https://leetcode.cn/problems/maximal-square/)

```go
package main

import (
	"fmt"
)

func maximalSquare(matrix [][]byte) int {
	m, n, res := len(matrix), len(matrix[0]), 0
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if matrix[i-1][j-1] == '1' {
				dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
				res = max(res, dp[i][j])
			}
		}
	}
	return res * res
}

func main() {
	fmt.Println(maximalSquare([][]byte{{'1', '1', '1'}, {'1', '1', '0'}, {'0', '0', '0'}}))
}
// 4
```

#### 162. 寻找峰值

[162. 寻找峰值 - 力扣（LeetCode）](https://leetcode.cn/problems/find-peak-element/description/)

```go
package main

import (
	"fmt"
)

func findPeakElement(nums []int) int {
	l, r := 0, len(nums)-1
	for l < r {
		mid := (l + r) / 2
		if nums[mid] >= nums[mid+1] {
			r = mid
		} else {
			l = mid + 1
		}
	}
	return r
}

func main() {
	fmt.Println(findPeakElement([]int{1, 2, 3, 1}))
}
// 2
```

#### 234. 回文链表

[234. 回文链表 - 力扣（LeetCode）](https://leetcode.cn/problems/palindrome-linked-list/description/)

```go
package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

func isPalindrome(head *ListNode) bool {
	if head == nil {
		return true
	}
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}
	if fast != nil {
		slow = slow.Next
	}
	p, q := head, reverseList(slow)
	for q != nil {
		if q.Val != p.Val {
			return false
		}
		q = q.Next
		p = p.Next
	}
	return true
}

func reverseList(head *ListNode) *ListNode {
	if head == nil {
		return head
	}
	a, b := head, head.Next
	for b != nil {
		t := b.Next
		b.Next = a
		a = b
		b = t
	}
	head.Next = nil
	return a
}

func main() {
	head := &ListNode{1, &ListNode{2, &ListNode{2, &ListNode{1, nil}}}}
	fmt.Println(isPalindrome(head))
}
// true
```

#### 112. 路径总和

[112. 路径总和 - 力扣（LeetCode）](https://leetcode.cn/problems/path-sum/description/)

```go
package main

import "fmt"

type TreeNode struct {
	Val         int
	Left, Right *TreeNode
}

var res bool

func hasPathSum(root *TreeNode, targetSum int) bool {
	res = false
	dfs(root, targetSum)
	return res
}

func dfs(root *TreeNode, targetSum int) {
	if root == nil {
		return
	}
	targetSum -= root.Val
	if root.Left == nil && root.Right == nil && targetSum == 0 {
		res = true
		return
	}
	dfs(root.Left, targetSum)
	dfs(root.Right, targetSum)
}

func main() {
	root := &TreeNode{1, &TreeNode{2, nil, nil}, &TreeNode{4, nil, nil}}
	fmt.Println(hasPathSum(root, 3))
}
// true
```

#### 14. 最长公共前缀

[14. 最长公共前缀 - 力扣（LeetCode）](https://leetcode.cn/problems/longest-common-prefix/description/)

```go
package main  
  
import "fmt"  
  
func longestCommonPrefix(strs []string) string {  
    res := ""  
    for i := 0; i < len(strs[0]); i++ {  
       c := strs[0][i]  
       for _, str := range strs {  
          if i >= len(str) || str[i] != c {  
             return res  
          }  
       }       res += string(c)  
    }    return res  
}  
  
func main() {  
    fmt.Println(longestCommonPrefix([]string{"flower", "flow", "flight"}))  
}
// fl
```

#### 128. 最长连续序列

[128. 最长连续序列 - 力扣（LeetCode）](https://leetcode.cn/problems/longest-consecutive-sequence/description/)

```go
package main

import "fmt"

func longestConsecutive(nums []int) int {
	set, res := map[int]bool{}, 0
	for _, n := range nums {
		set[n] = true
	}
	for n := range set {
		if !set[n-1] {
			num := n
			sum := 1
			for set[num+1] {
				num++
				sum++
			}
			res = max(res, sum)
		}
	}
	return res
}

func main() {
	fmt.Println(longestConsecutive([]int{100, 4, 200, 1, 3, 2}))
}
// 4
```

#### 718. 最长重复子数组

[718. 最长重复子数组 - 力扣（LeetCode）](https://leetcode.cn/problems/maximum-length-of-repeated-subarray/description/)

```go
package main

import "fmt"

func findLength(nums1 []int, nums2 []int) int {
	m, n, res := len(nums1), len(nums2), 0
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if nums1[i] == nums2[j] {
				dp[i+1][j+1] = dp[i][j] + 1
			}
			res = max(res, dp[i+1][j+1])
		}
	}
	return res
}

func main() {
	fmt.Println(findLength([]int{1, 2, 3, 2, 1}, []int{3, 2, 1, 4, 7}))
}
// 3
```

#### 169. 多数元素

[169. 多数元素 - 力扣（LeetCode）](https://leetcode.cn/problems/majority-element/)

```go
package main

import "fmt"

func majorityElement(nums []int) int {
	cnt, tg := 0, 0
	for i := 0; i < len(nums); i++ {
		if cnt == 0 {
			tg = nums[i]
			cnt++
			continue
		}
		if nums[i] != tg {
			cnt--
		} else {
			cnt++
		}
	}
	return tg
}

func main() {
	fmt.Println(majorityElement([]int{3, 2, 3}))
}
// 3
```

#### 662. 二叉树最大宽度

[662. 二叉树最大宽度 - 力扣（LeetCode）](https://leetcode.cn/problems/maximum-width-of-binary-tree/)

```go
package main

import "fmt"

type TreeNode struct {
	Val         int
	Left, Right *TreeNode
}

type Node struct {
	Node *TreeNode
	Pos  int
}

func widthOfBinaryTree(root *TreeNode) int {
	res := 0
	if root == nil {
		return res
	}
	q := []*Node{{root, 1}}
	for len(q) > 0 {
		length := len(q)
		l, r := q[0].Pos, 0
		for i := 0; i < length; i++ {
			t := q[0]
			q = q[1:]
			t1 := t.Node
			r = t.Pos
			p := r - l + 1
			if t1.Left != nil {
				q = append(q, &Node{t1.Left, p * 2})
			}
			if t1.Right != nil {
				q = append(q, &Node{t1.Right, p*2 + 1})
			}
		}
		res = max(res, r-l+1)
	}
	return res
}

func main() {
	tree := &TreeNode{
		Val:   1,
		Left:  &TreeNode{Val: 3, Left: &TreeNode{Val: 2}},
		Right: &TreeNode{Val: 2},
	}
	fmt.Println(widthOfBinaryTree(tree))
}
// 2
```

#### 122. 买卖股票的最佳时机 II

[122. 买卖股票的最佳时机 II - 力扣（LeetCode）](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/description/)

```go
package main

import "fmt"

func maxProfit(prices []int) int {
	dp := make([][]int, len(prices))
	for i := range dp {
		dp[i] = make([]int, 2)
	}

	dp[0][0] = 0
	dp[0][1] = -prices[0]

	for i := 1; i < len(prices); i++ {
		dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
		dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])
	}

	return dp[len(prices)-1][0]
}

func main() {
	fmt.Println(maxProfit([]int{7, 1, 5, 3, 6, 4}))
}
// 7
```

#### 62. 不同路径

[62. 不同路径 - 力扣（LeetCode）](https://leetcode.cn/problems/unique-paths/description/)

```go
package main  
  
import "fmt"  
  
func uniquePaths(m int, n int) int {  
    dp := make([][]int, m+1)  
    for i := range dp {  
       dp[i] = make([]int, n+1)  
    }    if m == 1 || n == 1 {  
       return 1  
    }  
    dp[0][1], dp[1][0] = 1, 1  
    for i := 0; i < m; i++ {  
       for j := 0; j < n; j++ {  
          if i != 0 {  
             dp[i][j] += dp[i-1][j]  
          }          if j != 0 {  
             dp[i][j] += dp[i][j-1]  
          }       }    }    return dp[m-1][n-1]  
}  
  
func main() {  
    fmt.Println(uniquePaths(3, 7))  
}
// 28
```

#### 226. 翻转二叉树

[226. 翻转二叉树 - 力扣（LeetCode）](https://leetcode.cn/problems/invert-binary-tree/)

```go
package main

import "fmt"

type TreeNode struct {
	Val         int
	Left, Right *TreeNode
}

func invertTree(root *TreeNode) *TreeNode {
	if root == nil {
		return root
	}
	t := root.Left
	root.Left = root.Right
	root.Right = t
	invertTree(root.Left)
	invertTree(root.Right)
	return root
}

func main() {
	root := &TreeNode{
		Val:   2,
		Left:  &TreeNode{Val: 1},
		Right: &TreeNode{Val: 3},
	}
	invertTree(root)
	fmt.Printf("%d %d %d", root.Val, root.Left.Val, root.Right.Val)
}
// 2 3 1
```

#### 179. 最大数

[179. 最大数 - 力扣（LeetCode）](https://leetcode.cn/problems/largest-number/description/)

```go
package main

import (
	"fmt"
	"sort"
	"strconv"
	"strings"
)

func largestNumber(nums []int) string {
	sort.Slice(nums, func(i, j int) bool {
		a, b := nums[i], nums[j]
		strA, strB := strconv.Itoa(a), strconv.Itoa(b)
		return strA+strB >= strB+strA
	})
	var res string
	for _, num := range nums {
		res += strconv.Itoa(num)
	}
	if len(res) > 0 && res[0] == '0' {
		return "0"
	}
	return res
}

func main() {
	fmt.Println(largestNumber([]int{10, 2}))
}
// 210
```

#### 152. 乘积最大的子数组

[152. 乘积最大子数组 - 力扣（LeetCode）](https://leetcode.cn/problems/maximum-product-subarray/description/)

```go
package main

import (
	"fmt"
)

func maxProduct(nums []int) int {
	dp1, dp2 := make([]int, len(nums)), make([]int, len(nums))
	dp1[0], dp2[0] = nums[0], nums[0]
	res := nums[0]
	for i := 1; i < len(nums); i++ {
		dp1[i] = max(nums[i], dp1[i-1]*nums[i], dp2[i-1]*nums[i])
		dp2[i] = min(nums[i], dp1[i-1]*nums[i], dp2[i-1]*nums[i])
		res = max(res, dp1[i])
	}
	return res
}

func main() {
	fmt.Println(maxProduct([]int{2, 3, -2, 4}))
}
// 6
```

#### 83. 删除排序链表中重复元素

[83. 删除排序链表中的重复元素 - 力扣（LeetCode）](https://leetcode.cn/problems/remove-duplicates-from-sorted-list/description/)

```go
package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

func deleteDuplicates(head *ListNode) *ListNode {
	if head == nil {
		return head
	}
	slow, fast := head, head.Next
	for fast != nil {
		if slow.Val != fast.Val {
			slow.Next = fast
			slow = slow.Next
		}
		fast = fast.Next
	}
	slow.Next = nil
	return head
}

func main() {
	head := &ListNode{Val: 1, Next: &ListNode{Val: 2, Next: &ListNode{Val: 2, Next: nil}}}
	deleteDuplicates(head)
	for head != nil {
		fmt.Printf("%d ", head.Val)
		head = head.Next
	}
}
// 2
```

#### 695. 岛屿的最大面积

[695. 岛屿的最大面积 - 力扣（LeetCode）](https://leetcode.cn/problems/max-area-of-island/description/)

```go
package main

import "fmt"

type Solution struct {
	dx, dy []int
	g      [][]int
}

func maxAreaOfIsland(grid [][]int) int {
	sol := Solution{
		dx: []int{0, 1, 0, -1},
		dy: []int{1, 0, -1, 0},
		g:  grid,
	}
	m, n, res := len(sol.g), len(sol.g[0]), 0
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if sol.g[i][j] == 1 {
				res = max(res, sol.dfs(i, j))
			}
		}
	}
	return res
}

func (sol *Solution) dfs(x, y int) int {
	sol.g[x][y] = 0
	res := 1
	for i := 0; i < 4; i++ {
		a, b := x+sol.dx[i], y+sol.dy[i]
		for a >= 0 && b >= 0 && a < len(sol.g) && b < len(sol.g[0]) && sol.g[a][b] == 1 {
			res += sol.dfs(a, b)
		}
	}
	return res
}

func main() {
	g := [][]int{{1, 1, 0}, {1, 1, 0}, {0, 0, 0}}
	fmt.Println(maxAreaOfIsland(g))
}
// 4
```

#### 227. 基本计算器 II

[227. 基本计算器 II - 力扣（LeetCode）](https://leetcode.cn/problems/basic-calculator-ii/description/)

```go
package main

import "fmt"

func calculate(s string) int {
	s += "+"
	nums, curNum, prevOp, sum := []int{}, 0, '+', 0
	for _, ch := range s {
		if ch >= '0' && ch <= '9' {
			curNum = curNum*10 + int(ch-'0')
		} else if ch != ' ' {
			switch prevOp {
			case '+':
				nums = append(nums, curNum)
			case '-':
				nums = append(nums, -curNum)
			case '*':
				nums[len(nums)-1] *= curNum
			case '/':
				nums[len(nums)-1] /= curNum
			}
			curNum, prevOp = 0, rune(ch)
		}
	}
	for _, n := range nums {
		sum += n
	}
	return sum
}

func main() {
	fmt.Println(calculate("3+2*2"))
}
// 7
```

#### 198. 打家劫舍

[198. 打家劫舍 - 力扣（LeetCode）](https://leetcode.cn/problems/house-robber/description/)

```go
package main

import "fmt"

func rob(nums []int) int {
	dp := make([]int, len(nums)+2)
	for i := len(nums) - 1; i >= 0; i-- {
		dp[i] = max(dp[i+1], dp[i+2]+nums[i])
	}
	return dp[0]
}

func main() {
	fmt.Println(rob([]int{1, 2, 3, 1}))
}
// 4
```

#### 139. 单词拆分

[139. 单词拆分 - 力扣（LeetCode）](https://leetcode.cn/problems/word-break/)

```go
package main

import "fmt"

func wordBreak(s string, dict []string) bool {
	dp := make([]bool, len(s)+1)
	dp[0] = true
	for i := 0; i < len(s); i++ {
		for _, w := range dict {
			if !dp[i] || len(w) > len(s)-i || s[i:i+len(w)] != w {
				continue
			}
			dp[i+len(w)] = true
		}
	}
	return dp[len(s)]
}

func main() {
	fmt.Println(wordBreak("leetcode", []string{"leet", "code"}))
}
// true
```

#### 补充题：手撕堆排序

[912. 排序数组 - 力扣（LeetCode）](https://leetcode.cn/problems/sort-an-array/)

```go
package main

import "fmt"

func heapSort(nums []int) {
	n := len(nums)
	for i := n / 2; i >= 0; i-- {
		sink(nums, i, n-1)
	}
	for end := n - 1; end >= 0; end-- {
		nums[0], nums[end] = nums[end], nums[0]
		sink(nums, 0, end-1)
	}
}

func sink(heap []int, root, end int) {
	// 循环直到节点没有子节点（child直到超出数组的范围）
	for child := 2*root + 1; child <= end; child = 2*root + 1 {
		// 如果有右子节点，并且右子节点的值大于左子节点，则选取右子节点与父节点进行比较
		if child < end && heap[child] < heap[child + 1] {
			child++
		}
		// 如果父节点的值大于子节点，则满足最大堆的性质，无须交换，直接返回
		if heap[root] >= heap[child] {
			break
		}
		// 否则，交换父节点与子节点的值，继续下沉调整
		heap[root], heap[child] = heap[child], heap[root]
		root = child
	}
}

func main() {
	nums := []int{3, 2, 1, 4, 5}
	heapSort(nums)
	fmt.Println(nums)
}
// 1 2 3 4 5
```

#### 24. 两两交换链表中的节点

[24. 两两交换链表中的节点 - 力扣（LeetCode）](https://leetcode.cn/problems/swap-nodes-in-pairs/description/)

```go
package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

func swapPairs(head *ListNode) *ListNode {
	if head == nil {
		return head
	}
	dummy := &ListNode{Next: head}
	p := dummy
	for p.Next != nil && p.Next.Next != nil {
		n1, n2 := p.Next, p.Next.Next
		n1.Next = n2.Next
		n2.Next = n1
		p.Next = n2
		p = n1
	}
	return dummy.Next
}

func main() {
	head := &ListNode{Val: 1, Next: &ListNode{Val: 2, Next: &ListNode{Val: 3, Next: &ListNode{Val: 4}}}}
	res := swapPairs(head)
	for res != nil {
		fmt.Printf("%d ", res.Val)
		res = res.Next
	}
}
// 2 1 4 3
```

#### 297. 二叉树的序列化与反序列化

[297. 二叉树的序列化与反序列化 - 力扣（LeetCode）](https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/description/)

```go
type TreeNode struct {
	Val         int
	Left, Right *TreeNode
}

type Codec struct{}

func Constructor() Codec {
	return Codec{}
}

// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
	if root == nil {
		return "X"
	}
	return strconv.Itoa(root.Val) + "," + this.serialize(root.Left) + "," + this.serialize(root.Right)
}

// Deserializes your encoded data to tree.
func buildTree(list *[]string) *TreeNode {
	rootVal := (*list)[0]
	*list = (*list)[1:]
	if rootVal == "X" {
		return nil
	}
	Val, _ := strconv.Atoi(rootVal)
	root := &TreeNode{Val: Val}
	root.Left = buildTree(list)
	root.Right = buildTree(list)
	return root
}

func (this *Codec) deserialize(data string) *TreeNode {
	list := strings.Split(data, ",")
	return buildTree(&list)
}
```

#### 560. 和为 K 的子数组

[560. 和为 K 的子数组 - 力扣（LeetCode）](https://leetcode.cn/problems/subarray-sum-equals-k/description/)

```go
package main

import "fmt"

func subarraySum(nums []int, k int) int {
	hash := make(map[int]int)
	hash[0] = 1
	pre, res := 0, 0
	for _, n := range nums {
		pre += n
		if _, ok := hash[pre-k]; ok {
			res += hash[pre-k]
		}
		hash[pre]++
	}
	return res
}

func main() {
	fmt.Println(subarraySum([]int{1, 1, 1}, 2))
}
// 2
```

#### 209. 长度最小的子数组

[209. 长度最小的子数组 - 力扣（LeetCode）](https://leetcode.cn/problems/minimum-size-subarray-sum/description/)

```go
package main

import (
	"fmt"
	"math"
)

func minSubArrayLen(target int, nums []int) int {
	r, l, length := 0, 0, math.MaxInt
	for r < len(nums) {
		target -= nums[r]
		r++
		for target <= 0 {
			length = min(length, r-l)
			target += nums[l]
			l++
		}
	}
	if length == math.MaxInt {
		return 0
	}
	return length
}

func main() {
	fmt.Println(minSubArrayLen(7, []int{2, 3, 1, 2, 4, 3}))
}
// 2
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://gists.lanlance.cn/leetcode/go-codetop.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.