10.2 TikTok 27 Intern OA 面经：机器人位置、模式匹配 KMP、反弹对角线排序、策略改写最大利润

TikTok 2027 Intern OA 四道题，整体没什么挑战，coding 熟练就能一次过。

1. 机器人最终位置

把机器人的当前位置看成一个整数，初始为 0。遍历 commands 字符串，遇到 L 位置减 1，遇到 R 位置加 1。

遍历结束后：最终位置 < 0 返回 "L"，> 0 返回 "R"，= 0 说明回到起点，返回空字符串。时间 O(n)，空间 O(1)。

def final_direction(commands):
    pos = commands.count("R") - commands.count("L")
    return "R" if pos > 0 else "L" if pos < 0 else ""

2. 比较数组上的 Pattern 计数

先把原数组相邻元素之间的大小关系转换成一个比较数组：后一个更大记 1，相等记 0，更小记 −1。问题就转化成统计 pattern 在比较数组中出现了多少次。

可以逐个位置直接匹配，也可以用 KMP 在线性时间内统计所有匹配：先构造 pattern 的前缀函数，再遍历比较数组进行匹配。时间 O(n + m)，空间 O(m)。

def count_pattern_matches(nums, pattern):
    cmp = [(b > a) - (b < a) for a, b in zip(nums, nums[1:])]
    m = len(pattern)
    if m == 0:
        return 0
    fail = [0] * m                       # KMP 前缀函数
    j = 0
    for i in range(1, m):
        while j and pattern[i] != pattern[j]:
            j = fail[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
        fail[i] = j
    count = j = 0
    for x in cmp:
        while j and x != pattern[j]:
            j = fail[j - 1]
        if x == pattern[j]:
            j += 1
        if j == m:
            count += 1
            j = fail[j - 1]
    return count

3. 按反弹对角线权重排序第一列

计算第一列每个元素对应的 **bouncing diagonal（反弹对角线）**的权重：从 (r, 0) 出发，每向右移动一列，行方向向上走，碰到边界就反弹。在 n×n 矩阵里，第 c 列对应的行就是 abs(r − c)。

遍历每个起点，把路径上的元素累加得到权重。把每个元素存成 (权重, 第一列元素值)，按权重升序排序，权重相同时按元素值升序，最后取出排好序的第一列元素即可。时间 O(n²)，排序 O(n log n)。

def sort_first_column_by_bounce(matrix):
    n, m = len(matrix), len(matrix[0])
    items = []
    for r in range(n):
        row, step, weight = r, -1, 0     # 先往上走
        for c in range(m):
            weight += matrix[row][c]
            if n > 1:
                if not 0 <= row + step < n:
                    step = -step         # 碰到边界反弹
                row += step
        items.append((weight, matrix[r][0]))
    return [v for _, v in sorted(items)]

上面用模拟写法，对非方阵也适用；n×n 方阵里可以直接用 matrix[abs(r - c)][c]。

4. 修改买卖策略求最大利润

先计算原始策略下的总利润：strategy 为 −1 表示买入，利润贡献 −price；为 1 表示卖出，贡献 +price；0 没有贡献。

然后枚举所有长度为 k 的连续区间：修改后区间的前一半全部变成 0，后一半全部变成 1。为了快速计算每个区间修改前后的利润，分别建立「原始利润」和「价格」的前缀和：

修改前的区间利润，由原始利润前缀和求出。
修改后只有后一半的价格产生正利润，由价格前缀和求出。

计算每个区间带来的利润增量，取最大值。题目允许不修改，所以最大增量的初始值是 0。

def max_profit_with_one_change(prices, strategy, k):
    n, half = len(prices), k // 2
    pp, ps = [0], [0]                    # 原始利润前缀和、价格前缀和
    for p, s in zip(prices, strategy):
        pp.append(pp[-1] + p * s)
        ps.append(ps[-1] + p)
    best_gain = 0                        # 允许不修改
    for i in range(n - k + 1):
        before = pp[i + k] - pp[i]
        after = ps[i + k] - ps[i + half]
        best_gain = max(best_gain, after - before)
    return pp[n] + best_gain

时间 O(n)，空间 O(n)。