Algorithm Templates

算法模板 💡 Algorithm Templates

常用算法代码模板，可以直接复制使用。

Common algorithm code templates, ready to copy and use.

---

目录 Table of Contents

• 数组 Array
• 链表 Linked List
• 双指针 Two Pointers
• 滑动窗口 Sliding Window
• 哈希表 Hash Table
• 栈 Stack
• 队列 Queue
• 二分查找 Binary Search
• 排序 Sorting
• 递归 Recursion

---

数组 Array

数组遍历 Array Traversal

// 正向遍历 Forward traversal
for i in 0..<nums.count {
    print(nums[i])
}

// 反向遍历 Backward traversal
for i in stride(from: nums.count - 1, through: 0, by: -1) {
    print(nums[i])
}

// 使用 enumerated
for (index, value) in nums.enumerated() {
    print("\(index): \(value)")
}

原地修改数组 In-place Array Modification

func modifyArray(_ nums: inout [Int]) {
    var writeIndex = 0
    
    for readIndex in 0..<nums.count {
        if shouldKeep(nums[readIndex]) {
            nums[writeIndex] = nums[readIndex]
            writeIndex += 1
        }
    }
    
    // 返回新长度
    return writeIndex
}

---

链表 Linked List

链表定义 ListNode Definition

public class ListNode {
    public var val: Int
    public var next: ListNode?
    public init(_ val: Int) {
        self.val = val
        self.next = nil
    }
}

链表遍历 List Traversal

func traverse(_ head: ListNode?) {
    var current = head
    while current != nil {
        print(current!.val)
        current = current!.next
    }
}

虚拟头节点技巧 Dummy Head Technique

func processLinkedList(_ head: ListNode?) -> ListNode? {
    let dummy = ListNode(0)
    dummy.next = head
    
    var current = dummy
    while current.next != nil {
        // 处理逻辑
        current = current.next!
    }
    
    return dummy.next
}

快慢指针 Fast-Slow Pointers

func findMiddle(_ head: ListNode?) -> ListNode? {
    var slow = head
    var fast = head
    
    while fast?.next != nil {
        slow = slow?.next
        fast = fast?.next?.next
    }
    
    return slow
}

---

双指针 Two Pointers

对撞指针 Two Pointers (Opposite Direction)

func twoPointers(_ nums: [Int]) {
    var left = 0
    var right = nums.count - 1
    
    while left < right {
        // 处理逻辑
        if condition {
            left += 1
        } else {
            right -= 1
        }
    }
}

快慢指针 Fast-Slow Pointers

func fastSlowPointers(_ nums: [Int]) {
    var slow = 0
    var fast = 0
    
    while fast < nums.count {
        if shouldMove {
            nums[slow] = nums[fast]
            slow += 1
        }
        fast += 1
    }
    
    return slow
}

---

滑动窗口 Sliding Window

固定大小窗口 Fixed-size Window

func fixedWindow(_ nums: [Int], _ k: Int) -> Int {
    var windowSum = 0
    
    // 初始化窗口
    for i in 0..<k {
        windowSum += nums[i]
    }
    
    var maxSum = windowSum
    
    // 滑动窗口
    for i in k..<nums.count {
        windowSum = windowSum - nums[i - k] + nums[i]
        maxSum = max(maxSum, windowSum)
    }
    
    return maxSum
}

可变大小窗口 Variable-size Window

func variableWindow(_ s: String) -> Int {
    let chars = Array(s)
    var left = 0
    var maxLength = 0
    var seen = Set<Character>()
    
    for right in 0..<chars.count {
        while seen.contains(chars[right]) {
            seen.remove(chars[left])
            left += 1
        }
        
        seen.insert(chars[right])
        maxLength = max(maxLength, right - left + 1)
    }
    
    return maxLength
}

---

哈希表 Hash Table

基本用法 Basic Usage

