目标
给你一个由数字组成的字符串 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;
}
}
性能
