551_白板编程注意事项¶

Step 1: 理解题目（2-3分钟）
  - 重复题目，确认理解
  - 问清楚：输入格式？边界条件？返回什么？
  - 举例：用具体例子验证理解

Step 2: 思路分析（3-5分钟）
  - 先说暴力解法（展示基础能力）
  - 再说优化思路（展示进阶能力）
  - 说明时间/空间复杂度权衡
  - 获得面试官认可后再写代码！

Step 3: 写代码（10-15分钟）
  - 先写函数签名和注释
  - 从简单情况开始写
  - 大声说出正在做什么

Step 4: 测试验证（3-5分钟）
  - 用刚才举的例子手动走一遍
  - 测试边界：空输入、单元素、极大值

Step 5: 复杂度分析（2分钟）
  - 时间复杂度：O(?)
  - 空间复杂度：O(?)
  - 是否还有优化空间？

坑1: 题目没看完就开始写
  → 先停5秒，读完题，确认例子

坑2: 一言不发只写代码
  → 边写边说，让面试官跟上你的思路

坑3: 卡住了沉默很久
  → 主动说"我在想XXX，有点卡住了，能给点提示吗？"

坑4: 写完后不检查
  → 主动走测试用例，找bug

坑5: 忘记边界条件
  → 记住：空/None, 0, 负数, 单元素, 最大值

# 题目：给一个DNA序列，找出最长不含重复碱基的子串长度
# 例：ATCGATCG → 最长是 ATCG，长度4

def longest_unique_dna(dna: str) -> int:
    """
    思路：滑动窗口（双指针）
    - left, right两个指针定义当前窗口
    - 用set记录窗口内出现的碱基
    - right右移，如果遇到重复，left右移直到不重复

    时间: O(n)，空间: O(1)（最多4种碱基ACGT）
    """
    # 边界条件
    if not dna:
        return 0

    seen = set()
    left = 0
    max_len = 0

    for right in range(len(dna)):
        # 有重复，移动左指针
        while dna[right] in seen:
            seen.remove(dna[left])
            left += 1

        seen.add(dna[right])
        max_len = max(max_len, right - left + 1)

    return max_len

# 测试
print(longest_unique_dna("ATCGATCG"))  # 期望: 4
print(longest_unique_dna("AAAA"))       # 期望: 1
print(longest_unique_dna(""))           # 期望: 0
print(longest_unique_dna("A"))          # 期望: 1

# 题目：给一组基因组区间（外显子），合并重叠区间
# 例：[[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]]

def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
    """
    思路：排序后扫描
    1. 按起始位置排序
    2. 遍历，与当前合并区间比较是否重叠

    时间: O(n log n)，空间: O(n)
    """
    if not intervals:
        return []

    # 按起始位置排序
    intervals.sort(key=lambda x: x[0])

    merged = [intervals[0]]

    for start, end in intervals[1:]:
        last_end = merged[-1][1]

        if start <= last_end:
            # 有重叠，扩展当前区间
            merged[-1][1] = max(last_end, end)
        else:
            # 无重叠，新增区间
            merged.append([start, end])

    return merged

# 测试
print(merge_intervals([[1,3],[2,6],[8,10],[15,18]]))
# 期望: [[1, 6], [8, 10], [15, 18]]

print(merge_intervals([[1,4],[4,5]]))
# 期望: [[1, 5]]（端点相接也算重叠）

print(merge_intervals([]))
# 期望: []

开始时：
"让我先理解题目……您的意思是[重复题目]，对吗？"
"输入保证有效吗？需要考虑空输入？"

思考时：
"我的第一思路是暴力解，时间复杂度O(n²)……"
"可以用[数据结构/算法]优化到O(n)……"

写代码时：
"我先写函数签名……"
"这里我用了[方法]，因为……"

测试时：
"让我用[1,2,3]验证一下……走到第二步是……"
"边界条件：空数组……"

结束时：
"时间复杂度O(n log n)，空间O(n)，还能进一步优化……"

常见时间复杂度从好到差：
  O(1) → O(log n) → O(n) → O(n log n) → O(n²) → O(2^n)

常用数据结构选择：
  需要快速查找？→ set/dict（哈希）
  需要有序？   → sorted list / 堆
  需要最大最小？→ heap（heapq）
  树形结构？   → 递归/BFS/DFS
  滑动窗口？   → 双指针

常见生信编程题类型：
  1. DNA/蛋白质序列处理（字符串）
  2. 基因组区间操作（区间合并/交集）
  3. 树形数据（物种树）
  4. 图算法（代谢通路）
  5. 矩阵操作（表达量矩阵）