2520. 统计能整除数字的位数 : 简单模拟题（时空复杂度最优解）

站长

2024年03月29日 17:56 · 阅读数 5

题目描述

这是 LeetCode 上的 2520. 统计能整除数字的位数 ，难度为简单。

Tag : 「模拟」

给你一个整数 num，返回 num 中能整除 num 的数位的数目。

如果满足 nums % val == 0，则认为整数 val 可以整除 nums。

示例 1：

输入：num = 7

输出：1

解释：7 被自己整除，因此答案是 1 。

示例 2：

输入：num = 121

输出：2

解释：121 可以被 1 整除，但无法被 2 整除。由于 1 出现两次，所以返回 2 。

示例 3：

输入：num = 1248

输出：4

解释：1248 可以被它每一位上的数字整除，因此答案是 4 。

提示：

1<=num<=1091 <= num <= 10^91<=num<=109
num 的数位中不含 0

模拟

根据题意进行模拟即可。

假设起始值为 num，符合要求的数位个数为 ans，按照「从低到高」的方式循环处理 num 中的每个数位：

每次仅对当前数值 num 的最低位进行判断（当前数值 num 会被不断更新），通过「模 101010」的方式来「截取当前数值的最低位」，并根据要求进行判断，若当前数位符合要求，对 ans 进行加一；
判断完当前数组 num 的最低位后，通过「与 101010 地板除」的方式来「摒弃当前数值的最低位」，并以此更新 num；
循环步骤 1 和步骤 2，直到 num 所有数位均被处理完，即 num = 0。

用题面的示例 3 来举个 🌰，给定 num = 1248，完整处理过程如下：

当前数 num = 1248，通过 mod 10 取最低位 8，该数值满足要求，ans = 1；

通过 // 10 摒弃已处理的最低位，得到 num = 124
当前数 num = 124，通过 mod 10 取最低位 4，该数值满足要求，ans = 2；

通过 // 10 摒弃已处理的最低位，得到 num = 12
当前数 num = 12，通过 mod 10 取最低位 2，该数值满足要求，ans = 3；

通过 // 10 摒弃已处理的最低位，得到 num = 1
当前数 num = 1，通过 mod 10 取最低位 1，该数值满足要求，ans = 4；

通过 // 10 摒弃已处理的最低位，得到 num = 0，循环结束

Java 代码：

class Solution {
    public int countDigits(int num) {
        int n = num, ans = 0;
        while (num != 0) {
            ans += n % (num % 10) == 0 ? 1 : 0;
            num /= 10;
        }
        return ans;
    }
}

Python 代码：

class Solution:
    def countDigits(self, num: int) -> int:
        return sum(num % int(i) == 0 for i in str(num))
        
        # n, ans = num, 0
        # while num != 0:
        #     ans += n % (num % 10) == 0
        #     num //= 10
        # return ans

C++ 代码：

class Solution {
public:
    int countDigits(int num) {
        int n = num, ans = 0;
        while (num != 0) {
            ans += n % (num % 10) == 0;
            num /= 10;
        }
        return ans;
    }
};

TypeScript 代码：

function countDigits(num: number): number {
    let n = num, ans = 0;
    while (num !== 0) {
        ans += n % (num % 10) == 0 ? 1 : 0;
        num = Math.floor(num / 10);
    }
    return ans;
};

Kotlin 代码：

class Solution {
    fun countDigits(num: Int): Int {
        return num.toString().count { x -> num % (x - '0') == 0 }
    }
}

时间复杂度：O(log⁡n)O(\log{n})O(logn)
空间复杂度：O(1)O(1)O(1)

最后

这是我们「刷穿 LeetCode」系列文章的第 No.2520 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的合集新基地 🎉🎉