2025-08-27：判断操作后字符串中的数字是否相等Ⅰ。用go语言，给定一个只包含数字字符的字符串 s。重复执行下面的变换，直到字符串长度为 2：

• 对原字符串中每一对相邻数字，计算它们之和对 10 取余；

• 将这些得到的新数按原有顺序拼成新的字符串（长度每次减一）。

当最终剩下的两个数字相同则返回 true，否则返回 false。

3 <= s.length <= 100。

s 仅由数字组成。

输入： 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。

题目来自力扣3461。

分步骤描述过程

1. 问题理解

给定一个数字字符串 s，重复执行以下操作直到字符串长度变为2：

• 对于每一对相邻数字，计算它们的和并对10取余（即 (a + b) % 10）。

• 将这些余数按顺序拼接成新字符串（新字符串长度比原字符串少1）。

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

2. 关键观察（数学性质）

实际上，这个过程类似于构建一个“数字三角形”（类似于杨辉三角），但每一步都进行模10运算。最终结果（最后两个数字是否相同）可以通过原始字符串的各位数字的线性组合（模10）来确定。

具体来说，最终结果（即最后两个数字）可以表示为原始字符串中每个数字乘以某个系数（组合数模10）的和（模10）。但注意，每一步操作都是模10的，因此整个变换是线性的（模10意义下）。

实际上，对于长度为 n 的字符串，经过 n-2 次操作后，得到两个数字：

• 第一个数字 = (c(0)*s[0] + c(1)*s[1] + ... + c(n-1)*s[n-1]) % 10

• 第二个数字 = (d(0)*s[0] + d(1)*s[1] + ... + d(n-1)*s[n-1]) % 10

其中系数 c(i) 和 d(i) 是二项式系数（组合数）模10的值（因为每一步操作相当于线性组合，且系数是二项式系数，但每一步模10后系数也需要模10）。

但更直接地，我们只需要判断两个最终数字是否相等，即：
(第一个数字 - 第二个数字) % 10 == 0

实际上，这两个数字的差可以表示为原始字符串各位的线性组合（系数为二项式系数的差，模10）。具体到本题代码中，hasSameDigits 函数计算的是：

diff = sum_{i=0}^{n-2} [ C(n-2, i) * (s[i] - s[i+1]) ] % 10

然后判断 diff % 10 == 0。

为什么？

• 实际上，最终两个数字的差可以推导为上述形式（通过数学归纳或观察线性变换的性质）。注意，每一步操作相当于应用一个线性变换（矩阵），而最终两个数字的差与原始相邻数字的差有关，系数是组合数（模10）。

3. 代码中的具体方法

• 预处理组合数（模2和模5？）：但这里实际上预处理了大小为5x5的组合数（因为卢卡斯定理中p=2和p=5，且n和k模p后不会超过4）。

• 使用卢卡斯定理计算 C(n, k) % p（p为2或5），然后通过中国剩余定理组合（因为10=2*5，且2和5互质）得到 C(n, k) % 10？但注意代码中：

  • lucas(n, k, p) 计算 C(n, k) % p（p为2或5）。

  • comb(n, k) 返回 lucas(n,k,2)*5 + lucas(n,k,5)*6，这实际上是在计算 C(n, k) % 10（因为5和6是中国剩余定理中的系数：模2和模5的组合数结果通过CRT合并为模10）。

• 在 hasSameDigits 中：

  • 计算 diff = sum_{i=0}^{n-2} [ comb(n-2, i) * (int(s[i]) - int(s[i+1])) ]

  • 然后判断 diff % 10 == 0。

为什么这样？

• 实际上，最终两个数字的差等于 diff（模10），所以如果 diff % 10 == 0，则两个数字相同。

4. 以 s = “3902” 为例验证

原始字符串：‘3’,‘9’,‘0’,‘2’，长度n=4。

需要计算：

diff = sum_{i=0}^{2} [ C(2, i) * (s[i] - s[i+1]) ]

即：

• i=0: C(2,0)(s0-s1) = 1(3-9) = -6

• i=1: C(2,1)(s1-s2) = 2(9-0)=18

• i=2: C(2,2)(s2-s3)=1(0-2)=-2

总和：-6 + 18 - 2 = 10。

10 % 10 = 0，所以返回true。

这与题目解释一致（最终得到"11"，相同）。

5. 复杂度分析

• 预处理组合数（大小5x5）：常数时间O(1)和常数空间O(1)。

• lucas 函数：递归深度为 log_p(n)（因为每次除以p），但n最大为100（字符串长度），而p=2或5，所以深度最多为7（因为2^7=128>100），每次递归是常数操作（因为组合数已预处理，直接查表）。所以每次调用lucas是O(log n)。

• comb 函数：调用两次lucas（分别模2和模5）和一次乘加，常数时间。

• hasSameDigits 函数：循环次数为n-1（即原始字符串长度减1），每次循环中调用一次comb（计算组合数模10）和一次乘加。所以总时间为O(n * log n)（因为每次comb是O(log n)）。

• 总时间：O(n log n)（n为字符串长度，最大100，所以很快）。

• 总空间：递归栈深度（lucas）为O(log n)，预处理组合数常数空间。所以额外空间为O(log n)（递归栈）。

总结

• 总时间复杂度：O(n log n)，其中n是字符串长度。

• 总额外空间复杂度：O(log n)（主要来自递归调用栈）。

注意：由于n最大为100，实际运行非常高效。

Go完整代码如下：

package main

import (
	"fmt"
)

const mx = 5

var c [mx][mx]int

func init() {
    // 预处理组合数
	for i := range mx {
		c[i][0], c[i][i] = 1, 1
		for j := 1; j < i; j++ {
			c[i][j] = c[i-1][j-1] + c[i-1][j]
		}
	}
}

// 计算 C(n, k) % p，要求 p 是质数
func lucas(n, k, p int) int {
	if k == 0 {
		return 1
	}
	return c[n%p][k%p] * lucas(n/p, k/p, p) % p
}

func comb(n, k int) int {
	// 结果至多为 5 + 4 * 6 = 29，无需中途取模
	return lucas(n, k, 2)*5 + lucas(n, k, 5)*6
}

func hasSameDigits(s string) bool {
	diff := 0
	for i := range len(s) - 1 {
		diff += comb(len(s)-2, i) * (int(s[i]) - int(s[i+1]))
	}
	return diff%10 == 0
}

func main() {
	s := "3902"
	result := hasSameDigits(s)
	fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

mx = 5
c = [[0] * mx for _ in range(mx)]

def init():
    # 预处理组合数
    for i in range(mx):
        c[i][0] = 1
        c[i][i] = 1
        for j in range(1, i):
            c[i][j] = c[i-1][j-1] + c[i-1][j]

def lucas(n, k, p):
    """计算 C(n, k) % p，p 是质数"""
    if k == 0:
        return 1
    return (c[n % p][k % p] * lucas(n // p, k // p, p)) % p

def comb(n, k):
    # 结果至多为 5 + 4 * 6 = 29，无需中途取模
    return lucas(n, k, 2) * 5 + lucas(n, k, 5) * 6

def has_same_digits(s):
    diff = 0
    for i in range(len(s) - 1):
        diff += comb(len(s) - 2, i) * (ord(s[i]) - ord(s[i+1]))
    return diff % 10 == 0

if __name__ == "__main__":
    init()
    s = "3902"
    result = has_same_digits(s)
    print(result)