Hard

题目描述

给你一个由数字组成的字符串 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 <= 10^5
  • s 只包含数字。

解题思路

这是一个看似简单但实际上需要数学知识的问题。如果我们直接模拟操作过程，时间复杂度会是 O(n²)，对于大数据会超时。

通过观察操作过程，我们发现每次操作都是将相邻数字相加取模。这个过程实际上可以用组合数学来分析。

关键洞察是：最终的两个数字实际上是原始字符串中所有数字的线性组合，其系数是二项式系数（组合数）。具体来说，对于长度为 n 的字符串，最终的第一个数字是 sum(C(n-2, i) * s[i]) % 10，第二个数字是 sum(C(n-2, i) * s[i+1]) % 10。

根据提示，我们需要使用卢卡斯定理计算 C(n,k) mod 10。由于 10 = 2 × 5，我们可以分别计算 C(n,k) mod 2 和 C(n,k) mod 5，然后用中国剩余定理合并结果。

对于 C(n,k) mod 2：根据卢卡斯定理，当且仅当 k 的二进制表示是 n 的二进制表示的子集时，C(n,k) mod 2 = 1。

对于 C(n,k) mod 5：同样使用卢卡斯定理，递归计算。

最终判断两个线性组合的结果是否相等即可。

代码实现

class Solution {
public:
    bool hasSameDigits(string s) {
        int n = s.length();
        if (n == 2) return s[0] == s[1];
        
        vector<int> digits(n);
        for (int i = 0; i < n; i++) {
            digits[i] = s[i] - '0';
        }
        
        // Calculate C(n-2, k) mod 10 for k = 0 to n-2
        vector<int> coeff(n-1);
        for (int k = 0; k < n-1; k++) {
            coeff[k] = lucas10(n-2, k);
        }
        
        int sum1 = 0, sum2 = 0;
        for (int i = 0; i < n-1; i++) {
            sum1 = (sum1 + coeff[i] * digits[i]) % 10;
            sum2 = (sum2 + coeff[i] * digits[i+1]) % 10;
        }
        
        return sum1 == sum2;
    }
    
private:
    int lucas10(int n, int k) {
        if (k > n) return 0;
        return (lucas2(n, k) * 6 + lucas5(n, k) * 4) % 10;
    }
    
    int lucas2(int n, int k) {
        while (n > 0 || k > 0) {
            if ((k & 1) > (n & 1)) return 0;
            n >>= 1;
            k >>= 1;
        }
        return 1;
    }
    
    int lucas5(int n, int k) {
        if (k == 0) return 1;
        if (n == 0) return 0;
        return (lucas5(n/5, k/5) * comb5(n%5, k%5)) % 5;
    }
    
    int comb5(int n, int k) {
        if (k > n) return 0;
        static vector<vector<int>> pascal = {{1}, {1,1}, {1,2,1}, {1,3,3,1}, {1,4,1,4,1}};
        return pascal[n][k];
    }
};

class Solution:
    def hasSameDigits(self, s: str) -> bool:
        n = len(s)
        if n == 2:
            return s[0] == s[1]
        
        digits = [int(c) for c in s]
        
        def lucas2(n, k):
            while n > 0 or k > 0:
                if k & 1 > n & 1:
                    return 0
                n >>= 1
                k >>= 1
            return 1
        
        def lucas5(n, k):
            if k == 0:
                return 1
            if n == 0:
                return 0
            pascal = [[1], [1,1], [1,2,1], [1,3,3,1], [1,4,1,4,1]]
            return (lucas5(n//5, k//5) * pascal[n%5][k%5]) % 5
        
        def lucas10(n, k):
            if k > n:
                return 0
            return (lucas2(n, k) * 6 + lucas5(n, k) * 4) % 10
        
        sum1 = sum2 = 0
        for i in range(n-1):
            coeff = lucas10(n-2, i)
            sum1 = (sum1 + coeff * digits[i]) % 10
            sum2 = (sum2 + coeff * digits[i+1]) % 10
        
        return sum1 == sum2

public class Solution {
    public bool HasSameDigits(string s) {
        int n = s.Length;
        if (n == 2) return s[0] == s[1];
        
        int[] digits = new int[n];
        for (int i = 0; i < n; i++) {
            digits[i] = s[i] - '0';
        }
        
        int sum1 = 0, sum2 = 0;
        for (int i = 0; i < n-1; i++) {
            int coeff = Lucas10(n-2, i);
            sum1 = (sum1 + coeff * digits[i]) % 10;
            sum2 = (sum2 + coeff * digits[i+1]) % 10;
        }
        
        return sum1 == sum2;
    }
    
    private int Lucas10(int n, int k) {
        if (k > n) return 0;
        return (Lucas2(n, k) * 6 + Lucas5(n, k) * 4) % 10;
    }
    
    private int Lucas2(int n, int k) {
        while (n > 0 || k > 0) {
            if ((k & 1) > (n & 1)) return 0;
            n >>= 1;
            k >>= 1;
        }
        return 1;
    }
    
    private int Lucas5(int n, int k) {
        if (k == 0) return 1;
        if (n == 0) return 0;
        return (Lucas5(n/5, k/5) * Comb5(n%5, k%5)) % 5;
    }
    
    private int Comb5(int n, int k) {
        if (k > n) return 0;
        int[][] pascal = {
            new int[]{1},
            new int[]{1,1},
            new int[]{1,2,1},
            new int[]{1,3,3,1},
            new int[]{1,4,1,4,1}
        };
        return pascal[n][k];
    }
}

/**
 * @param {string} s
 * @return {boolean}
 */
var hasSameDigits = function(s) {
    let digits = s.split('').map(Number);
    
    while (digits.length > 2) {
        let newDigits = [];
        for (let i = 0; i < digits.length - 1; i++) {
            newDigits.push((digits[i] + digits[i + 1]) % 10);
        }
        digits = newDigits;
    }
    
    return digits[0] === digits[1];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n log n)
空间复杂度O(1)

其中 n 是字符串长度。时间复杂度主要来自于计算组合数的卢卡斯定理，每次计算的复杂度是 O(log n)，总共需要计算 O(n) 次。

相关题目