3461.判断操作后字符串中的数字是否相等I

目标

给你一个由数字组成的字符串 s 。重复执行以下操作，直到字符串恰好包含 两个 数字：

• 从第一个数字开始，对于 s 中的每一对连续数字，计算这两个数字的和 模 10。
• 用计算得到的新数字依次替换 s 的每一个字符，并保持原本的顺序。

如果 s 最后剩下的两个数字 相同 ，返回 true 。否则，返回 false。

示例 1：

输入： s = "3902"
输出： true
解释：
一开始，s = "3902"
第一次操作：
(s[0] + s[1]) % 10 = (3 + 9) % 10 = 2
(s[1] + s[2]) % 10 = (9 + 0) % 10 = 9
(s[2] + s[3]) % 10 = (0 + 2) % 10 = 2
s 变为 "292"
第二次操作：
(s[0] + s[1]) % 10 = (2 + 9) % 10 = 1
(s[1] + s[2]) % 10 = (9 + 2) % 10 = 1
s 变为 "11"
由于 "11" 中的数字相同，输出为 true。

示例 2：

输入： s = "34789"
输出： false
解释：
一开始，s = "34789"。
第一次操作后，s = "7157"。
第二次操作后，s = "862"。
第三次操作后，s = "48"。
由于 '4' != '8'，输出为 false。

说明：

• 3 <= s.length <= 100
• s 仅由数字组成。

思路

有一个长度为 n 的数字字符串，每一次操作收集相邻两个数字之和模 10 的结果，得到一个长度为 n - 1 的字符串，反复执行操作直到剩下两个数字，判断剩余的两个数字是否相等。

简单的做法就是根据题意模拟。

在 n - 2 次合并后，s[i] 对最终结果的贡献等于从它开始，往下 n - 2 层到达根（可以看成一个倒着的杨辉三角）的路径数。

代码

/**
 * @date 2025-10-23 9:40
 */
public class HasSameDigits3461 {

    /**
     * 计算二项式展开系数
     */
    public boolean hasSameDigits_v1(String s) {
        int n = s.length();
        BigInteger[] factor = getFactor(n - 2);
        BigInteger a = BigInteger.ZERO;
        BigInteger b = BigInteger.ZERO;
        for (int i = 0; i < n - 1; i++) {
            a = a.add(BigInteger.valueOf(s.charAt(i) - '0').multiply(factor[i]));
        }
        for (int i = 1; i < n; i++) {
            b = b.add(BigInteger.valueOf(s.charAt(i) - '0').multiply(factor[i - 1]));
        }
        return a.mod(BigInteger.TEN).equals(b.mod(BigInteger.TEN));
    }

    public static Map<Integer, BigInteger[]> cache = new HashMap<>();

    public static BigInteger[] getFactor(int n) {
        BigInteger[] c = cache.get(n);
        if (c != null) {
            return c;
        }
        BigInteger[] prev = new BigInteger[1];
        prev[0] = BigInteger.ONE;
        for (int i = 1; i <= n; i++) {
            BigInteger[] cur = new BigInteger[i + 1];
            cur[0] = BigInteger.ONE;
            cur[i] = BigInteger.ONE;
            for (int j = 1; j < i; j++) {
                cur[j] = prev[j - 1].add(prev[j]);
            }
            prev = cur;
        }
        return prev;
    }

    /**
     * 模拟
     */
    public boolean hasSameDigits(String s) {
        Queue<Integer> q = new ArrayDeque<>();
        int n = s.length();
        for (int i = 0; i < n; i++) {
            q.offer(s.charAt(i) - '0');
        }
        while (q.size() > 2) {
            int len = q.size();
            int prev = q.poll();
            for (int i = 1; i < len; i++) {
                int cur = q.poll();
                q.offer((prev + cur) % 10);
                prev = cur;
            }
        }
        int a = q.poll();
        int b = q.poll();
        return a == b;
    }

}

性能