812 字
2 分钟
算法题
本文整理了面试中常见的算法题型，涵盖数组、链表、树、堆、动态规划等核心考点。
Tip
复杂度速查表
一、顺时针旋转矩阵
1.1 题目描述
给定一个 n×n 的矩阵，顺时针旋转 90 度。
1.2 解题思路
对于旋转后的位置 (i, j)，变换规律是：
- 原位置
(n-1-j, i)→ 新位置(i, j)
也可以分两步完成：
- 按主对角线翻转
- 按水平中线翻转
1.3 代码实现
// 方法一：原地旋转func rotate(matrix [][]int) { n := len(matrix) // 按主对角线翻转 for i := 0; i < n; i++ { for j := i + 1; j < n; j++ { matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j] } } // 按水平中线翻转 for i := 0; i < n/2; i++ { for j := 0; j < n; j++ { matrix[i][j], matrix[n-1-i][j] = matrix[n-1-i][j], matrix[i][j] } }}
// 方法二：公式法（需要额外空间）func rotate2(matrix [][]int) { n := len(matrix) result := make([][]int, n) for i := 0; i < n; i++ { result[i] = make([]int, n) } for i := 0; i < n; i++ { for j := 0; j < n; j++ { result[j][n-1-i] = matrix[i][j] } } copy(matrix, result)}1.4 复杂度分析
- 时间复杂度：O(n²)
- 空间复杂度：O(1)（原地）或 O(n²)（额外空间）
二、合并区间
2.1 题目描述
给出一个区间的集合，合并所有重叠的区间。
2.2 解题思路
- 按区间的起始位置排序
- 遍历区间，如果当前区间起始 ≤ 上一个区间结束，则合并
- 否则开始新的区间
2.3 代码实现
type Interval struct { Start int End int}
func merge(intervals []Interval) []Interval { if len(intervals) == 0 { return intervals }
// 按起始位置排序 sort.Slice(intervals, func(i, j int) bool { return intervals[i].Start < intervals[j].Start })
result := []Interval{intervals[0]}
for i := 1; i < len(intervals); i++ { last := &result[len(result)-1] if intervals[i].Start <= last.End { // 重叠，合并（取较大结束位置） if intervals[i].End > last.End { last.End = intervals[i].End } } else { // 不重叠，直接添加 result = append(result, intervals[i]) } }
return result}2.4 复杂度分析
- 时间复杂度：O(n log n)（排序）
- 空间复杂度：O(1)（原地）或 O(n)（结果存储）
三、堆排序
3.1 堆的基本概念
堆是一棵完全二叉树，根据堆序性质分为：
- 大根堆：父节点 ≥ 子节点
- 小根堆：父节点 ≤ 子节点
堆的物理存储通常用数组，节点关系：
- 父节点：
(i-1)/2 - 左子节点：
2*i + 1 - 右子节点：
2*i + 2
3.2 代码实现
func heapSort(arr []int) { n := len(arr)
// 构建大根堆 for i := n/2 - 1; i >= 0; i-- { heapify(arr, n, i) }
// 逐个取出堆顶元素 for i := n - 1; i > 0; i-- { arr[0], arr[i] = arr[i], arr[0] // 交换堆顶和末尾 heapify(arr, i, 0) // 调整堆 }}
func heapify(arr []int, n, i int) { largest := i left := 2*i + 1 right := 2*i + 2
if left < n && arr[left] > arr[largest] { largest = left } if right < n && arr[right] > arr[largest] { largest = right }
if largest != i { arr[i], arr[largest] = arr[largest], arr[i] heapify(arr, n, largest) }}3.3 复杂度分析
- 时间复杂度：O(n log n)
- 空间复杂度：O(1)
四、获取第 k 大的元素
4.1 方法一：排序后取第 k 大
func findKthLargest1(nums []int, k int) int { sort.Ints(nums) return nums[len(nums)-k]}- 时间复杂度：O(n log n)
4.2 方法二：快速选择（基于快速排序）
func findKthLargest2(nums []int, k int) int { return quickSelect(nums, 0, len(nums)-1, len(nums)-k)}
func quickSelect(nums []int, left, right, k int) int { if left == right { return nums[left] }
pivotIndex := left + rand.Intn(right-left+1) pivotIndex = partition(nums, left, right, pivotIndex)
if k == pivotIndex { return nums[k] } else if k < pivotIndex { return quickSelect(nums, left, pivotIndex-1, k) } else { return quickSelect(nums, pivotIndex+1, right, k) }}
func partition(nums []int, left, right, pivotIndex int) int { pivot := nums[pivotIndex] nums[pivotIndex], nums[right] = nums[right], nums[pivotIndex] storeIndex := left
for i := left; i < right; i++ { if nums[i] < pivot { nums[storeIndex], nums[i] = nums[i], nums[storeIndex] storeIndex++ } } nums[right], nums[storeIndex] = nums[storeIndex], nums[right] return storeIndex}- 时间复杂度：O(n)（期望），最坏 O(n²)
- 空间复杂度：O(1)
4.3 方法三：堆
func findKthLargest3(nums []int, k int) int { // 小根堆，堆顶是当前第 k 大的元素 h := &IntHeap{} heap.Init(h)
for _, num := range nums { heap.Push(h, num) if h.Len() > k { heap.Pop(h) } }
return (*h)[0]}
type IntHeap []int
func (h IntHeap) Len() int { return len(h) }func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] } // 小根堆func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.(int)) }func (h *IntHeap) Pop() interface{} { old := *h n := len(old) x := old[n-1] *h = old[:n-1] return x}- 时间复杂度：O(n log k)
- 空间复杂度：O(k)
五、更多经典算法题
5.1 两数之和
// Hash 表解法func twoSum(nums []int, target int) []int { m := make(map[int]int) for i, num := range nums { if j, ok := m[target-num]; ok { return []int{j, i} } m[num] = i } return nil}5.2 合并两个有序链表
func mergeTwoLists(l1, l2 *ListNode) *ListNode { dummy := &ListNode{} cur := dummy
for l1 != nil && l2 != nil { if l1.Val < l2.Val { cur.Next = l1 l1 = l1.Next } else { cur.Next = l2 l2 = l2.Next } cur = cur.Next }
if l1 != nil { cur.Next = l1 } else { cur.Next = l2 }
return dummy.Next}5.3 验证二叉搜索树
func isValidBST(root *TreeNode) bool { return helper(root, math.MinInt64, math.MaxInt64)}
func helper(node *TreeNode, min, max int) bool { if node == nil { return true } if node.Val <= min || node.Val >= max { return false } return helper(node.Left, min, node.Val) && helper(node.Right, node.Val, max)}六、二叉树层序遍历
6.1 题目描述
给定二叉树，返回其节点值的层序遍历结果（从上到下，从左到右）。
6.2 代码实现
func levelOrder(root *TreeNode) [][]int { if root == nil { return nil }
result := [][]int{} queue := []*TreeNode{root}
for len(queue) > 0 { levelSize := len(queue) level := []int{}
for i := 0; i < levelSize; i++ { node := queue[0] queue = queue[1:] level = append(level, node.Val)
if node.Left != nil { queue = append(queue, node.Left) } if node.Right != nil { queue = append(queue, node.Right) } } result = append(result, level) }
return result}- 时间复杂度：O(n)
- 空间复杂度：O(n)
七、LRU 缓存
7.1 题目描述
实现一个 LRU（最近最少使用）缓存，支持 get 和 put 操作，时间复杂度 O(1)。
7.2 解题思路
使用哈希表 + 双向链表的组合：
- 哈希表：O(1) 查找
- 双向链表：O(1) 插入/删除
7.3 代码实现
type LRUCache struct { capacity int cache map[int]*DListNode head *DListNode tail *DListNode}
type DListNode struct { key, value int prev, next *DListNode}
func Constructor(capacity int) LRUCache { head, tail := &DListNode{}, &DListNode{} head.next = tail tail.prev = head return LRUCache{ capacity: capacity, cache: make(map[int]*DListNode), head: head, tail: tail, }}
func (l *LRUCache) Get(key int) int { if node, ok := l.cache[key]; ok { l.moveToFront(node) return node.value } return -1}
func (l *LRUCache) Put(key, value int) { if node, ok := l.cache[key]; ok { node.value = value l.moveToFront(node) return }
if len(l.cache) >= l.capacity { // 删除最少使用的节点（链表尾部） delete(l.cache, l.tail.prev.key) l.removeNode(l.tail.prev) }
node := &DListNode{key: key, value: value} l.cache[key] = node l.addToFront(node)}
func (l *LRUCache) moveToFront(node *DListNode) { l.removeNode(node) l.addToFront(node)}
func (l *LRUCache) removeNode(node *DListNode) { node.prev.next = node.next node.next.prev = node.prev}
func (l *LRUCache) addToFront(node *DListNode) { node.next = l.head.next node.prev = l.head l.head.next.prev = node l.head.next = node}八、动态规划
8.1 最长递增子序列
func lengthOfLIS(nums []int) int { if len(nums) == 0 { return 0 }
// dp[i] 表示以 nums[i] 结尾的最长递增子序列长度 dp := make([]int, len(nums)) for i := range dp { dp[i] = 1 }
maxLen := 1 for i := 1; i < len(nums); i++ { for j := 0; j < i; j++ { if nums[i] > nums[j] { dp[i] = max(dp[i], dp[j]+1) } } maxLen = max(maxLen, dp[i]) }
return maxLen}
func max(a, b int) int { if a > b { return a } return b}- 时间复杂度：O(n²)
- 空间复杂度：O(n)
8.2 零钱兑换
func coinChange(coins []int, amount int) int { // dp[i] 表示凑成金额 i 需要的最少硬币数 dp := make([]int, amount+1) for i := 1; i <= amount; i++ { dp[i] = amount + 1 // 初始化为不可能的值 } dp[0] = 0
for i := 1; i <= amount; i++ { for _, coin := range coins { if coin <= i { dp[i] = min(dp[i], dp[i-coin]+1) } } }
if dp[amount] > amount { return -1 } return dp[amount]}
func min(a, b int) int { if a < b { return a } return b}- 时间复杂度：O(amount × n)
- 空间复杂度：O(amount)
九、参考
参考
支持与分享
如果这篇文章对你有帮助，欢迎支持作者或分享给更多人
部分信息可能已经过时
相关文章 智能推荐
1
MySQL 面试题
面试 面试中常见的 MySQL 题目——索引原理、事务隔离级别、锁机制、日志系统、SQL 优化等知识点整理。
2
系统设计面试题
面试 面试中常见的系统设计题目——短 URL 设计、Feed 流设计、延迟任务队列、秒杀系统等高频题型的分析与解答。
3
Redis 面试题
面试 面试中常见的 Redis 题目——数据结构、持久化、集群方案、缓存穿透/击穿/雪崩、分布式锁等知识点整理。
4
项目经验面试题
面试 面试中关于项目经验的典型问题与作答思路整理。
5
计算机基础面试题
面试 面试中常见的计算机基础题目——网络七层模型、进程与线程、内存管理、系统调用等核心知识点整理。