离职电脑损坏赔偿引热议，算法题解LR字符串相邻字符交换规则

刚在网上看到一个帖子，一位网友吐槽说，自己在一家公司干了四年多，离职归还公司电脑时，因为电脑的四个角有磕碰痕迹，竟然被要求赔偿 275 块钱，把他气得够呛，直呼“真恶心”。

这事儿的关键，其实在于两个点：第一，这算正常磨损还是人为损坏？第二，入职时签署的资产协议里，折旧规则有没有白纸黑字写清楚。如果正常使用磨损也全算在员工头上，那确实不地道；但如果真是自己用得太“糙”，该承担的责任也不能全往外推。

在我看来，公司如果老拿这种“小钱”卡人，只会把员工的好感和信任一点点磨光。反过来，咱们打工人也得长个心眼，领设备时拍照留个底，交接时要有书面记录，一旦有争议就拿事实说话。

算法题：在 LR 字符串中交换相邻字符

昨晚十一点多，我在楼下抽烟（别学啊…），群里突然有人丢了个算法题过来。题目很简单：给你一个只包含 L 和 R 的字符串，规则有点像排队时有人插队——只要看到相邻的 "LR"，你就能把它交换成 "RL"。他问我，这玩意儿怎么写才能又快又稳，别一上来就用暴力模拟，那可太慢了。

我第一反应有点像处理线上故障时“数据包粘在一起”的感觉，你们懂吧？你以为数据是一个一个来的，结果它俩挤一块儿来了，解析就炸了。这道题也一样，你以为交换就是简单换一下，但实际上同一轮里有很多对 "LR" 可以同时发生，你得小心“重叠交换”。比如在 "LLRR" 里，如果你处理不好中间那对，指针走错了就可能重复交换或者漏掉。

先说最朴素的方法：模拟“一轮交换”（同一轮里，不能让刚交换出来的新字符继续参与本轮交换）。写法就是用指针 i 扫过去，遇到 "LR" 就输出 "RL" 并且 i += 2，否则就输出当前字符 i += 1。这很像我写协议解析时的“读够了就跳两个字节”的思路。

def one_round_swap(s: str) -> str:
    # 一轮：把不重叠的 "LR" 交换成 "RL"
    out = []
    i = 0
    n = len(s)
    while i < n:
        if i + 1 < n and s[i] == 'L' and s[i + 1] == 'R':
            out.append('R')
            out.append('L')
            i += 2
        else:
            out.append(s[i])
            i += 1
    return ''.join(out)

def simulate_until_stable(s: str, limit: int = 10_000) -> tuple[str, int]:
    # 一直做一轮轮交换，直到稳定（没有 "LR"）
    steps = 0
    for _ in range(limit):
        ns = one_round_swap(s)
        if ns == s:
            return s, steps
        s = ns
        steps += 1
    raise RuntimeError("可能是limit太小，或者输入不对劲")

但如果你要问“到底需要几轮才能稳定”，我可以告诉你，其实根本不需要一直模拟。你可以把这个过程想象成：每一轮，某个 R 最多只能往左移动 1 格（因为它只能和左边的 L 交换）。所以，最终的稳定形态其实就是所有的 R 都跑到了左边，所有的 L 都去了右边。那么，稳定所需要的最小轮数，就是看“最倒霉的那个 R，它左边一开始有多少个 L 需要跨过去”，取这个最大值就行了。

我们只需扫描一遍字符串：从左到右统计 L 的数量 cntL，每遇到一个 R，它需要跨过的 L 的数量就是当前的 cntL，取所有 R 中的最大值就是所需的最小轮数。另外，把这些 cntL 累加起来，其实得到的就是总交换次数（也就是逆序对的数量），有时候这个数据也挺有用的。

def min_rounds_to_stable(s: str) -> int:
    cntL = 0
    ans = 0
    for ch in s:
        if ch == 'L':
            cntL += 1
        elif ch == 'R':
            ans = max(ans, cntL)
        else:
            raise ValueError("只允许L/R")
    return ans

def total_swaps_needed(s: str) -> int:
    cntL = 0
    inv = 0
    for ch in s:
        if ch == 'L':
            cntL += 1
        elif ch == 'R':
            inv += cntL
        else:
            raise ValueError("只允许L/R")
    return inv

举个例子，"LLRLRR"。从头开始看，第一个 R 左边有 2 个 L，第二个 R 左边也有 2 个 L，最后一个 R 左边有 3 个 L。那么最小轮数就是 3。如果你真的用 simulate_until_stable 去跑，结果也是 3。这个看似简单的“交换相邻字符”问题，背后其实是一个并行版的冒泡排序思想。我当时困得要命，还在群里跟人解释了半天。

行了，不说了，我点的外卖到了，再不吃凉了又得挨老婆唠叨。这种生活里的小摩擦，还有Python 代码里的逻辑巧思，其实都挺有意思的，可以在开发者广场和大家多聊聊。