判断一个数的数字计数是否等于数位的值

难度: 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" 满足题目要求条件，所以返回 true 。

示例 2：

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

提示：

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

Submission

运行时间: 24 ms

内存: 16.0 MB

class Solution:
    def digitCount(self, num: str) -> bool:
        kv = collections.Counter(num)
        for i in range(len(num)):
            if int(num[i]) != kv[chr(i + 0x30)]:
                return False
        return True

Explain

此题解首先使用collections.Counter来计数字符串中每个字符出现的次数，存储在字典kv中。然后，遍历字符串的每个字符，对于每个位置i，检查字符num[i]（转换为整数）是否等于它在字符串中出现的次数（通过kv[chr(i + 0x30)]获取）。chr(i + 0x30)将索引转换为对应的字符。如果所有位置都满足条件，返回True，否则一旦发现不匹配则返回False。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def digitCount(self, num: str) -> bool:
        # 使用collections.Counter来计算num中每个数字字符的出现频率
        kv = collections.Counter(num)
        # 遍历num的每个位置
        for i in range(len(num)):
            # 检查num中位置i的数字字符是否出现了num[i]次
            if int(num[i]) != kv[chr(i + 0x30)]:
                return False
        return True

Explore

`collections.Counter`是Python标准库中的一个类，专门用于计数可哈希对象。它本质上是一个字典，其中元素作为键，它们的计数作为值。`Counter`在内部使用散列表（哈希表）实现，因此其计数操作的平均时间复杂度为O(1)。这意味着对于大多数实际应用来说，它的效率已经非常高。尽管如此，如果我们知道数据的具体特性，例如只有十个数字字符，可以使用长度为10的数组来计数，每个索引对应一个数字的出现次数，这种方法的空间和时间效率可能略优于`Counter`，因为它避免了哈希表的潜在开销。

`chr(i + 0x30)`用于将整数i转换为对应的ASCII字符。这里0x30是数字0的ASCII码。因此，当i在0到9的范围内时，`chr(i + 0x30)`正确地将索引转换为相应的字符'0'到'9'。如果索引i超过9，这种转换仍然有效，但不再对应于单个数字字符，而是对应于其他ASCII字符。然而，题解假设输入字符串只包含数字字符，因此实际情况中i不应超过9。

如果数字字符串长度大于10，算法仍然有效，但其逻辑必须正确理解。算法不是假设字符串长度必须小于或等于10，而是假设字符串只包含数字0到9。即使字符串长度超过10，只要字符串中的每个数字字符的出现次数与其在字符串中的位置匹配，算法就能正确返回True。例如，对于字符串'112'，虽然长度超过10，但只要每个数字的出现次数符合条件，算法仍然返回True。

这种转换是必要的，因为`num[i]`是一个字符，而`kv[chr(i + 0x30)]`是一个整数，表示字符的出现次数。直接比较一个字符与一个整数在Python中不会得到有效的比较结果。因此，我们需要将`num[i]`从字符转换为对应的整数，以便与出现次数（也是整数）进行比较。这确保了比较的合理性和准确性。