Easy

题目描述

给你一个由数字组成的字符串 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 仅由数字组成。

解题思路

解题思路

这是一道模拟题，需要按照题目描述的规则逐步进行操作。

核心思路：

  1. 重复执行操作直到字符串长度为2
  2. 每次操作：遍历当前字符串，对每对相邻数字求和并取模10
  3. 用新生成的数字序列替换原字符串
  4. 最后检查两位数字是否相同

算法步骤：

  1. 当字符串长度大于2时，继续执行操作
  2. 对于每次操作，创建新的字符串来存储结果
  3. 遍历当前字符串的相邻位置 i 和 i+1
  4. 计算 (s[i] + s[i+1]) % 10 并添加到新字符串
  5. 用新字符串替换原字符串
  6. 重复直到长度为2，然后比较两位数字

时间复杂度分析：

  • 每次操作字符串长度减1，最多需要 n-2 次操作
  • 每次操作需要 O(当前长度) 的时间
  • 总时间复杂度为 O(n²)

这种直接模拟的方法简单易懂，对于题目给定的约束条件（长度不超过100）完全可以满足性能要求。

代码实现

class Solution {
public:
    bool hasSameDigits(string s) {
        while (s.length() > 2) {
            string newS = "";
            for (int i = 0; i < s.length() - 1; i++) {
                int sum = (s[i] - '0') + (s[i + 1] - '0');
                newS += to_string(sum % 10);
            }
            s = newS;
        }
        return s[0] == s[1];
    }
};

class Solution:
    def hasSameDigits(self, s: str) -> bool:
        while len(s) > 2:
            new_s = ""
            for i in range(len(s) - 1):
                sum_digits = int(s[i]) + int(s[i + 1])
                new_s += str(sum_digits % 10)
            s = new_s
        return s[0] == s[1]

public class Solution {
    public bool HasSameDigits(string s) {
        while (s.Length > 2) {
            string newS = "";
            for (int i = 0; i < s.Length - 1; i++) {
                int sum = (s[i] - '0') + (s[i + 1] - '0');
                newS += (sum % 10).ToString();
            }
            s = newS;
        }
        return s[0] == s[1];
    }
}

var hasSameDigits = function(s) {
    while (s.length > 2) {
        let newS = "";
        for (let i = 0; i < s.length - 1; i++) {
            let sum = parseInt(s[i]) + parseInt(s[i + 1]);
            newS += (sum % 10).toString();
        }
        s = newS;
    }
    return s[0]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)最多进行 n-2 次操作，每次操作的时间复杂度为 O(当前字符串长度)
空间复杂度O(n)每次操作需要创建新的字符串存储中间结果