算法题自除数-平芜编程栈

自除数

问题描述

自除数是指可以被它包含的每一位数整除的正整数。
例如，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]

算法思路

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

代码实现

方法一：逐位验证

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

num = 1：
- 位数：1
- 1 % 1 == 0
num = 2：
- 位数：2
- 2 % 2 == 0
num = 10：
- 位数：1, 0
- 包含0
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));// []}