可以读通讯稿的组数

满足条件的对 $[A, B]$ :
镜像号码 $A$ + 原号码 $B$ = 镜像号码 $B$ + 原号码 $A$
移项：
镜像号码 $A$ - 原号码 $A$ = 镜像号码 $B$ - 原号码 $B$

因此，对于每个数，我们求出它的镜像号码减去原号码，放到一个新数组里，最后，我们再看有多少对相同即可。例如：如果 9 在新数组中出现了 10 次，那么它会产生 10 * 9 // 2 = 45 对。

Python3

class Solution:
    def numberOfPairs(self, nums: List[int]) -> int:
        mod = 10 ** 9 + 7
        d = {}
        for n in nums:
            k = n - int(str(n)[::-1])
            d[k] = d.get(k, 0) + 1
        r = 0
        for k in d:
            r += d[k] * (d[k] - 1) // 2
            r %= mod
        return r

时间复杂度： $O (n)$

池塘计数

相似问题：200. 岛屿数量

思路是：对所有水方格使用并查集，从上到下从左到右遍历，每到一个水方格，检查其左边、左上、上边、右上四个格子是否有水方格，如果有，则合并它们。

这里并查集里的 parents 数组，我用的是字典，值为方格的横纵坐标。

Python3

class Solution:
    def lakeCount(self, field: List[str]) -> int:
        n, m = len(field), len(field[0])
        d = {}
        for i in range(n):
            for j in range(m):
                if field[i][j] == 'W':
                    d[(i, j)] = (i, j)
        def find(x):
            if d[x] == x:
                return x
            else:
                d[x] = find(d[x])
                return d[x]
        def merge(p, q):
            p_, q_ = find(p), find(q)
            d[p_] = q_
        
        for i in range(n):
            for j in range(m):
                if field[i][j] != 'W':
                    continue
                if j > 0 and field[i][j - 1] == 'W':
                    p = (i, j)
                    q = (i, j - 1)
                    merge(p, q)
                if i > 0:
                    if j > 0 and field[i - 1][j - 1] == 'W':
                        p = (i, j)
                        q = (i - 1, j - 1)
                        merge(p, q)
                    if field[i - 1][j] == 'W':
                        p = (i, j)
                        q = (i - 1, j)
                        merge(p, q)
                    if j < m - 1 and field[i - 1][j + 1] == 'W':
                        p = (i, j)
                        q = (i - 1, j + 1)
                        merge(p, q)
        
        s = set()
        for i in range(n):
            for j in range(m):
                if field[i][j] == 'W':
                    p = find((i, j))
                    s.add(p)
        return len(s)

时间复杂度： $O (mn)$

数字默契考验

考虑这样一个问题：10 和 14 为什么不能变成同一个数呢（样例2）？因为 10 是 5 的倍数，而无论乘多少次 2 或 3，这一点都改变不了，同样改变不了的是 14 不是 5 的倍数这个现实。这就是他们不默契的原因。

如果两个数字 a 和 b “默契”，那么它们需要满足：从 a 和 b 中去掉所有的 2 和 3 的因子之后，它们会变成相同的数。这里观察样例 1 可以看出是符合这种情况的。

如若不然，令 a 变成 a', b 变成 b'，那么，要么 a' 不整除 b'，要么 b' 不整除 a'。不妨是前一种情况，那么a' 显然也不整除 b，因为 a' 中没有 2 或 3 了。所以 a 怎么乘都是 a' 的倍数，b 怎么乘都不是 a' 的倍数。这里如果有点基础数论知识就比较显然，没有的话稍微想想就行。

所以，如果把每个数都除干净 2 和 3，它们剩下的是同一个数，才有可能乘出同一个数来。这一点是可以保证的。比如我们设剩下那个数是 x。那么每个数 $a_{i}$ 都可以表示为 $a_{i} = x * 2^{p_{i}} * 3^{q_{i}}$ ，那么我们找到最大的 $p_{i}$ 和 $q_{i}$ ，设为 $p$ 和 $q$ ，然后把所有的数都变成 $x * 2^{p} * 3^{q}$ 就可以了。显然每个数乘的次数是 $p - p_{i} + q - q_{i}$

Python3

class Solution:
    def minOperations(self, numbers: List[int]) -> int:
        l = [n for n in numbers]
        p, q = 0, 0
        p_total, q_total = 0, 0
        for i in range(len(l)):
            pi, qi = 0, 0
            while l[i] % 2 == 0:
                l[i] //= 2
                pi += 1
            while l[i] % 3 == 0:
                l[i] //= 3
                qi += 1
            p = max(pi, p)
            q = max(qi, q)
            p_total += pi
            q_total += qi
        if len(set(l)) != 1:
            return -1
        else:
            return (p + q) * len(numbers) - p_total - q_total

