算法题 自除数

自除数

问题描述

自除数是指可以被它包含的每一位数整除的正整数。
例如，128 是一个自除数，因为128 % 1 == 0，128 % 2 == 0，128 % 8 == 0。

注意：自除数不允许包含 0，因为任何数除以 0 都是未定义的。

给定两个整数left和right，返回[left, right]范围内所有自除数的列表。

示例：

输入: left = 1, right = 22 输出: [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22]

算法思路

1. 遍历[left, right]范围内的每个数字
2. 对每个数字，提取其每一位数字进行验证
3. 验证条件：
   • 不能包含数字 0（因为除以 0 未定义）
   • 原数字必须能被每一位数字整除
4. 如果满足所有条件，则为自除数

代码实现

方法一：逐位验证

importjava.util.*;classSolution{/** * 找出指定范围内所有的自除数 * * @param left 范围左边界（包含） * @param right 范围右边界（包含） * @return 自除数列表 */publicList<Integer>selfDividingNumbers(intleft,intright){List<Integer>result=newArrayList<>();// 遍历给定范围内的每个数字for(intnum=left;num<=right;num++){// 检查当前数字是否为自除数if(isSelfDividing(num)){result.add(num);}}returnresult;}/** * 判断一个数字是否为自除数 * * @param num 待检查的数字 * @return true表示是自除数，false表示不是 */privatebooleanisSelfDividing(intnum){intoriginal=num;// 保存原始数字用于后续的整除判断// 逐位检查数字的每一位while(num>0){intdigit=num%10;// 获取当前数字的最后一位// 如果包含0，则不是自除数// 任何数都不能被0整除（除以0未定义）if(digit==0){returnfalse;}// 原始数字必须能被当前位数字整除if(original%digit!=0){returnfalse;}num/=10;// 去掉最后一位，继续检查下一位}// 所有位都通过检查，是自除数returntrue;}}

方法二：字符串

importjava.util.*;classSolution{/** * 使用字符串判断自除数 * * @param left 范围左边界（包含） * @param right 范围右边界（包含） * @return 自除数列表 */publicList<Integer>selfDividingNumbers(intleft,intright){List<Integer>result=newArrayList<>();for(intnum=left;num<=right;num++){if(isSelfDividingString(num)){result.add(num);}}returnresult;}/** * 使用字符串判断自除数 * * @param num 待检查的数字 * @return true表示是自除数，false表示不是 */privatebooleanisSelfDividingString(intnum){StringnumStr=String.valueOf(num);// 遍历字符串的每个字符for(charc:numStr.toCharArray()){intdigit=c-'0';// 将字符转换为数字// 检查是否包含0或不能整除if(digit==0||num%digit!=0){returnfalse;}}returntrue;}}

算法分析

• 时间复杂度：O(n × log m)

  • n = right - left + 1（范围内的数字个数）
  • log m = 数字的位数（m 为数字的大小，以10为底的对数）
  • 每个数字需要检查其所有位数

• 空间复杂度：O(1)（不包括结果列表）

  • 只使用了常数个额外变量

算法过程

输入：left = 1, right = 22

1. num = 1：

   • 位数：1
   • 1 % 1 == 0

2. num = 2：

   • 位数：2
   • 2 % 2 == 0

3. num = 10：

   • 位数：1, 0
   • 包含0

4. num = 11：

   • 位数：1, 1
   • 11 % 1 == 0

最终结果：[1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22]

测试用例

publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：标准示例System.out.println("Test 1: "+solution.selfDividingNumbers(1,22));// [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22]// 测试用例2：包含10的范围System.out.println("Test 2: "+solution.selfDividingNumbers(10,15));// [11, 12, 15]// 测试用例3：单个数字System.out.println("Test 3: "+solution.selfDividingNumbers(1,1));// [1]// 测试用例4：较大范围System.out.println("Test 4: "+solution.selfDividingNumbers(1,100));// 包含1-9, 11, 12, 15, 22, 24, 33, 36, 44, 48, 55, 66, 77, 88, 99// 测试用例5：包含边界值System.out.println("Test 5: "+solution.selfDividingNumbers(47,85));// [48, 55, 66, 77]// 测试用例6：无自除数的范围System.out.println("Test 6: "+solution.selfDividingNumbers(100,101));// []// 测试用例7：包含2000System.out.println("Test 7: "+solution.selfDividingNumbers(1999,2000));// []}

关键点

1. 0：

   • 自除数绝对不能包含数字0

2. 原始数字保存：

   • 在逐位检查时，必须使用原始数字进行整除运算

3. 位数提取：

   • 使用num % 10获取最后一位
   • 使用num / 10去掉最后一位

常见问题

1. 为什么不能包含0？

   • 数学上除以0是未定义的操作
   • 即使其他位都能整除，只要包含0就不是自除数

2. 为什么要保存原始数字？

   • 在逐位提取过程中，原数字会被修改（num /= 10）
   • 整除判断必须用完整的原始数字

3. 单数字（1-9）为什么都是自除数？

   • 任何非零数字都能被自己整除