标签: 数学
难度: Easy
自除数 是指可以被它包含的每一位数整除的数。
128 是一个 自除数 ，因为 128 % 1 == 0，128 % 2 == 0，128 % 8 == 0。自除数 不允许包含 0 。
给定两个整数 left 和 right ，返回一个列表，列表的元素是范围 [left, right] 内所有的 自除数 。
示例 1：
输入：left = 1, right = 22 输出：[1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22]
示例 2:
输入：left = 47, right = 85 输出：[48,55,66,77]
提示：
1 <= left <= right <= 104运行时间: 28 ms
内存: 15.9 MB
class Solution:
def selfDividingNumbers(self, left: int, right: int) -> List[int]:
ans=[]
for i in range(left,right+1):
use=i
flag=True
while(use!=0):
if (use%10 and i%(use%10)!=0) or (not use%10):
flag=False
break
use=use//10
if (flag) :
ans.append(i)
return ans
该题解的思路是遍历从 left 到 right 的所有整数，对于每个整数 i，判断它是否是自除数。判断的方法是不断对 i 进行整除 10 的操作，得到每一位数字，然后判断 i 是否能被每一位数字整除。如果出现任何一位数字为 0，或者 i 不能被某一位数字整除，则 i 不是自除数。如果 i 能被它的每一位数字整除，则将其加入到结果列表中。
时间复杂度: O(n * logr)
空间复杂度: O(n)
class Solution:
def selfDividingNumbers(self, left: int, right: int) -> List[int]:
ans = []
for i in range(left, right + 1):
use = i
flag = True
while use != 0:
# 判断当前位数字是否为 0，或者 i 是否不能被当前位数字整除
if (use % 10 and i % (use % 10) != 0) or (not use % 10):
flag = False
break
use = use // 10
# 如果 i 是自除数，则将其加入结果列表
if flag:
ans.append(i)
return ans
在算法实现中，对于每一个整数i，通过不断地进行取余操作（use % 10）来获取i的最低位。紧接着进行了一个判断：如果当前位（即 use % 10）为0，则立即将该数标记为非自除数并终止当前数的进一步检查。这样的处理确保了当遇到数字0时，程序不会尝试执行除以0的操作，从而避免了运行错误。
采用从右到左的方式检查每一位数字主要是因为这种方法可以直接通过取余和整除操作来实现，操作简单且直接。对于整数i，通过不断对10进行取余可以获取当前最低位，之后再通过整除10操作去除最低位，这样可以顺序地检查每一位数。这种方式在实现上不需要额外的数据结构，例如数组或字符串，而且可以即时地判断每一位是否符合自除数的条件，效率较高。
在这种情况下，尽管left和right非常接近，算法仍然需要检查每个数的每一位来确定是否是自除数。对于大数字，这意味着每个数字都需要进行多次除法和取余操作，这可能会导致计算量增大。然而，由于检查的数的范围较小（例如只有11个数字从9990到10000），总体计算量仍然是可管理的。但是，如果区间内的数字都很大且数量较多，算法的性能可能会受到影响。
现有的算法在理论上可以处理任何范围的数，但是随着数字大小的增加，每个数字的位数也会增长，这将导致更多的取余和整除操作，从而影响算法的效率。如果要处理更大的数，可以考虑以下优化：1. 使用并行处理技术来同时检查多个数字，特别是在多核处理器上。2. 预先筛选掉包含0的数，因为这些数字一定不是自除数，可以减少不必要的检查。3. 优化数字分解的逻辑，可能通过一些数学技巧减少操作数。4. 考虑使用更高效的编程语言或工具，以便更快地处理大型数据。