时间复杂度： $O (n l o g C)$ ，其中 $C$ 是数字大小。

筹码游戏

首先观察范围可以发现这基本上是一道暴力搜索的题。初看它的逻辑也很像动态规划，或者说是记忆化搜索。所以关键有两个，一是怎么表达状态，二是转移方程是什么。

由于在最后结果中，每个数代表的筹码种类是任意的，也就是说我取出来一个筹码打算让它成为第一堆，后来别的筹码取出来了很多，超过它了，我又想让别的筹码变成第一堆。所以这时我们设置状态要灵活一点。

根据直觉，我们大概希望，现在已经有的筹码堆里面，比较多的堆我们把它目标朝向结果里比较多的那个数。因为如果目标少了的话，它可能很快就满了，或者已经满了，不得不丢掉，导致我们的选择减少。另外，我们希望这种目标是动态的。如果我连续抽出来比这堆少的其他筹码，使得另一堆的数量超过这一堆，那么它们的目标就要对换一下。

说人话就是：不管现有的是什么结果，第 $i$ 多的堆，它的目标就是 $n u m s$ 中第 $i$ 大的数。

比如说，我们现在有：（这里我们先对 $n u m s$ 进行排序和补零）

n u m s = (4, 2, 1, 1, 0) s t a t e = (2, 2, 1, 1, 0)

这时我们抽出了第二种筹码， $s t a t e$ 变成了 $(2, 3, 1, 1, 0)$ ，看起来它超过了，但是我们不需要让第二种筹码对应第二个数，我们把 $s t a t e$ 排序：

n u m s = (4, 2, 1, 1, 0) s t a t e = (3, 2, 1, 1, 0)

这样就很ok。但是如果我们现在抽出了第三种筹码（相对于现在的 $s t a t e$ 来说），那么它变成了 $(3, 2, 1, 2, 0)$ ，这时无论怎么排序都不行了，我们只能扔掉它了。

由于每次我们有均等的可能从 $kin d$ 种筹码中抽出一个，所以我们分类讨论：

如果 $s t a t e = n u m s$ ，那么搜索结束，返回 $0$ （需要 $0$ 步）
否则，先令期望 $E_{n e x t} = 0$
如果抽出一个发现不会超过，那么我们更新状态（+1然后排序），继续搜索，有：
$E_{n e x t} = E_{n e x t} + (1 + df s (n e w_t u pl e)) / kin d$
如果抽出来一个发现超过 $n u m s$ 了，也就是说在排序的情况下也有一个 $i$ 使得 $s t a t e [i] > n u m s [i]$ 了，这样的话我们只能把这个放回去了。我们把它的概率记下来，记做
$v ain = v ain + 1/ kin d$
所以现在我们有 $v ain$ 的可能性抽了白抽，剩下的可能性，我们算出了之后的期望 $E$ 了。所以这一步的返回值 $E$ 是什么呢？显然，如果是抽了白抽，那么接下来还是 $E$ ，所以我们有

E = v ain * (E + 1) + E_{n e x t} 即 E = \frac{v ain + E _{n e x t}}{1 - v ain}

然后按照这个去写 $df s$ 函数即可。

Python3

from functools import lru_cache
class Solution:
    def chipGame(self, nums: List[int], kind: int) -> float:
        nums.sort(reverse=True)
        while len(nums) < kind:
            nums.append(0)
        nums = tuple(nums)

        @lru_cache(None)
        def dfs(s):
            if s == nums:
                return 0
            state = list(s)
            E = 0
            vain = 0
            for i in range(len(state)):
                new_state = copy.copy(state)
                new_state[i] += 1
                new_state.sort(reverse=True)
                new_state = tuple(new_state)
                if not all(new_state[j] <= nums[j] for j in range(kind)):
                    vain += 1 / kind
                    continue
                E += (dfs(new_state) + 1) / kind
            return (vain + E) / (1 - vain)

        return dfs(tuple([0] * kind))

时间复杂度：由于 $s u m (n u m s) < 50$ ，那么状态数有一个上界是对 $s u m (s t a t e)$ 的整数拆分，其中 $s u m (s t a t e) < s u m (n u m s)$ 。 $50$ 的整数拆分大约在 $2 * 1 0^{5}$ 的量级，所以状态数肯定不会超过 $1 0^{7}$ 。当然这是一个很宽泛的估计，因为状态数还有其他的限制条件。最后再乘以 $O (k)$ ，所以它的上界是 $5 * 1 0^{8}$ 。这道题我的时间是 $9300 m s$ ，也是得亏没多弄几十个样例。