8.13 TikTok OA 又抽到原题：CodeSignal 70 分钟 4 题全过

OA 概况

• 平台：CodeSignal
• 题量 / 时长：70 分钟 4 道 coding
• 结果：半小时做完，全部通过 ✅

第一题：连续三个数恰好两个相等

遍历数组，每次看连续三个数，判断是不是恰好两个相等。用 if 把三种情况列出来就行：a == b != c、a == c != b、b == c != a。O(n)。

def count_exactly_two_equal(nums):
    count = 0
    for a, b, c in zip(nums, nums[1:], nums[2:]):
        if (a == b != c) or (a == c != b) or (b == c != a):
            count += 1
    return count

第二题：摧毁房子求剩余段数

思路：倒着做最方便。先算出所有房子都被摧毁后剩下的状态，然后从最后一个被摧毁的房子开始，逐个「恢复」：

• 左右邻居都在：两段连成一段，段数减 1。
• 左右只有一边在：接到已有的段上，段数不变。
• 左右都不在：自成一段，段数加 1。

把每次恢复前的段数存下来，最后反转数组就是答案。

def segments_after_each_destroy(houses, queries):
    """houses: 房子坐标；queries: 依次被摧毁的房子。返回每次摧毁后的段数"""
    alive = set(houses) - set(queries)
    count = sum(1 for h in alive if h - 1 not in alive)   # 每段的起点数 = 段数
    res = []
    for q in reversed(queries):
        res.append(count)
        left, right = q - 1 in alive, q + 1 in alive
        if left and right:
            count -= 1
        elif not left and not right:
            count += 1
        alive.add(q)
    return res[::-1]

第三题：带修改的 a + b 求和计数

维护 a、b 两个数组的频率表：

• 查询类型 1（给定 x）：遍历 a 的每个值，看 b 里有多少个 x - a[i]，累加次数。
• 查询类型 0（修改 a[i]）：更新 a 的值，同时更新 a 的频率表（旧值减一，新值加一）。

题目不要求最优，每次查询 O(n) 遍历就行。

from collections import Counter

def process_queries(a, b, queries):
    a = list(a)
    ca, cb = Counter(a), Counter(b)
    res = []
    for q in queries:
        if q[0] == 0:                    # [0, i, x]：把 a[i] 改成 x
            _, i, x = q
            ca[a[i]] -= 1
            a[i] = x
            ca[x] += 1
        else:                            # [1, x]：统计 a[i] + b[j] == x 的对数
            x = q[1]
            res.append(sum(cnt * cb[x - v] for v, cnt in ca.items() if cnt))
    return res

第四题：矩阵边框排序

从外到内一层层处理。对于第 k 层（k 从 0 开始），先按顺时针顺序取出这一圈的元素：上边从左到右，右边从上到下，下边从右到左，左边从下到上。排序后再按同样的顺序填回去。

一直处理到第 floor((n-1)/2) 层，每层 O(n) 取出和填回，整体 O(n² log n) 足够。

def sort_borders(matrix):
    n = len(matrix)
    m = [row[:] for row in matrix]
    for k in range((n + 1) // 2):
        lo, hi = k, n - 1 - k
        if lo == hi:
            continue                      # 奇数阶的中心只有一个元素
        coords = ([(lo, c) for c in range(lo, hi)] +        # 上边：左 → 右
                  [(r, hi) for r in range(lo, hi)] +        # 右边：上 → 下
                  [(hi, c) for c in range(hi, lo, -1)] +    # 下边：右 → 左
                  [(r, lo) for r in range(hi, lo, -1)])     # 左边：下 → 上
        vals = sorted(m[r][c] for r, c in coords)
        for (r, c), v in zip(coords, vals):
            m[r][c] = v
    return m