可以读通讯稿的组数

Leetcode Link: 可以读通讯稿的组数 - 力扣 (LeetCode) 竞赛

题目

解法一

思路： 假设原始数字为 A 和 B，其对应的镜像为 A’和 B’

本题的约束是找到所有 A 和 B 的组合，满足 $A^{\prime }+B=A+B^{\prime }$ 直接决解问题会非常复杂，故对公式进行变换，有 $A-A^{\prime }=B-B^{\prime }$ 即问题等价于找到所有 A 和 B 的组合，满足两者自身减去自身的镜像的结果相等。

解决等价问题的步骤为

1. 求解镜像数组，并创建字典用来计数，key=自身减去镜像的差，value=个数
2. 计算所有数字自身减镜像的值存入字典
3. 每个key下的所有个数都可以两两组成一对，计算结果即可

题解：

class Solution:
    def numberOfPairs(self, nums: List[int]) -> int:
        dd = defaultdict(int)
        # 取镜像
        mirror = [int(str(x)[::-1]) for x in nums]
        # 计算所有的 A-A' 的值
        for a, a_ in zip(nums, mirror):
            dd[a-a_] += 1
        # 计算结果，两两一对。
        res = 0
        for k, v in dd.items():
            res += v * (v-1) / 2
        return int(res) % (10**9+7)