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