在 LeetCode 上做脑筋急转弯

---

这篇文章主要包含以下内容：

• #292 - Nim 游戏
• #319 - 灯泡开关
• #521 - 最长特殊序列 Ⅰ
• #777 - 在LR字符串中交换相邻字符
• #1033 - 移动石子直到连续
• #1227 - 飞机座位分配概率
• #1503 - 所有蚂蚁掉下来前的最后一刻

#292 - Nim 游戏

你和你的朋友，两个人一起玩 Nim 游戏：

• 桌子上有一堆石头。
• 你们轮流进行自己的回合，你作为先手。
• 每一回合，轮到的人拿掉 1 - 3 块石头。
• 拿掉最后一块石头的人就是获胜者。

假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。

由于每个人最多只能拿 3 块石头，那么如果桌上还剩 4 块的话，一个人是一定不能一次拿完的。那么只要在一个人拿 x 块石头之后，另一个人继续拿 4 - x 块，就能保证一开始拿的那个人一定不可能赢。

因此，因为你作为先手，如果桌上的石头一开始就是 4 的倍数，那么你就是一开始拿的人，也就是说你会输；如果不是 4 的倍数，你就可以拿 n % 4 块，那么你的对手就不可能赢，因此你会获得胜利。

所以胜利与否只取决于桌上原始的石头数。解法如下：

class Solution:
    def canWinNim(self, n: int) -> bool:
        return n % 4 != 0

#319 - 灯泡开关

初始时有 n 个灯泡关闭。

第 1 轮，你打开所有的灯泡。 第 2 轮，每两个灯泡你关闭一次。 第 3 轮，每三个灯泡切换一次开关（如果关闭则开启，如果开启则关闭）。

第 i 轮，每 i 个灯泡切换一次开关。 对于第 n 轮，你只切换最后一个灯泡的开关。

找出 n 轮后有多少个亮着的灯泡。

首先，初始时每个灯泡都是灭的。

那么，什么时候灯泡会转变一次状态呢？由题意，对于第 i 轮，如果 k % i == 0，也就是 k 是 i 的倍数，此时灯泡 k 会转变一次状态。另一方面，在第 k / i 轮，灯泡 k 同样会转变一次状态。因此，如果 i != k / i，那么灯泡会转变两次，最终还是灭的；而只有 i == k / i，也就是 k == i * i，即 k 是个平方数，此时灯泡 k 只会转变一次，因此最后的状态是亮的。

举个例子，比如 12，由于 12 = 1 * 12 = 2 * 6 = 3 * 4，因此会分别在第 1, 2, 3, 4, 6, 12 轮转换六次状态，最终还是灭的；而对于 16，由于 16 = 1 * 16 = 2 * 8 = 4 * 4，由于在 4 处只变了一次，最终在第 1, 2, 4, 8, 16 轮转换五次，最终是亮的。

因此，亮着的灯泡的个数就等同于 [1, n] 内的平方数的个数。解法如下：

class Solution:
    def bulbSwitch(self, n: int) -> int:
        return floor(sqrt(n))

#521 - 最长特殊序列 Ⅰ

给你两个字符串，请你从这两个字符串中找出最长的特殊序列。

「最长特殊序列」定义如下：该序列为某字符串独有的最长子序列（即不能是其他字符串的子序列）。

子序列 可以通过删去字符串中的某些字符实现，但不能改变剩余字符的相对顺序。空序列为所有字符串的子序列，任何字符串为其自身的子序列。

输入为两个字符串，输出最长特殊序列的长度。如果不存在，则返回 -1。

class Solution:
    def findLUSlength(self, a: str, b: str) -> int:
        if a == b:
            return -1
        else:
            return max(len(a), len(b))

#777 - 在LR字符串中交换相邻字符

在一个由 ‘L’ , ‘R’ 和 ‘X’ 三个字符组成的字符串（例如"RXXLRXRXL"）中进行移动操作。一次移动操作指用一个"LX"替换一个"XL"，或者用一个"XR"替换一个"RX"。现给定起始字符串start和结束字符串end，请编写代码，当且仅当存在一系列移动操作使得start可以转换成end时， 返回True。

#1033 - 移动石子直到连续

三枚石子放置在数轴上，位置分别为 a，b，c。

每一回合，我们假设这三枚石子当前分别位于位置 x, y, z 且 x < y < z。从位置 x 或者是位置 z 拿起一枚石子，并将该石子移动到某一整数位置 k 处，其中 x < k < z 且 k != y。

当你无法进行任何移动时，即，这些石子的位置连续时，游戏结束。

要使游戏结束，你可以执行的最小和最大移动次数分别是多少？ 以长度为 2 的数组形式返回答案：answer = [minimum_moves, maximum_moves]

class Solution:
    def numMovesStones(self, a: int, b: int, c: int) -> List[int]:
        a, b, c = sorted([a, b, c])
        if a + 1 == b and b + 1 == c:
            return [0, 0]
        elif b - a  <= 2 or c - b <= 2:
            return [1, c - a - 2]
        else:
            return [2, c - a - 2]

#1227 - 飞机座位分配概率

有 n 位乘客即将登机，飞机正好有 n 个座位。第一位乘客的票丢了，他随便选了一个座位坐下。

剩下的乘客将会：

如果他们自己的座位还空着，就坐到自己的座位上，

当他们自己的座位被占用时，随机选择其他座位
第 n 位乘客坐在自己的座位上的概率是多少？

class Solution:
    def nthPersonGetsNthSeat(self, n: int) -> float:
        return 1 if n == 1 else 0.5

#1503 - 所有蚂蚁掉下来前的最后一刻

有一块木板，长度为 n 个 单位 。一些蚂蚁在木板上移动，每只蚂蚁都以 每秒一个单位 的速度移动。其中，一部分蚂蚁向 左 移动，其他蚂蚁向 右 移动。

当两只向 不同 方向移动的蚂蚁在某个点相遇时，它们会同时改变移动方向并继续移动。假设更改方向不会花费任何额外时间。

而当蚂蚁在某一时刻 t 到达木板的一端时，它立即从木板上掉下来。

给你一个整数 n 和两个整数数组 left 以及 right 。两个数组分别标识向左或者向右移动的蚂蚁在 t = 0 时的位置。请你返回最后一只蚂蚁从木板上掉下来的时刻。

题目写的花里胡哨的，但是想想看，两只蚂蚁碰面的时候，究竟发生了什么？

改变移动方向并继续移动，这是不是等同于他们穿过了彼此，然后继续移动？

所以就不用考虑碰不碰面的问题，就当每只蚂蚁都是独立的，而现在要求的就是行走最远的蚂蚁走了多久。

因此答案就是：

1. 向左走的蚂蚁要走到 0 的位置，走的最远的路程就是他们所在的位置的最大值，也就是 max(left)
2. 向右走的蚂蚁要走到 n 的位置，走的最远的路程就是 n 减去他们所在的位置的最小值，也就是 n - max(right)
3. 最终的结果就是上面两个的最大值。

解答如下：

class Solution:
    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:
        ans = 0
        if left:
            ans = max(ans, max(left))
        if right:
            ans = max(ans, n - min(right))
        return ans