Go CodeTop 题解

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

3. 无重复字符的最长子串 - 力扣（LeetCode）

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

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）

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）

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）

用快速排序完成

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）

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

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）

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）

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

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/

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

// 简易版本 未截断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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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

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

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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）

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