Easy

题目描述

给你一个下标从 0 开始、长度为 n 的字符串 num ，它只包含数字。

如果对于 每个 0 <= i < n 的下标 i ，都有数字 i 在 num 中恰好出现了 num[i] 次，则返回 true ，否则返回 false 。

示例 1：

输入：num = "1210"
输出：true
解释：
num[0] = '1' 。数字 0 在 num 中出现了一次。
num[1] = '2' 。数字 1 在 num 中出现了两次。
num[2] = '1' 。数字 2 在 num 中出现了一次。
num[3] = '0' 。数字 3 在 num 中出现了零次。
对于 "1210" 中的每个下标 i ，条件都成立，所以返回 true 。

示例 2：

输入：num = "030"
输出：false
解释：
num[0] = '0' 。数字 0 应该出现 0 次，但是在 num 中出现了 2 次。
num[1] = '3' 。数字 1 应该出现 3 次，但是在 num 中出现了 0 次。
num[2] = '0' 。数字 2 在 num 中出现了 0 次。
下标 0 和 1 都违反了条件，所以返回 false 。

提示：

  • n == num.length
  • 1 <= n <= 10
  • num 只包含数字

解题思路

这道题的核心思路是理解题目要求：对于位置 i，数字 i 应该在整个字符串中出现 num[i] 次。

解题步骤：

  1. 统计频次：首先统计字符串中每个数字（0-9）出现的次数
  2. 逐位检查：遍历字符串的每个位置 i，检查数字 i 的实际出现次数是否等于 num[i] 的值
  3. 返回结果：如果所有位置都满足条件则返回 true，否则返回 false

算法实现：

  • 使用频次数组或哈希表统计每个数字的出现次数
  • 由于字符串长度最大为10，且只包含数字，可以直接用大小为10的数组记录0-9的频次
  • 对于每个位置 i，比较 count[i] 和 num[i] - '0' 是否相等

时间复杂度分析： 需要两次遍历，一次统计频次，一次检查条件，总体为O(n) 空间复杂度分析： 使用固定大小的频次数组，为O(1)

代码实现

class Solution {
public:
    bool digitCount(string num) {
        vector<int> count(10, 0);
        
        // 统计每个数字的出现次数
        for (char c : num) {
            count[c - '0']++;
        }
        
        // 检查每个位置的条件
        for (int i = 0; i < num.size(); i++) {
            if (count[i] != num[i] - '0') {
                return false;
            }
        }
        
        return true;
    }
};

class Solution:
    def digitCount(self, num: str) -> bool:
        count = [0] * 10
        
        # 统计每个数字的出现次数
        for digit in num:
            count[int(digit)] += 1
        
        # 检查每个位置的条件
        for i in range(len(num)):
            if count[i] != int(num[i]):
                return False
        
        return True

public class Solution {
    public bool DigitCount(string num) {
        int[] count = new int[10];
        
        // 统计每个数字的出现次数
        foreach (char c in num) {
            count[c - '0']++;
        }
        
        // 检查每个位置的条件
        for (int i = 0; i < num.Length; i++) {
            if (count[i] != num[i] - '0') {
                return false;
            }
        }
        
        return true;
    }
}

var digitCount = function(num) {
    const count = new Array(10).fill(0);
    
    // 统计每个数字的出现次数
    for (let digit of num) {
        count[parseInt(digit)]++;
    }
    
    // 检查每个位置的条件
    for (let i = 0; i < num.length; i++) {
        if (count[i] !== parseInt(num[i])) {
            return false;
        }
    }
    
    return true;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)需要遍历字符串两次，n为字符串长度
空间复杂度O(1)使用固定大小为10的数组存储数字频次

相关题目