数据结构与算法问题集合
关于数组和链表的几个必知必会的代码实现
数组
实现一个支持动态扩容的数组
// 支持范型的动态数组（Go 1.18+）
type DynamicArray[T any] struct {
data []T
capacity int
size int
}
func NewDynamicArray[T any](initCap int) *DynamicArray[T] {
return &DynamicArray[T]{
data: make([]T, initCap),
capacity: initCap,
size: 0,
}
}
func (a *DynamicArray[T]) Append(val T) {
if a.size == a.capacity {
newData := make([]T, a.capacity*2)
copy(newData, a.data)
a.data = newData
a.capacity *= 2
}
a.data[a.size] = val
a.size++
}
func (a *DynamicArray[T]) Get(idx int) T {
if idx < 0 || idx >= a.size {
panic("index out of range")
}
return a.data[idx]
}
func (a *DynamicArray[T]) Len() int {
return a.size
}
实现一个大小固定的有序数组，支持动态增删改操作
// 固定大小有序数组，支持动态增删改（Go 1.18+）
type SortedArray[T any] struct {
data []T
size int
capacity int
less func(a, b T) bool // 比较函数
}
func NewSortedArray[T any](cap int, less func(a, b T) bool) *SortedArray[T] {
return &SortedArray[T]{
data: make([]T, cap),
size: 0,
capacity: cap,
less: less,
}
}
// 插入元素，自动保持有序
func (a *SortedArray[T]) Insert(val T) bool {
if a.size == a.capacity {
return false // 超出容量
}
idx := 0
for idx < a.size && a.less(a.data[idx], val) {
idx++
}
// 插入并后移
copy(a.data[idx+1:], a.data[idx:a.size])
a.data[idx] = val
a.size++
return true
}
// 删除指定下标元素
func (a *SortedArray[T]) Delete(idx int) bool {
if idx < 0 || idx >= a.size {
return false
}
copy(a.data[idx:], a.data[idx+1:a.size])
a.size--
return true
}
// 修改指定下标元素并保持有序
func (a *SortedArray[T]) Update(idx int, val T) bool {
if idx < 0 || idx >= a.size {
return false
}
// 删除原元素
old := a.data[idx]
a.Delete(idx)
// 插入新元素
return a.Insert(val)
}
// 获取指定下标元素
func (a *SortedArray[T]) Get(idx int) T {
if idx < 0 || idx >= a.size {
panic("index out of range")
}
return a.data[idx]
}
func (a *SortedArray[T]) Len() int {
return a.size
}
实现两个有序数组合并为一个有序数组
// 合并两个有序数组为一个有序数组（Go 1.18+）
func MergeSortedArrays[T any](a, b []T, less func(a, b T) bool) []T {
i, j := 0, 0
res := make([]T, 0, len(a)+len(b))
for i < len(a) && j < len(b) {
if less(a[i], b[j]) {
res = append(res, a[i])
i++
} else {
res = append(res, b[j])
j++
}
}
for i < len(a) {
res = append(res, a[i])
i++
}
for j < len(b) {
res = append(res, b[j])
j++
}
return res
}
链表
实现单链表，支持增删操作
type SinglyNode[T any] struct {
Val T
Next *SinglyNode[T]
}
type SinglyList[T any] struct {
Head *SinglyNode[T]
}
func (l *SinglyList[T]) Insert(val T) {
node := &SinglyNode[T]{Val: val}
node.Next = l.Head
l.Head = node
}
func (l *SinglyList[T]) Delete(val T, equal func(a, b T) bool) bool {
var prev *SinglyNode[T]
cur := l.Head
for cur != nil {
if equal(cur.Val, val) {
if prev == nil {
l.Head = cur.Next
} else {
prev.Next = cur.Next
}
return true
}
prev = cur
cur = cur.Next
}
return false
}
实现循环链表，支持增删操作
type CircularNode[T any] struct {
Val T
Next *CircularNode[T]
}
type CircularList[T any] struct {
Head *CircularNode[T]
}
func (l *CircularList[T]) Insert(val T) {
node := &CircularNode[T]{Val: val}
if l.Head == nil {
node.Next = node
l.Head = node
return
}
cur := l.Head
for cur.Next != l.Head {
cur = cur.Next
}
cur.Next = node
node.Next = l.Head
}
func (l *CircularList[T]) Delete(val T, equal func(a, b T) bool) bool {
if l.Head == nil {
return false
}
cur := l.Head
var prev *CircularNode[T]
for {
if equal(cur.Val, val) {
if prev == nil {
// 删除头结点
tail := l.Head
for tail.Next != l.Head {
tail = tail.Next
}
if tail == l.Head {
l.Head = nil
} else {
tail.Next = cur.Next
l.Head = cur.Next
}
} else {
prev.Next = cur.Next
}
return true
}
prev = cur
cur = cur.Next
if cur == l.Head {
break
}
}
return false
}
实现双向链表，支持增删操作
type DoublyNode[T any] struct {
Val T
Prev *DoublyNode[T]
Next *DoublyNode[T]
}
type DoublyList[T any] struct {
Head *DoublyNode[T]
Tail *DoublyNode[T]
}
func (l *DoublyList[T]) InsertHead(val T) {
node := &DoublyNode[T]{Val: val}
node.Next = l.Head
if l.Head != nil {
l.Head.Prev = node
}
l.Head = node
if l.Tail == nil {
l.Tail = node
}
}
func (l *DoublyList[T]) InsertTail(val T) {
node := &DoublyNode[T]{Val: val}
node.Prev = l.Tail
if l.Tail != nil {
l.Tail.Next = node
}
l.Tail = node
if l.Head == nil {
l.Head = node
}
}
func (l *DoublyList[T]) Delete(val T, equal func(a, b T) bool) bool {
cur := l.Head
for cur != nil {
if equal(cur.Val, val) {
if cur.Prev != nil {
cur.Prev.Next = cur.Next
} else {
l.Head = cur.Next
}
if cur.Next != nil {
cur.Next.Prev = cur.Prev
} else {
l.Tail = cur.Prev
}
return true
}
cur = cur.Next
}
return false
}
实现单链表反转
type SinglyNode[T any] struct {
Val T
Next *SinglyNode[T]
}
type SinglyList[T any] struct {
Head *SinglyNode[T]
}
func (l *SinglyList[T]) Reverse() {
var prev *SinglyNode[T]
cur := l.Head
for cur != nil {
next := cur.Next
cur.Next = prev
prev = cur
cur = next
}
l.Head = prev
}
实现两个有序的链表合并为一个有序链表
func MergeSortedLists[T any](l1, l2 *SinglyList[T], less func(a, b T) bool) *SinglyList[T] {
dummy := &SinglyNode[T]{}
cur := dummy
p1, p2 := l1.Head, l2.Head
for p1 != nil && p2 != nil {
if less(p1.Val, p2.Val) {
cur.Next = p1
p1 = p1.Next
} else {
cur.Next = p2
p2 = p2.Next
}
cur = cur.Next
}
if p1 != nil {
cur.Next = p1
}
if p2 != nil {
cur.Next = p2
}
return &SinglyList[T]{Head: dummy.Next}
}
求单链表的中间结点（快慢指针法）
func (l *SinglyList[T]) MiddleNode() *SinglyNode[T] {
slow, fast := l.Head, l.Head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
return slow
}
Three Sum(求三数之和)
func threeSum(nums []int) [][]int {
sort.Ints(nums)
res := [][]int{}
n := len(nums)
for i := 0; i < n-2; i++ {
if i > 0 && nums[i] == nums[i-1] {
continue // 跳过重复
}
left, right := i+1, n-1
for left < right {
sum := nums[i] + nums[left] + nums[right]
if sum == 0 {
res = append(res, []int{nums[i], nums[left], nums[right]})
// 跳过重复
for left < right && nums[left] == nums[left+1] {
left++
}
for left < right && nums[right] == nums[right-1] {
right--
}
left++
right--
} else if sum < 0 {
left++
} else {
right--
}
}
}
return res
}
Majority Element(求众数)
func majorityElement(nums []int) int {
res := make(map[int]int)
for _, val := range nums {
res[val]++
}
max, ret := 0, 0
for k, v := range res {
if v > max {
ret = k
max = v
}
}
return ret
}
判断链表中是否有环。
func hasCycle[T any](head *SinglyNode[T]) bool {
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
if slow == fast {
return true
}
}
return false
}
给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。
import (
"container/heap"
)
// 堆节点结构
type heapNode[T any] struct {
node *SinglyNode[T]
}
type nodeHeap[T any] struct {
arr []*heapNode[T]
less func(a, b T) bool
}
func (h *nodeHeap[T]) Len() int { return len(h.arr) }
func (h *nodeHeap[T]) Less(i, j int) bool { return h.less(h.arr[i].node.Val, h.arr[j].node.Val) }
func (h *nodeHeap[T]) Swap(i, j int) { h.arr[i], h.arr[j] = h.arr[j], h.arr[i] }
func (h *nodeHeap[T]) Push(x any) { h.arr = append(h.arr, x.(*heapNode[T])) }
func (h *nodeHeap[T]) Pop() any {
n := len(h.arr)
x := h.arr[n-1]
h.arr = h.arr[:n-1]
return x
}
// 合并多个升序链表
func mergeKLists[T any](lists []*SinglyNode[T], less func(a, b T) bool) *SinglyNode[T] {
h := &nodeHeap[T]{less: less}
heap.Init(h)
for _, node := range lists {
if node != nil {
heap.Push(h, &heapNode[T]{node: node})
}
}
dummy := &SinglyNode[T]{}
cur := dummy
for h.Len() > 0 {
minNode := heap.Pop(h).(*heapNode[T])
cur.Next = minNode.node
cur = cur.Next
if minNode.node.Next != nil {
heap.Push(h, &heapNode[T]{node: minNode.node.Next})
}
}
return dummy.Next
}
用法举例：
lists := []*SinglyNode[int]{链表1头, 链表2头, ...}
merged := mergeKLists(lists, func(a, b int) bool { return a < b })
关于栈、队列和递归的几个必知必会的代码实现
栈
用数组实现一个顺序栈
// 顺序栈（支持范型，Go 1.18+）
type Stack[T any] struct {
data []T
top int
}
func NewStack[T any]() *Stack[T] {
return &Stack[T]{data: make([]T, 0), top: -1}
}
func (s *Stack[T]) Push(val T) {
s.data = append(s.data, val)
s.top++
}
func (s *Stack[T]) Pop() (T, bool) {
if s.top < 0 {
var zero T
return zero, false
}
val := s.data[s.top]
s.data = s.data[:s.top]
s.top--
return val, true
}
func (s *Stack[T]) Peek() (T, bool) {
if s.top < 0 {
var zero T
return zero, false
}
return s.data[s.top], true
}
func (s *Stack[T]) IsEmpty() bool {
return s.top < 0
}
func (s *Stack[T]) Len() int {
return s.top +
用链表实现一个链式栈
// 链式栈（支持范型，Go 1.18+）
type StackNode[T any] struct {
Val T
Next *StackNode[T]
}
type LinkedStack[T any] struct {
top *StackNode[T]
size int
}
func NewLinkedStack[T any]() *LinkedStack[T] {
return &LinkedStack[T]{top: nil, size: 0}
}
func (s *LinkedStack[T]) Push(val T) {
node := &StackNode[T]{Val: val, Next: s.top}
s.top = node
s.size++
}
func (s *LinkedStack[T]) Pop() (T, bool) {
if s.top == nil {
var zero T
return zero, false
}
val := s.top.Val
s.top = s.top.Next
s.size--
return val, true
}
func (s *LinkedStack[T]) Peek() (T, bool) {
if s.top == nil {
var zero T
return zero, false
}
return s.top.Val, true
}
func (s *LinkedStack[T]) IsEmpty() bool {
return s.top == nil
}
func (s *LinkedStack[T]) Len() int {
return s.size
}
编程模拟实现一个浏览器的前进、后退功能
// 浏览器前进/后退功能模拟（Go 1.18+）
type Browser[T any] struct {
backStack *LinkedStack[T] // 后退栈
forwardStack *LinkedStack[T] // 前进栈
current T
hasCurrent bool
}
func NewBrowser[T any]() *Browser[T] {
return &Browser[T]{
backStack: NewLinkedStack[T](),
forwardStack: NewLinkedStack[T](),
hasCurrent: false,
}
}
// 打开新页面
func (b *Browser[T]) Open(page T) {
if b.hasCurrent {
b.backStack.Push(b.current)
}
b.current = page
b.hasCurrent = true
b.forwardStack = NewLinkedStack[T]() // 清空前进栈
}
// 后退
func (b *Browser[T]) Back() bool {
if b.backStack.IsEmpty() {
return false
}
b.forwardStack.Push(b.current)
b.current, _ = b.backStack.Pop()
return true
}
// 前进
func (b *Browser[T]) Forward() bool {
if b.forwardStack.IsEmpty() {
return false
}
b.backStack.Push(b.current)
b.current, _ = b.forwardStack.Pop()
return true
}
// 获取当前页面
func (b *Browser[T]) Current() (T, bool) {
return b.current, b.hasCurrent
}
队列
用数组实现一个顺序队列(循环队列)
// 顺序队列（支持范型，Go 1.18+）
type Queue[T any] struct {
data []T
front int
rear int
size int
}
func NewQueue[T any](cap int) *Queue[T] {
return &Queue[T]{
data: make([]T, cap),
front: 0,
rear: 0,
size: 0,
}
}
func (q *Queue[T]) Enqueue(val T) bool {
if q.size == len(q.data) {
return false // 队列满
}
q.data[q.rear] = val
q.rear = (q.rear + 1) % len(q.data)
q.size++
return true
}
func (q *Queue[T]) Dequeue() (T, bool) {
if q.size == 0 {
var zero T
return zero, false
}
val := q.data[q.front]
q.front = (q.front + 1) % len(q.data)
q.size--
return val, true
}
func (q *Queue[T]) IsEmpty() bool {
return q.size == 0
}
func (q *Queue[T]) IsFull() bool {
return q.size == len(q.data)
}
func (q *Queue[T]) Len() int {
return
用链表实现一个链式队列
// 链式队列（支持范型，Go 1.18+）
type QueueNode[T any] struct {
Val T
Next *QueueNode[T]
}
type LinkedQueue[T any] struct {
head *QueueNode[T]
tail *QueueNode[T]
size int
}
func NewLinkedQueue[T any]() *LinkedQueue[T] {
return &LinkedQueue[T]{head: nil, tail: nil, size: 0}
}
func (q *LinkedQueue[T]) Enqueue(val T) {
node := &QueueNode[T]{Val: val}
if q.tail != nil {
q.tail.Next = node
} else {
q.head = node
}
q.tail = node
q.size++
}
func (q *LinkedQueue[T]) Dequeue() (T, bool) {
if q.head == nil {
var zero T
return zero, false
}
val := q.head.Val
q.head = q.head.Next
if q.head == nil {
q.tail = nil
}
q.size--
return val, true
}
func (q *LinkedQueue[T]) IsEmpty() bool {
return q.size == 0
}
func (q *LinkedQueue[T]) Len() int {
return q.size
}
递归
编程实现斐波那契数列求值 f(n)=f(n-1)+f(n-2)
func fib(n int) int {
if n <= 1 {
return n
}
return fib(n-1) + fib(n-2)
}
递归实现阶乘 n!
func factorial(n int) int {
if n <= 1 {
return 1
}
return n * factorial(n-1)
}
Valid Parentheses(有效的括号)
// 有效的括号判断（Go 1.18+）
func isValid(s string) bool {
stack := []rune{}
pairs := map[rune]rune{')': '(', ']': '[', '}': '{'}
for _, ch := range s {
switch ch {
case '(', '[', '{':
stack = append(stack, ch)
case ')', ']', '}':
if len(stack) == 0 || stack[len(stack)-1] != pairs[ch] {
return false
}
stack = stack[:len(stack)-1]
}
}
return len(stack) == 0
}
逆波兰表达式求值
// 逆波兰表达式（后缀表达式）求值
func evalRPN(tokens []string) int {
stack := []int{}
for _, token := range tokens {
switch token {
case "+", "-", "*", "/":
b := stack[len(stack)-1]
a := stack[len(stack)-2]
stack = stack[:len(stack)-2]
var res int
switch token {
case "+":
res = a + b
case "-":
res = a - b
case "*":
res = a * b
case "/":
res = a / b
}
stack = append(stack, res)
default:
num, _ := strconv.Atoi(token)
stack = append(stack, num)
}
}
return stack[0]
}
设计循环双端队列
// 循环双端队列（Go 1.18+）
type CircularDeque[T any] struct {
data []T
front int
rear int
size int
}
func NewCircularDeque[T any](cap int) *CircularDeque[T] {
return &CircularDeque[T]{
data: make([]T, cap),
front: 0,
rear: 0,
size: 0,
}
}
// 队头插入
func (q *CircularDeque[T]) PushFront(val T) bool {
if q.size == len(q.data) {
return false // 满
}
q.front = (q.front - 1 + len(q.data)) % len(q.data)
q.data[q.front] = val
q.size++
return true
}
// 队尾插入
func (q *CircularDeque[T]) PushBack(val T) bool {
if q.size == len(q.data) {
return false // 满
}
q.data[q.rear] = val
q.rear = (q.rear + 1) % len(q.data)
q.size++
return true
}
// 队头弹出
func (q *CircularDeque[T]) PopFront() (T, bool) {
if q.size == 0 {
var zero T
return zero, false
}
val := q.data[q.front]
q.front = (q.front + 1) % len(q.data)
q.size--
return val, true
}
// 队尾弹出
func (q *CircularDeque[T]) PopBack() (T, bool) {
if q.size == 0 {
var zero T
return zero, false
}
q.rear = (q.rear - 1 + len(q.data)) % len(q.data)
val := q.data[q.rear]
q.size--
return val, true
}
func (q *CircularDeque[T]) IsEmpty() bool {
return q.size == 0
}
func (q *CircularDeque[T]) IsFull() bool {
return q.size == len(q.data)
}
func (q *CircularDeque[T]) Len() int {
爬楼梯(假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？)
// 爬楼梯问题，动态规划解法
func climbStairs(n int) int {
if n <= 2 {
return n
}
a, b := 1, 2
for i := 3; i <= n; i++ {
a, b = b, a+b
}
return b
}
关于排序和二分查找的几个必知必会的代码实现
排序
实现归并排序
// 归并排序（Go 1.18+，支持范型）
func mergeSort[T any](arr []T, less func(a, b T) bool) []T {
if len(arr) <= 1 {
return arr
}
mid := len(arr) / 2
left := mergeSort(arr[:mid], less)
right := mergeSort(arr[mid:], less)
return merge(left, right, less)
}
func merge[T any](a, b []T, less func(a, b T) bool) []T {
res := make([]T, 0, len(a)+len(b))
i, j := 0, 0
for i < len(a) && j < len(b) {
if less(a[i], b[j]) {
res = append(res, a[i])
i++
} else {
res = append(res, b[j])
j++
}
}
res = append(res, a[i:]...)
res = append(res, b[j:]...)
return res
}
nums := []int{5, 2, 4, 7, 1, 3, 6}
sorted := mergeSort(nums, func(a, b int) bool { return a < b })
快速排序
// 快速排序（Go 1.18+，支持范型）
func quickSort[T any](arr []T, less func(a, b T) bool) {
var sort func(left, right int)
sort = func(left, right int) {
if left >= right {
return
}
pivot := arr[left]
i, j := left, right
for i < j {
for i < j && !less(arr[j], pivot) {
j--
}
if i < j {
arr[i] = arr[j]
i++
}
for i < j && less(arr[i], pivot) {
i++
}
if i < j {
arr[j] = arr[i]
j--
}
}
arr[i] = pivot
sort(left, i-1)
sort(i+1, right)
}
sort(0, len(arr)-1)
}
nums := []int{5, 2, 4, 7, 1, 3, 6}
quickSort(nums, func(a, b int) bool { return a < b })
插入排序
// 插入排序（Go 1.18+，支持范型）
func insertionSort[T any](arr []T, less func(a, b T) bool) {
n := len(arr)
for i := 1; i < n; i++ {
key := arr[i]
j := i - 1
for j >= 0 && less(key, arr[j]) {
arr[j+1] = arr[j]
j--
}
arr[j+1] = key
}
}
nums := []int{5, 2, 4, 7, 1, 3, 6}
insertionSort(nums, func(a, b int) bool { return a < b })
冒泡排序
// 冒泡排序（Go 1.18+，支持范型）
func bubbleSort[T any](arr []T, less func(a, b T) bool) {
n := len(arr)
for i := 0; i < n-1; i++ {
for j := 0; j < n-1-i; j++ {
if less(arr[j+1], arr[j]) {
arr[j], arr[j+1] = arr[j+1], arr[j]
}
}
}
}
// 用法示例
nums := []int{5, 2, 4, 7, 1, 3, 6}
bubbleSort(nums, func(a, b int) bool { return a <
选择排序
// 选择排序（Go 1.18+，支持范型）
func selectionSort[T any](arr []T, less func(a, b T) bool) {
n := len(arr)
for i := 0; i < n-1; i++ {
minIdx := i
for j := i + 1; j < n; j++ {
if less(arr[j], arr[minIdx]) {
minIdx = j
}
}
if minIdx != i {
arr[i], arr[minIdx] = arr[minIdx], arr[i]
}
}
}
// 用法示例
nums := []int{5, 2, 4, 7, 1, 3, 6}
selectionSort(nums, func(a, b int) bool { return a < b
O(n) 时间复杂度内找到一组数据的第 K 大元素
// 快速选择算法，O(n) 平均时间复杂度，找第 K 大元素（Go 1.18+）
func findKthLargest(nums []int, k int) int {
n := len(nums)
target := n - k // 转为第 (n-k) 小
var quickSelect func(left, right int) int
quickSelect = func(left, right int) int {
pivot := nums[left]
i, j := left, right
for i < j {
for i < j && nums[j] >= pivot {
j--
}
if i < j {
nums[i] = nums[j]
i++
}
for i < j && nums[i] <= pivot {
i++
}
if i < j {
nums[j] = nums[i]
j--
}
}
nums[i] = pivot
if i == target {
return nums[i]
} else if i < target {
return quickSelect(i+1, right)
} else {
return quickSelect(left, i-1)
}
}
return quickSelect(0, n-1)
}
二分查找
实现一个有序数组的二分查找算法
// 二分查找（Go 1.18+，支持范型）
func binarySearch[T any](arr []T, target T, less func(a, b T) bool, equal func(a, b T) bool) int {
left, right := 0, len(arr)-1
for left <= right {
mid := left + (right-left)/2
if equal(arr[mid], target) {
return mid
} else if less(arr[mid], target) {
left = mid + 1
} else {
right = mid - 1
}
}
return -1 // 未找到
}
// 用法示例
nums := []int{1, 2, 3, 4, 5, 6, 7}
idx := binarySearch(nums, 4, func(a, b int) bool { return a < b }, func(a, b int) bool { return a == b })
// idx == 3
搜索旋转排序数组 https://leetcode.cn/problems/search-in-rotated-sorted-array/description/
// 搜索旋转排序数组
func search(nums []int, target int) int {
left, right := 0, len(nums)-1
for left <= right {
mid := left + (right-left)/2
if nums[mid] == target {
return mid
}
// 左半部分有序
if nums[left] <= nums[mid] {
if nums[left] <= target && target < nums[mid] {
right = mid - 1
} else {
left = mid + 1
}
} else { // 右半部分有序
if nums[mid] < target && target <= nums[right] {
left = mid + 1
} else {
right = mid - 1
}
}
}
return -1
}
实现模糊二分查找算法(比如大于等于给定值的第一个元素)
// 模糊二分查找：返回大于等于 target 的第一个元素下标（Go 1.18+，支持范型）
func lowerBound[T any](arr []T, target T, less func(a, b T) bool) int {
left, right := 0, len(arr)
for left < right {
mid := left + (right-left)/2
if less(arr[mid], target) {
left = mid + 1
} else {
right = mid
}
}
// 如果 left == len(arr)，说明没有大于等于 target 的元素
return left
}
// 用法示例
nums := []int{1, 2, 4, 4, 5, 7}
idx := lowerBound(nums, 4, func(a, b int) bool { return a < b }) //
x 的平方根
// 用二分查找实现 x 的平方根（返回整数部分）
func mySqrt(x int) int {
if x < 2 {
return x
}
left, right := 1, x
for left <= right {
mid := left + (right-left)/2
if mid*mid == x {
return mid
} else if mid*mid < x {
left = mid + 1
} else {
right = mid - 1
}
}
return right // 返回不超过 x 的最大整数
}
// 用法示例
// mySqrt(8) 返回
关于散列表和字符串的几个必知必会的代码实现
散列表
实现一个基于链表法解决冲突问题的散列表
// 基于链表法解决冲突的散列表（Go 1.18+，支持范型）
type HashNode[K comparable, V any] struct {
Key K
Value V
Next *HashNode[K, V]
}
type HashTable[K comparable, V any] struct {
buckets []*HashNode[K, V]
size int
}
func NewHashTable[K comparable, V any](cap int) *HashTable[K, V] {
return &HashTable[K, V]{buckets: make([]*HashNode[K, V], cap)}
}
func (ht *HashTable[K, V]) hash(key K) int {
return int(uint64(hashAny(key)) % uint64(len(ht.buckets)))
}
// 简单哈希函数
func hashAny(key any) uint64 {
return uint64(fmt.Sprintf("%v", key)[0])
}
// 插入或更新
func (ht *HashTable[K, V]) Put(key K, value V) {
idx := ht.hash(key)
node := ht.buckets[idx]
for node != nil {
if node.Key == key {
node.Value = value
return
}
node = node.Next
}
ht.buckets[idx] = &HashNode[K, V]{Key: key, Value: value, Next: ht.buckets[idx]}
ht.size++
}
// 查找
func (ht *HashTable[K, V]) Get(key K) (V, bool) {
idx := ht.hash(key)
node := ht.buckets[idx]
for node != nil {
if node.Key == key {
return node.Value, true
}
node = node.Next
}
var zero V
return zero, false
}
// 删除
func (ht *HashTable[K, V]) Delete(key K) bool {
idx := ht.hash(key)
node := ht.buckets[idx]
var prev *HashNode[K, V]
for node != nil {
if node.Key == key {
if prev == nil {
ht.buckets[idx] = node.Next
} else {
prev.Next = node.Next
}
ht.size--
return true
}
prev = node
node = node.Next
}
return false
}
实现一个 LRU 缓存淘汰算法
import "container/list"
type LRUCache struct {
capacity int
cache map[int]*list.Element
list *list.List
}
type Pair struct {
key int
value int
}
func NewLRUCache(capacity int) *LRUCache {
return &LRUCache{
capacity: capacity,
cache: make(map[int]*list.Element),
list: list.New(),
}
}
func (c *LRUCache) Get(key int) int {
if elem, found := c.cache[key]; found {
c.list.MoveToFront(elem)
return elem.Value.(*Pair).value
}
return -1
}
func (c *LRUCache) Put(key int, value int) {
if elem, found := c.cache[key]; found {
c.list.MoveToFront(elem)
elem.Value.(*Pair).value = value
} else {
if c.list.Len() == c.capacity {
back := c.list.Back()
c.list.Remove(back)
delete(c.cache, back.Value.(*Pair).key)
}
pair := &Pair{key, value}
elem := c.list.PushFront(pair)
c.cache[key] = elem
}
}
实现一个 LFU 缓存淘汰算法
import "container/heap"
type LFUCache struct {
capacity int
cache map[int]*Item
freqHeap *FrequencyHeap
}
type Item struct {
key int
value int
frequency int
index int
}
type FrequencyHeap []*Item
func (h FrequencyHeap) Len() int { return len(h) }
func (h FrequencyHeap) Less(i, j int) bool { return h[i].frequency < h[j].frequency }
func (h FrequencyHeap) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
h[i].index = i
h[j].index = j
}
func (h *FrequencyHeap) Push(x interface{}) {
item := x.(*Item)
item.index = len(*h)
*h = append(*h, item)
}
func (h *FrequencyHeap) Pop() interface{} {
old := *h
n := len(old)
item := old[n-1]
*h = old[0 : n-1]
return item
}
func NewLFUCache(capacity int) *LFUCache {
return &LFUCache{
capacity: capacity,
cache: make(map[int]*Item),
freqHeap: &FrequencyHeap{},
}
}
func (c *LFUCache) Get(key int) int {
if item, found := c.cache[key]; found {
item.frequency++
heap.Fix(c.freqHeap, item.index)
return item.value
}
return -1
}
func (c *LFUCache) Put(key int, value int) {
if c.capacity == 0 {
return
}
if item, found := c.cache[key]; found {
item.value = value
item.frequency++
heap.Fix(c.freqHeap, item.index)
} else {
if len(c.cache) == c.capacity {
least := heap.Pop(c.freqHeap).(*Item)
delete(c.cache, least.key)
}
item := &Item{key: key, value: value, frequency: 1}
heap.Push(c.freqHeap, item)
c.cache[key] = item
}
}
字符串
实现一个字符集，只包含 a~z 这 26 个英文字母的 Trie 树
// 只包含 a~z 的 Trie 树实现
type TrieNode struct {
children [26]*TrieNode
isEnd bool
}
type Trie struct {
root *TrieNode
}
func NewTrie() *Trie {
return &Trie{root: &TrieNode{}}
}
// 插入单词
func (t *Trie) Insert(word string) {
node := t.root
for _, ch := range word {
idx := ch - 'a'
if node.children[idx] == nil {
node.children[idx] = &TrieNode{}
}
node = node.children[idx]
}
node.isEnd = true
}
// 查找单词
func (t *Trie) Search(word string) bool {
node := t.root
for _, ch := range word {
idx := ch - 'a'
if node.children[idx] == nil {
return false
}
node = node.children[idx]
}
return node.isEnd
}
// 查找前缀
func (t *Trie) StartsWith(prefix string) bool {
node := t.root
for _, ch := range prefix {
idx := ch - 'a'
if node.children[idx] == nil {
return false
}
node = node.children[idx]
}
return true
实现朴素的字符串匹配算法
// 朴素字符串匹配算法（Go 1.18+）
func strStr(haystack, needle string) int {
n, m := len(haystack), len(needle)
if m == 0 {
return 0
}
for i := 0; i <= n-m; i++ {
j := 0
for ; j < m; j++ {
if haystack[i+j] != needle[j] {
break
}
}
if j == m {
return i
}
}
return -1
}
反转字符串
func reverseString(s string) string {
runes := []rune(s)
left, right := 0, len(runes)-1
for left < right {
runes[left], runes[right] = runes[right], runes[left]
left++
right--
}
return string(runes)
}
翻转字符串里的单词
// 翻转字符串里的单词（去除多余空格，单词顺序反转）
func reverseWords(s string) string {
words := strings.Fields(s) // 按空格分割并去除多余空格
left, right := 0, len(words)-1
for left < right {
words[left], words[right] = words[right], words[left]
left++
right--
}
return strings.Join(words, " ")
}
字符串转换整数 (atoi)
// 字符串转换整数 (atoi) 实现
func myAtoi(s string) int {
s = strings.TrimSpace(s)
if len(s) == 0 {
return 0
}
sign, i := 1, 0
if s[0] == '-' {
sign = -1
i++
} else if s[0] == '+' {
i++
}
res := 0
for ; i < len(s); i++ {
if s[i] < '0' || s[i] > '9' {
break
}
res = res*10 + int(s[i]-'0')
// 溢出处理
if sign == 1 && res > 2147483647 {
return 2147483647
}
if sign == -1 && res > 2147483648 {
return -2147483648
}
}
return sign * res
}
关于二叉树和堆的 几个必知必会的代码实现
二叉树
实现一个二叉查找树，并且支持插入、删除、查找操作
// 二叉查找树（BST）支持插入、删除、查找操作（Go 1.18+）
type BSTNode[T any] struct {
Val T
Left *BSTNode[T]
Right *BSTNode[T]
}
type BST[T any] struct {
Root *BSTNode[T]
less func(a, b T) bool
equal func(a, b T) bool
}
func NewBST[T any](less func(a, b T) bool, equal func(a, b T) bool) *BST[T] {
return &BST[T]{less: less, equal: equal}
}
// 插入
func (t *BST[T]) Insert(val T) {
t.Root = insertNode(t.Root, val, t.less)
}
func insertNode[T any](node *BSTNode[T], val T, less func(a, b T) bool) *BSTNode[T] {
if node == nil {
return &BSTNode[T]{Val: val}
}
if less(val, node.Val) {
node.Left = insertNode(node.Left, val, less)
} else if less(node.Val, val) {
node.Right = insertNode(node.Right, val, less)
}
return node
}
// 查找
func (t *BST[T]) Search(val T) *BSTNode[T] {
node := t.Root
for node != nil {
if t.equal(val, node.Val) {
return node
} else if t.less(val, node.Val) {
node = node.Left
} else {
node = node.Right
}
}
return nil
}
// 删除
func (t *BST[T]) Delete(val T) {
t.Root = deleteNode(t.Root, val, t.less, t.equal)
}
func deleteNode[T any](node *BSTNode[T], val T, less func(a, b T) bool, equal func(a, b T) bool) *BSTNode[T] {
if node == nil {
return nil
}
if less(val, node.Val) {
node.Left = deleteNode(node.Left, val, less, equal)
} else if less(node.Val, val) {
node.Right = deleteNode(node.Right, val, less, equal)
} else {
// 找到节点
if node.Left == nil {
return node.Right
}
if node.Right == nil {
return node.Left
}
// 两个孩子，找右子树最小节点替换
minNode := node.Right
for minNode.Left != nil {
minNode = minNode.Left
}
node.Val = minNode.Val
node.Right = deleteNode(node.Right, minNode.Val, less, equal)
}
return node
}
实现查找二叉查找树中某个节点的后继、前驱节点
// 查找BST中某个节点的后继节点（中序遍历下一个节点）
func successor[T any](root *BSTNode[T], node *BSTNode[T], less func(a, b T) bool) *BSTNode[T] {
// 情况1：有右子树，后继是右子树最左节点
if node.Right != nil {
succ := node.Right
for succ.Left != nil {
succ = succ.Left
}
return succ
}
// 情况2：无右子树，向上找第一个比当前节点大的祖先
var succ *BSTNode[T]
cur := root
for cur != nil {
if less(node.Val, cur.Val) {
succ = cur
cur = cur.Left
} else if less(cur.Val, node.Val) {
cur = cur.Right
} else {
break
}
}
return succ
}
// 查找BST中某个节点的前驱节点（中序遍历上一个节点）
func predecessor[T any](root *BSTNode[T], node *BSTNode[T], less func(a, b T) bool) *BSTNode[T] {
// 情况1：有左子树，前驱是左子树最右节点
if node.Left != nil {
pred := node.Left
for pred.Right != nil {
pred = pred.Right
}
return pred
}
// 情况2：无左子树，向上找第一个比当前节点小的祖先
var pred *BSTNode[T]
cur := root
for cur != nil {
if less(cur.Val, node.Val) {
pred = cur
cur = cur.Right
} else if less(node.Val, cur.Val) {
cur = cur.Left
} else {
break
}
}
return pred
}
//后继：右子树最左节点或向上找第一个比当前节点大的祖先。
//前驱：左子树最右节点或向上找第一个比当前节点小的祖先。
实现二叉树前、中、后序以及按层遍历
// 二叉树前序遍历（递归）
func preorder[T any](root *BSTNode[T], visit func(T)) {
if root == nil {
return
}
visit(root.Val)
preorder(root.Left, visit)
preorder(root.Right, visit)
}
// 二叉树中序遍历（递归）
func inorder[T any](root *BSTNode[T], visit func(T)) {
if root == nil {
return
}
inorder(root.Left, visit)
visit(root.Val)
inorder(root.Right, visit)
}
// 二叉树后序遍历（递归）
func postorder[T any](root *BSTNode[T], visit func(T)) {
if root == nil {
return
}
postorder(root.Left, visit)
postorder(root.Right, visit)
visit(root.Val)
}
// 二叉树按层遍历（广度优先）
func levelOrder[T any](root *BSTNode[T], visit func(T)) {
if root == nil {
return
}
queue := []*BSTNode[T]{root}
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
visit(node.Val)
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
}
// 示例：打印节点值
visit := func(val int) {
fmt.Println(val)
}
// 用法举例
// 假设 root 是 *BSTNode[int]
preorder(root, visit)
inorder(root, visit)
postorder(root, visit)
levelOrder(root, visit)
堆
实现一个小顶堆、大顶堆、优先级队列
// 小顶堆（Go 1.18+，支持范型）
type MinHeap[T any] struct {
data []T
less func(a, b T) bool
}
func NewMinHeap[T any](less func(a, b T) bool) *MinHeap[T] {
return &MinHeap[T]{less: less}
}
func (h *MinHeap[T]) Push(val T) {
h.data = append(h.data, val)
h.up(len(h.data) - 1)
}
func (h *MinHeap[T]) Pop() (T, bool) {
if len(h.data) == 0 {
var zero T
return zero, false
}
res := h.data[0]
h.data[0] = h.data[len(h.data)-1]
h.data = h.data[:len(h.data)-1]
h.down(0)
return res, true
}
func (h *MinHeap[T]) up(i int) {
for i > 0 {
p := (i - 1) / 2
if !h.less(h.data[i], h.data[p]) {
break
}
h.data[i], h.data[p] = h.data[p], h.data[i]
i = p
}
}
func (h *MinHeap[T]) down(i int) {
n := len(h.data)
for {
l, r, smallest := 2*i+1, 2*i+2, i
if l < n && h.less(h.data[l], h.data[smallest]) {
smallest = l
}
if r < n && h.less(h.data[r], h.data[smallest]) {
smallest = r
}
if smallest == i {
break
}
h.data[i], h.data[smallest] = h.data[smallest], h.data[i]
i = smallest
}
}
// 大顶堆只需将 less 逻辑反转
type MaxHeap[T any] struct {
data []T
greater func(a, b T) bool
}
func NewMaxHeap[T any](greater func(a, b T) bool) *MaxHeap[T] {
return &MaxHeap[T]{greater: greater}
}
func (h *MaxHeap[T]) Push(val T) {
h.data = append(h.data, val)
h.up(len(h.data) - 1)
}
func (h *MaxHeap[T]) Pop() (T, bool) {
if len(h.data) == 0 {
var zero T
return zero, false
}
res := h.data[0]
h.data[0] = h.data[len(h.data)-1]
h.data = h.data[:len(h.data)-1]
h.down(0)
return res, true
}
func (h *MaxHeap[T]) up(i int) {
for i > 0 {
p := (i - 1) / 2
if !h.greater(h.data[i], h.data[p]) {
break
}
h.data[i], h.data[p] = h.data[p], h.data[i]
i = p
}
}
func (h *MaxHeap[T]) down(i int) {
n := len(h.data)
for {
l, r, largest := 2*i+1, 2*i+2, i
if l < n && h.greater(h.data[l], h.data[largest]) {
largest = l
}
if r < n && h.greater(h.data[r], h.data[largest]) {
largest = r
}
if largest == i {
break
}
h.data[i], h.data[largest] = h.data[largest], h.data[i]
i = largest
}
}
// 优先级队列本质就是堆，可以用 MinHeap 或 MaxHeap 实现
实现堆排序
// 堆排序（Go 1.18+，支持范型，升序用大顶堆，降序用小顶堆）
func heapSort[T any](arr []T, less func(a, b T) bool) {
n := len(arr)
// 建堆（大顶堆）
for i := n/2 - 1; i >= 0; i-- {
down(arr, i, n, less)
}
// 排序
for i := n - 1; i > 0; i-- {
arr[0], arr[i] = arr[i], arr[0]
down(arr, 0, i, less)
}
}
// 堆调整（大顶堆）
func down[T any](arr []T, i, n int, less func(a, b T) bool) {
for {
l, r, largest := 2*i+1, 2*i+2, i
if l < n && less(arr[largest], arr[l]) {
largest = l
}
if r < n && less(arr[largest], arr[r]) {
largest = r
}
if largest == i {
break
}
arr[i], arr[largest] = arr[largest], arr[i]
i = largest
}
}
// 用法示例
nums := []int{5, 2, 4, 7, 1, 3, 6}
heapSort(nums, func(a, b int) bool { return a < b }) // 升序排序
利用优先级队列合并 K 个有序数组
import (
"container/heap"
)
// 堆节点结构
type ArrayNode struct {
val int
arrIdx int // 数组编号
idx int // 当前元素在数组中的下标
}
// 小顶堆实现
type NodeHeap []*ArrayNode
func (h NodeHeap) Len() int { return len(h) }
func (h NodeHeap) Less(i, j int) bool { return h[i].val < h[j].val }
func (h NodeHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *NodeHeap) Push(x any) { *h = append(*h, x.(*ArrayNode)) }
func (h *NodeHeap) Pop() any {
old := *h
n := len(old)
x := old[n-1]
*h = old[:n-1]
return x
}
// 合并 K 个有序数组
func mergeKSortedArrays(arrs [][]int) []int {
h := &NodeHeap{}
heap.Init(h)
res := []int{}
// 初始化堆，放入每个数组的第一个元素
for i, arr := range arrs {
if len(arr) > 0 {
heap.Push(h, &ArrayNode{val: arr[0], arrIdx: i, idx: 0})
}
}
for h.Len() > 0 {
node := heap.Pop(h).(*ArrayNode)
res = append(res, node.val)
// 如果该数组还有下一个元素，加入堆
if node.idx+1 < len(arrs[node.arrIdx]) {
nextIdx := node.idx + 1
heap.Push(h, &ArrayNode{val: arrs[node.arrIdx][nextIdx], arrIdx: node.arrIdx, idx: nextIdx})
}
}
return res
}
// 用法示例
// arrs := [][]int{{1,4,7},{2,5,8},{3,6,9}}
// merged := mergeKSortedArrays(arrs) // 返回 [1 2 3 4 5 6 7 8 9]
求一组动态数据集合的最大 Top K
import (
"container/heap"
)
// 小顶堆实现 Top K
type MinHeap []int
func (h MinHeap) Len() int { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x any) { *h = append(*h, x.(int)) }
func (h *MinHeap) Pop() any {
old := *h
n := len(old)
x := old[n-1]
*h = old[:n-1]
return x
}
// 求动态数据集合最大 Top K
type TopK struct {
k int
heap *MinHeap
}
func NewTopK(k int) *TopK {
h := &MinHeap{}
heap.Init(h)
return &TopK{k: k, heap: h}
}
func (t *TopK) Add(val int) {
if t.heap.Len() < t.k {
heap.Push(t.heap, val)
} else if val > (*t.heap)[0] {
heap.Pop(t.heap)
heap.Push(t.heap, val)
}
}
func (t *TopK) Get() []int {
res := make([]int, len(*t.heap))
copy(res, *t.heap)
return res
}
// 用法示例
// topk := NewTopK(3)
// for _, v := range []int{5, 1, 9, 3, 7, 8} { topk.Add(v) }
// topk.Get() // 返回最大3个元素
翻转二叉树
// 翻转二叉树（递归实现）
func invertTree[T any](root *BSTNode[T]) *BSTNode[T] {
if root == nil {
return nil
}
root.Left, root.Right = invertTree(root.Right), invertTree(root.Left)
return root
}
二叉树的最大深度
// 翻转二叉树（递归实现）
func invertTree[T any](root *BSTNode[T]) *BSTNode[T] {
if root == nil {
return nil
}
root.Left, root.Right = invertTree(root.Right), invertTree(root.Left)
return root
}
验证二叉查找树
// 验证二叉查找树（递归实现）
func isValidBST[T any](root *BSTNode[T], less func(a, b T) bool) bool {
var helper func(node *BSTNode[T], min, max *T) bool
helper = func(node *BSTNode[T], min, max *T) bool {
if node == nil {
return true
}
if min != nil && !less(*min, node.Val) {
return false
}
if max != nil && !less(node.Val, *max) {
return false
}
return helper(node.Left, min, &node.Val) && helper(node.Right, &node.Val, max)
}
return helper(root, nil, nil)
}
Path Sum(路径总和)
// 路径总和（递归实现）：判断是否存在从根到叶子的路径和等于 target
func hasPathSum[T int | int64](root *BSTNode[T], targetSum T) bool {
if root == nil {
return false
}
// 叶子节点
if root.Left == nil && root.Right == nil {
return root.Val == targetSum
}
left := hasPathSum(root.Left, targetSum-root.Val)
right := hasPathSum(root.Right, targetSum-root.Val)
return left || right
}
关于图的几个必知必会的代码实现
图
实现有向图、无向图、有权图、无权图的邻接矩阵和邻接表表示方法
// 邻接矩阵表示法（有向/无向、有权/无权图）
type MatrixGraph struct {
matrix [][]int // 权重，0表示无边
n int // 顶点数
directed bool // 是否有向
}
func NewMatrixGraph(n int, directed bool) *MatrixGraph {
return &MatrixGraph{
matrix: make([][]int, n),
n: n,
directed: directed,
}
}
func (g *MatrixGraph) AddEdge(u, v, weight int) {
g.matrix[u] = append(g.matrix[u], make([]int, g.n-len(g.matrix[u]))...)
g.matrix[v] = append(g.matrix[v], make([]int, g.n-len(g.matrix[v]))...)
g.matrix[u][v] = weight
if !g.directed {
g.matrix[v][u] = weight
}
}
// 邻接表表示法（有向/无向、有权/无权图）
type AdjListGraph struct {
adj [][]Edge
n int
directed bool
}
type Edge struct {
to int
weight int
}
func NewAdjListGraph(n int, directed bool) *AdjListGraph {
return &AdjListGraph{
adj: make([][]Edge, n),
n: n,
directed: directed,
}
}
func (g *AdjListGraph) AddEdge(u, v, weight int) {
g.adj[u] = append(g.adj[u], Edge{to: v, weight: weight})
if !g.directed {
g.adj[v] = append(g.adj[v], Edge{to: u, weight: weight})
}
}
实现图的深度优先搜索、广度优先搜索
// 图的深度优先搜索（DFS）
func DFS(g *AdjListGraph, start int, visited []bool, visit func(int)) {
visit(start)
visited[start] = true
for _, edge := range g.adj[start] {
if !visited[edge.to] {
DFS(g, edge.to, visited, visit)
}
}
}
// 图的广度优先搜索（BFS）
func BFS(g *AdjListGraph, start int, visit func(int)) {
visited := make([]bool, g.n)
queue := []int{start}
visited[start] = true
for len(queue) > 0 {
u := queue[0]
queue = queue[1:]
visit(u)
for _, edge := range g.adj[u] {
if !visited[edge.to] {
visited[edge.to] = true
queue = append(queue, edge.to)
}
}
}
}
// 用法示例
// visited := make([]bool, g.n)
// DFS(g, 0, visited, func(v int) { fmt.Println(v) })
// BFS(g, 0, func(v int) { fmt.Println(v) })
实现 Dijkstra 算法、A* 算法
// Dijkstra 算法和 A* 算法主要用于图的最短路径搜索：
// Dijkstra 算法：用于无负权边的图，计算单源点到所有其他节点的最短路径，常用于地图导航、网络路由等。
// A 算法*：用于有启发式信息的路径搜索，结合实际距离和估算距离，常用于游戏寻路、智能导航等场景，能更快找到起点到终点的最优路径。
// Dijkstra 算法（单源最短路径，邻接表实现）
func Dijkstra(g *AdjListGraph, start int) []int {
dist := make([]int, g.n)
for i := range dist {
dist[i] = 1<<31 - 1 // 初始化为无穷大
}
dist[start] = 0
visited := make([]bool, g.n)
for i := 0; i < g.n; i++ {
u := -1
for v := 0; v < g.n; v++ {
if !visited[v] && (u == -1 || dist[v] < dist[u]) {
u = v
}
}
if u == -1 || dist[u] == 1<<31-1 {
break
}
visited[u] = true
for _, edge := range g.adj[u] {
if dist[edge.to] > dist[u]+edge.weight {
dist[edge.to] = dist[u] + edge.weight
}
}
}
return dist
}
// A* 算法（伪代码，需自定义启发函数 h）
type AStarNode struct {
idx int
g int // 起点到当前节点的实际距离
f int // g + h
}
func AStar(g *AdjListGraph, start, goal int, h func(int) int) []int {
open := &MinHeap[*AStarNode]{less: func(a, b *AStarNode) bool { return a.f < b.f }}
heap.Init(open)
heap.Push(open, &AStarNode{idx: start, g: 0, f: h(start)})
cameFrom := make(map[int]int)
gScore := make(map[int]int)
gScore[start] = 0
for open.Len() > 0 {
curr := heap.Pop(open).(*AStarNode)
if curr.idx == goal {
// reconstruct path
path := []int{}
for u := goal; u != start; u = cameFrom[u] {
path = append([]int{u}, path...)
}
path = append([]int{start}, path...)
return path
}
for _, edge := range g.adj[curr.idx] {
tentativeG := curr.g + edge.weight
if gs, ok := gScore[edge.to]; !ok || tentativeG < gs {
cameFrom[edge.to] = curr.idx
gScore[edge.to] = tentativeG
heap.Push(open, &AStarNode{idx: edge.to, g: tentativeG, f: tentativeG + h(edge.to)})
}
}
}
return nil // 无路径
}
实现拓扑排序的 Kahn 算法、DFS 算法
// 拓扑排序的 Kahn 算法和 DFS 算法主要用于有向无环图（DAG）中的任务依赖排序。
// 它可以找出所有任务的执行顺序，使得每个任务都在其所有依赖任务之后执行。
// 常用于编译依赖、课程安排、项目调度等场景。
// Kahn 算法实现拓扑排序（适用于有向无环图 DAG）
func topoSortKahn(g *AdjListGraph) []int {
indegree := make([]int, g.n)
for u := 0; u < g.n; u++ {
for _, edge := range g.adj[u] {
indegree[edge.to]++
}
}
queue := []int{}
for i := 0; i < g.n; i++ {
if indegree[i] == 0 {
queue = append(queue, i)
}
}
res := []int{}
for len(queue) > 0 {
u := queue[0]
queue = queue[1:]
res = append(res, u)
for _, edge := range g.adj[u] {
indegree[edge.to]--
if indegree[edge.to] == 0 {
queue = append(queue, edge.to)
}
}
}
if len(res) != g.n {
return nil // 有环，无法拓扑排序
}
return res
}
// DFS 算法实现拓扑排序（适用于有向无环图 DAG）
func topoSortDFS(g *AdjListGraph) []int {
visited := make([]bool, g.n)
res := []int{}
var dfs func(u int)
dfs = func(u int) {
visited[u] = true
for _, edge := range g.adj[u] {
if !visited[edge.to] {
dfs(edge.to)
}
}
res = append(res, u)
}
for i := 0; i < g.n; i++ {
if !visited[i] {
dfs(i)
}
}
// 逆序即为拓扑序
for i, j := 0, len(res)-1; i < j; i, j = i+1, j-1 {
res[i], res[j] = res[j], res[i]
}
return res
}
Number of Islands(岛屿的个数) leetcode
// 岛屿的个数（DFS实现）
func numIslands(grid [][]byte) int {
if len(grid) == 0 || len(grid[0]) == 0 {
return 0
}
rows, cols := len(grid), len(grid[0])
count := 0
var dfs func(r, c int)
dfs = func(r, c int) {
if r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] != '1' {
return
}
grid[r][c] = '0' // 标记已访问
dfs(r+1, c)
dfs(r-1, c)
dfs(r, c+1)
dfs(r, c-1)
}
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
if grid[r][c] == '1' {
count++
dfs(r, c)
}
}
}
return count
}
有效的数独
// 有效的数独判断（LeetCode 36，9x9数独）
func isValidSudoku(board [][]byte) bool {
rows := [9][9]bool{}
cols := [9][9]bool{}
boxes := [9][9]bool{}
for i := 0; i < 9; i++ {
for j := 0; j < 9; j++ {
if board[i][j] == '.' {
continue
}
num := board[i][j] - '1' // 数字1~9映射为0~8
boxIdx := (i/3)*3 + j/3
if rows[i][num] || cols[j][num] || boxes[boxIdx][num] {
return false
}
rows[i][num] = true
cols[j][num] = true
boxes[boxIdx][num] = true
}
}
return true
}
// 算法详细解释
// 初始化三个标记数组
// rows[i][num]：第 i 行是否出现过数字 num+1
// cols[j][num]：第 j 列是否出现过数字 num+1
// boxes[boxIdx][num]：第 boxIdx 个 3x3 宫格是否出现过数字 num+1
// 遍历整个数独棋盘
// 对每个格子 (i, j)，如果是 '.'（空格），跳过。
// 计算数字 num = board[i][j] - '1'，将字符转为 0~8 的索引。
// 计算当前格子属于哪个 3x3 宫格：boxIdx = (i/3)*3 + j/3
// 检查是否重复
// 如果该数字在当前行、列或宫格已经出现过，则返回 false，说明数独无效。
// 标记已出现数字
// 将 rows[i][num]、cols[j][num]、boxes[boxIdx][num] 设为 true，表示该数字已出现。
// 全部遍历完无冲突则有效
// 如果没有发现重复，返回 true