问题描述(来源于LeetCode)

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

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

解题思路分析

问题本质

遍历整数的每一位数字，检查该数字是否能整除原数。

核心挑战

  1. 如何提取整数的每一位数字
  2. 如何处理数字0（不能作为除数）
  3. 如何高效遍历所有数位

代码实现

1
2
3
4
5
6
7
8
9
10
class Solution:
    def countDigits(self, num: int) -> int:
        x=0
        nums=num
        while num:
            val = num %10
            if nums % val ==0 and val!=0:
                x+=1
            num=num//10
        return x

算法详解

步骤分解

  1. 初始化计数器：x=0 用于统计满足条件的位数
  2. 保存原数字：nums=num 保存原始数字用于后续除法检查
  3. 循环遍历每一位：
    • 使用 num % 10 获取最后一位数字
    • 检查该数字是否能整除原数字 nums % val == 0 且数字不为0 val != 0
    • 如果满足条件，计数器 x 加1
    • 使用 num = num // 10 移除最后一位
  4. 返回结果：返回计数器 x 的值

关键技术点

  • 数字分解：通过取模和整除操作提取数位
  • 循环控制：当 num 变为0时循环结束
  • 原数字保存：保存原始数字用于除法检查
  • 除零防护：添加 val != 0 检查避免除零错误

复杂度分析

  • 时间复杂度：O(log n)
    • 循环次数等于数字的位数，对于整数n，位数为 ⌊log₁₀n⌋ + 1
  • 空间复杂度：O(1)
    • 只使用了固定数量的变量，不随输入规模变化

示例分析

示例1：num = 1248

1
2
3
4
5
6
7
原始数字：1248
循环过程：
- 第一次：val=8, 1248%8=0 → x=1
- 第二次：val=4, 1248%4=0 → x=2  
- 第三次：val=2, 1248%2=0 → x=3
- 第四次：val=1, 1248%1=0 → x=4
结果：4

示例2：num = 121

1
2
3
4
5
6
原始数字：121
循环过程：
- 第一次：val=1, 121%1=0 → x=1
- 第二次：val=2, 121%2=1 ≠0 → x=1
- 第三次：val=1, 121%1=0 → x=2
结果：2

示例3：num = 101

1
2
3
4
5
6
原始数字：101
循环过程：
- 第一次：val=1, 101%1=0 → x=1
- 第二次：val=0, 跳过（因为val=0）→ x=1
- 第三次：val=1, 101%1=0 → x=2
结果：2

测试用例

测试用例 输入num 位数 满足条件的位数 输出
1 7 [7] [7] 1
2 121 [1,2,1] [1,1] 2
3 1248 [1,2,4,8] [1,2,4,8] 4
4 37 [3,7] [] 0
5 101 [1,0,1] [1,1] 2

边界情况考虑

已处理的边界情况

  1. 包含零的情况：通过 val != 0 检查避免除零错误
  2. 个位数情况：正确处理只有一位数字的情况
  3. 重复数字：正确处理包含重复数字的情况
  4. 质数情况：所有位数都不能整除的情况

其他边界情况

  • 负整数：题目保证输入是非负整数
  • 零本身：输入为0时，循环不会执行，返回0

算法正确性分析

算法优势

  1. 正确性：对于所有非负整数输入，算法能正确统计能整除原数的位数
  2. 健壮性：通过 val != 0 检查避免了除零错误
  3. 高效性：时间复杂度与数字位数成正比，是最优解

算法局限性

  • 仅适用于非负整数（符合题目要求）
  • 对于非常大的数字，仍能高效处理

扩展思考

相关数学概念

  1. 整除性质：理解整除的基本定义和性质
  2. 数位分解：掌握数字的位值表示法
  3. 模运算：熟练运用模运算解决问题

实际应用场景

  • 数字属性分析工具
  • 数学游戏中的特殊数字判定
  • 密码学中的数字特征检查
  • 数字筛选和分类系统

算法变体

1
2
3
4
5
6
7
8
# 使用字符串转换的方法
	def countDigits(self, num: int) -> int:
    	count = 0
    	for digit_char in str(num):
       	 digit = int(digit_char)
        	if digit != 0 and num % digit == 0:
           	 count += 1
   	 return count

总结

这个算法展示了完整的数字处理解决方案：

  1. 问题分析能力：准确理解问题要求和约束条件
  2. 数字分解技术：熟练使用模运算和整除运算提取数位
  3. 循环控制技巧：通过循环高效遍历数字的所有位数
  4. 边界情况处理：正确处理除零错误等边界情况
  5. 条件判断逻辑：精确检查数位是否能整除原数