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 仅由数字组成。

思路

找规律，如上图，只需对85%10 和51%10 是否相等即可，最终发现，哇！是杨辉三角*数值的组合耶！
- 其中 78 粉色区域是两边公共相加数值区域，所以不需要计算
- 比如 85 = 3*1+4*4+6*6+7*4+2*1 51 = 6*1+7*4+2*6+0*4+5*1 ，其中 [1,4,6,4,1]是不是就是杨辉三角的第5行的数？
- 利用组合数递推公式：C(n,i) = C(n,i-1) * (n - i + 1) / i ，来求杨辉三角第 n 行的数值，但是由于数值溢出问题，所以我们分成两个区间计算：
  - n<62 时，通过公式推导，时间复杂度为 O(n)
  - 数值溢出时，通过 rowLastDigits[j] = (rowLastDigits[j] + rowLastDigits[j - 1]) % 10 来反向推导，时间复杂度为O(n^2)
最终优化版本
- 我们观察到比如 85 = 3*1+4*4+6*6+7*4+2*1 51 = 6*1+7*4+2*6+0*4+5*1 分别模10比较，与 (3-6)*1+(4-7)*4+(6-2)*6+(7-0)*4+(2-5)*1 模10判断是否等于0效果是一样的，所以我们进行优化

代码

找规律，杨辉三角*数值的组合耶！

class Solution {
    public boolean hasSameDigits(String s) {
        int n = s.length() - 3;
        int[] rowLastDigits = new int[n + 1];
        rowLastDigits[0] = 1;
        int pre = s.charAt(0) - '0';
        int suf = s.charAt(2) - '0';
        // 使用组合数公式的迭代计算，仅保留最后一位
        if (n < 62) {
            long current = 1;
            for (int i = 1; i <= n; i++) {
                // 利用组合数递推公式：C(n,i) = C(n,i-1) * (n - i + 1) / i
                // 关键：先进行除法操作，再进行取模
                current = current * (n - i + 1) / i;
                rowLastDigits[i] = (int) (current % 10);// 只保留最后一位
                if (rowLastDigits[i] != 0) { //为什么加if语句？性能高于乘和模运算
                    pre = (pre + rowLastDigits[i] * (s.charAt(i) - '0')) % 10;
                    suf = (suf + rowLastDigits[i] * (s.charAt(i + 2) - '0')) % 10;
                }
            }
        } else {
            for (int i = 1; i <= n; i++) {
                rowLastDigits[i] = 1;
                for (int j = i - 1; j > 0; j--) {
                    rowLastDigits[j] = (rowLastDigits[j] + rowLastDigits[j - 1]) % 10;
                }
            }
            for (int i = 1; i <= n; i++) {
                if (rowLastDigits[i] != 0) {
                    pre = (pre + rowLastDigits[i] * (s.charAt(i) - '0')) % 10;
                    suf = (suf + rowLastDigits[i] * (s.charAt(i + 2) - '0')) % 10;
                }
            }
        }
        return pre == suf;
    }
}

最终优化版本

class Solution {
    public boolean hasSameDigits(String s) {
        int n = s.length() - 3;
        int[] rowLastDigits = new int[n + 1];
        rowLastDigits[0] = 1;
        int sum = s.charAt(0) - s.charAt(2);
        // 使用组合数公式的迭代计算，仅保留最后一位
        if (n < 62) {
            long current = 1; //防止溢出使用long
            for (int i = 1; i <= n; i++) {
                // 利用组合数递推公式：C(n,i) = C(n,i-1) * (n - i + 1) / i
                // 关键：先进行除法操作，再进行取模
                current = current * (n - i + 1) / i;
                rowLastDigits[i] = (int) (current % 10);// 只保留最后一位
                if (rowLastDigits[i] != 0) { //为什么加if语句？性能高于乘和模运算
                    sum = (sum + rowLastDigits[i] * (s.charAt(i) - s.charAt(i + 2))) % 10;
                }
            }
        } else {
            for (int i = 1; i <= n; i++) {
                rowLastDigits[i] = 1;
                for (int j = i - 1; j > 0; j--) {
                    rowLastDigits[j] = (rowLastDigits[j] + rowLastDigits[j - 1]) % 10;
                }
            }
            for (int i = 1; i <= n; i++) {
                if (rowLastDigits[i] != 0) {
                    sum = (sum + rowLastDigits[i] * (s.charAt(i) - s.charAt(i + 2))) % 10;
                }
            }
        }
        return sum == 0;
    }
}