// Dictionary (键值对)
var dict = [Int: Int]()
dict[key] = value
if let value = dict[key] {
    print(value)
}

// Set (集合)
var set = Set<Int>()
set.insert(value)
if set.contains(value) {
    print("Found")
}

频率统计 Frequency Count

func countFrequency(_ nums: [Int]) -> [Int: Int] {
    var freq = [Int: Int]()
    
    for num in nums {
        freq[num, default: 0] += 1
    }
    
    return freq
}

---

栈 Stack

栈实现 Stack Implementation

// 使用数组实现栈
var stack = [Int]()

// 入栈 Push
stack.append(element)

// 出栈 Pop
if let top = stack.popLast() {
    print(top)
}

// 查看栈顶 Peek
if let top = stack.last {
    print(top)
}

// 判空 Is Empty
let isEmpty = stack.isEmpty

单调栈 Monotonic Stack

func nextGreaterElement(_ nums: [Int]) -> [Int] {
    var result = Array(repeating: -1, count: nums.count)
    var stack = [Int]() // 存储索引
    
    for i in 0..<nums.count {
        while !stack.isEmpty && nums[i] > nums[stack.last!] {
            let index = stack.removeLast()
            result[index] = nums[i]
        }
        stack.append(i)
    }
    
    return result
}

---

二分查找 Binary Search

标准二分查找 Standard Binary Search

func binarySearch(_ nums: [Int], _ target: Int) -> Int {
    var left = 0
    var right = nums.count - 1
    
    while left <= right {
        let mid = left + (right - left) / 2
        
        if nums[mid] == target {
            return mid
        } else if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    
    return -1
}

左边界查找 Left Boundary

func leftBound(_ nums: [Int], _ target: Int) -> Int {
    var left = 0
    var right = nums.count
    
    while left < right {
        let mid = left + (right - left) / 2
        
        if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid
        }
    }
    
    return left
}

---

排序 Sorting

快速排序 Quick Sort

func quickSort(_ nums: inout [Int], _ left: Int, _ right: Int) {
    if left >= right { return }
    
    let pivot = partition(&nums, left, right)
    quickSort(&nums, left, pivot - 1)
    quickSort(&nums, pivot + 1, right)
}

func partition(_ nums: inout [Int], _ left: Int, _ right: Int) -> Int {
    let pivot = nums[right]
    var i = left
    
    for j in left..<right {
        if nums[j] < pivot {
            nums.swapAt(i, j)
            i += 1
        }
    }
    
    nums.swapAt(i, right)
    return i
}

---

递归 Recursion

递归模板 Recursion Template

func recursion(_ params: Parameters) -> ReturnType {
    // 1. 终止条件
    if baseCase {
        return baseResult
    }
    
    // 2. 处理当前层逻辑
    // process current logic
    
    // 3. 递归调用
    let result = recursion(newParams)
    
    // 4. 返回结果
    return result
}

回溯模板 Backtracking Template

func backtrack(_ path: inout [Int], _ choices: [Int]) {
    // 终止条件
    if satisfiesCondition(path) {
        result.append(path)
        return
    }
    
    // 遍历所有选择
    for choice in choices {
        // 做选择
        path.append(choice)
        
        // 递归
        backtrack(&path, getNextChoices(choice))
        
        // 撤销选择
        path.removeLast()
    }
}

---

时间复杂度速查 Time Complexity Cheat Sheet

操作 Operation	时间复杂度 Time
数组访问 Array Access	O(1)
数组查找 Array Search	O(n)
数组插入/删除 Array Insert/Delete	O(n)
哈希表插入/查找 Hash Table	O(1) avg
链表访问 Linked List Access	O(n)
链表插入/删除 Linked List Insert/Delete	O(1)
栈/队列 Stack/Queue Push/Pop	O(1)
二分查找 Binary Search	O(log n)
快速排序 Quick Sort	O(n log n) avg
归并排序 Merge Sort	O(n log n)

---

← 返回首页 Back to Home