computer-science-tutor

计算机科学学科专家

为计算机科学学习、问题求解和笔记创建提供专业知识。

主题范围

mindmap
  root((Computer Science))
    Algorithms
      Sorting
      Searching
      Graph Algorithms
      Dynamic Programming
    Data Structures
      Arrays & Lists
      Trees & Graphs
      Hash Tables
      Heaps & Queues
    Systems
      Operating Systems
      Networks
      Databases
    Theory
      Complexity
      Automata
      Computability

---

快速参考链接

• **算法模式：**参见 algorithms.md
• **数据结构：**参见 data-structures.md
• **Big-O 分析：**参见 big-o.md

---

图示模式

算法流程图

flowchart TB
    A[Start] --> B{Condition?}
    B -->|Yes| C[Process A]
    B -->|No| D[Process B]
    C --> E[End]
    D --> E

数据结构可视化

graph TB
    subgraph "Binary Search Tree"
        A((8)) --> B((3))
        A --> C((10))
        B --> D((1))
        B --> E((6))
        C --> F((14))
    end

时序图（API/流程）

sequenceDiagram
    Client->>Server: Request
    Server->>Database: Query
    Database-->>Server: Results
    Server-->>Client: Response

---

问题求解框架

算法设计步骤

1. 理解 - 明确输入、输出和约束条件
2. 示例 - 手动推演 2-3 个示例
3. 蛮力法 - 从直观的 O(n²) 或 O(n!) 方案入手
4. 优化 - 应用各种模式（双指针、滑动窗口等）
5. 实现 - 编写清晰、模块化的代码
6. 测试 - 测试边界情况（空、单个元素、重复元素）

常见模式

模式	适用场景	示例
双指针	已排序数组，查找数对	两数之和（已排序）
滑动窗口	连续子数组	最大和子数组
哈希表	需要 O(1) 查找	两数之和（未排序）
BFS	最短路径（无权图）	迷宫求解
DFS	探索所有路径	排列
二分查找	已排序数据，查找元素	搜索旋转数组
动态规划	重叠子问题	斐波那契、背包问题

---

代码模板模式

二分查找

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1  # Not found

BFS 模板

from collections import deque

def bfs(start, target):
    queue = deque([start])
    visited = {start}
    while queue:
        node = queue.popleft()
        if node == target:
            return True
        for neighbor in get_neighbors(node):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return False

DFS 模板

def dfs(node, visited):
    if node in visited:
        return
    visited.add(node)
    # Process node
    for neighbor in get_neighbors(node):
        dfs(neighbor, visited)

---

复杂度速查

操作	数组	链表	哈希表	BST（平均）
访问	O(1)	O(n)	O(1)	O(log n)
查找	O(n)	O(n)	O(1)	O(log n)
插入	O(n)	O(1)	O(1)	O(log n)
删除	O(n)	O(1)	O(1)	O(log n)