1 minute read

一、闭区间 vs 半开区间

  • 数组相关的推荐画数轴节点图。涉及node的问题，画箭头图也会有很大帮助。画图经常能发现没意识到的问题，有时候想不到的边界情况也可以通过随手瞎画有灵感。

二、二分法与死循环

三、中点/中位数奇偶分支

  • 需要“左中点/右中点”时，初始化 fast 指针区别处理。

  • 例子（链表找左中点以做均衡切分）

    slow = head
fast = head.next    
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

四、空数组

  • 避免对 null 或空数组进行操作；任何访问前都要判断是否为空。
  # 示例：求数组中的最大值
  def findMax(a):
      if a == null or len(a) == 0:    # 判空避免越界
          return None                 # 或返回题目要求的默认值
      maxv = a[0]
      for x in a:
          if x > maxv:
              maxv = x
      return maxv

五、数值溢出

  • 在 32 位边界附近用 64 位或字符串；乘法前做阈值判断。

  • 例子（安全乘积）

    res = 1
for x in nums:
    if abs(res) > LIMIT // max(1, abs(x)):
        return overflow_behavior
    res *= x
return res

六、负数取模统一到 [0..k-1]

  • mod = ((x % k) + k) % k

  • 例子（前缀取模计数）

    s = 0; cnt = {0:1}; ans = 0
for x in a:
    s = ((s + x) % k + k) % k
    ans += cnt.get(s, 0)
    cnt[s] = cnt.get(s, 0) + 1
return ans

七、浮点比较与 eps

  • 比较用 abs(a-b) <= eps；浮点二分用迭代次数或区间长度终止。

  • 例子（平方根近似）

    l = 0.0; r = max(1.0, x)
repeat 100 times:
    m = (l + r) / 2
    if m*m >= x: r = m
    else: l = m
return l

八、快速幂的负指数与最小整型

  • n < 0 时：x = 1/x；n = -(long)n（避免最小整型取负溢出）。

  • 例子（快速幂）

    if n < 0:
    x = 1 / x
    n = -(long)n
res = 1
while n > 0:
    if n & 1: res *= x
    x *= x
    n >>= 1
return res

九、除数为零

  • 整除前判分母非 0；

  • 例子（安全整除）

    if denom == 0: return special_case
q = numer // denom

十、顺序稳定性与比较器

  • 需要稳定输出时，使用稳定结构（队列、稳定排序）；自定义比较器要自洽。

  • 例子（优先队列 tie-break）

    # 键一：频率降序；键二：值升序
push items with ( -freq, value )
# 这样堆顶在频率相同下保持值小者优先

十一、BFS 分层与“层末更新”

  • 每层用当前队列大小做快照；入队前标记 visited，避免重复入队。

  • 例子（最短层数）

    step = 0
push(start); visited[start] = true
while queue not empty:
    size = queue.size()
    repeat size times:
        u = pop()
        if u is target: return step
        for v in neighbors(u):
            if not visited[v]:
                visited[v] = true
                push(v)
    step += 1

十二、网格越界与访问标记时机

  • 判断 (0 <= x < n) 和 (0 <= y < m)；入队/入栈前立即标记。

  • 例子（DFS 岛屿面积）

    def dfs(x, y):
    if x<0 or x>=n or y<0 or y>=m: return 0
    if vis[x][y] or grid[x][y]==0: return 0
    vis[x][y] = true
    area = 1
    for (dx,dy) in 4-neighbors:
        area += dfs(x+dx, y+dy)
    return area

You May Also Enjoy