728. 自除数
728. 自除数
题目
A self-dividing number is a number that is divisible by every digit it contains.
- For example,
128
is a self-dividing number because128 % 1 == 0
,128 % 2 == 0
, and128 % 8 == 0
.
A self-dividing number is not allowed to contain the digit zero.
Given two integers left
and right
, return a list of all theself- dividing numbers in the range [left, right]
(both inclusive).
Example 1:
Input: left = 1, right = 22
Output: [1,2,3,4,5,6,7,8,9,11,12,15,22]
Example 2:
Input: left = 47, right = 85
Output: [48,55,66,77]
Constraints:
1 <= left <= right <= 10^4
题目大意
自除数 是指可以被它包含的每一位数整除的数。
- 例如,
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 <= 10^4
解题思路
题目要求在 [left, right]
范围内找到所有 自除数。可以通过逐一枚举该范围内的数字,并使用辅助函数检查每个数字是否符合条件。
辅助函数
isSelfDividing
:- 输入一个数字
num
,判断它是否为 自除数。 - 对于每一位数字
digit
:- 如果
digit == 0
或者num % digit != 0
,返回false
。 - 如果数字满足条件,继续检查下一位,直到所有位都检查完。
- 如果
- 如果检查完所有位后未发现任何不符合条件的情况,则返回
true
。
- 输入一个数字
遍历范围
[left, right]
:- 对于每个数字
num
,调用辅助函数isSelfDividing
进行检查。 - 如果是 自除数,将其加入结果列表。
- 对于每个数字
返回结果:
- 返回包含所有 自除数 的列表。
复杂度分析
时间复杂度:
O(n * log_10(m))
,其中n
是范围内的数字个数,m
是最大值right
。- 外层遍历:范围
[left, right]
的数字,共n = right - left + 1
个。 - 内部检查:对于每个数字
num
,检查其位数,最多有log_10(num)
次操作。
- 外层遍历:范围
空间复杂度:
O(1)
,仅使用了常量空间。
代码
/**
* @param {number} left
* @param {number} right
* @return {number[]}
*/
var selfDividingNumbers = function (left, right) {
// 辅助函数:判断一个数字是否是自除数
const isSelfDividing = (num) => {
let temp = num;
while (temp > 0) {
const digit = temp % 10; // 提取当前最低位数字
if (digit === 0 || num % digit !== 0) {
// 包含0或者不能整除
return false;
}
temp = Math.floor(temp / 10); // 去掉最低位
}
return true;
};
const result = [];
for (let num = left; num <= right; num++) {
if (isSelfDividing(num)) {
result.push(num); // 满足条件加入结果
}
}
return result;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
507 | 完美数 | [✓] | 数学 | 🟢 | 🀄️ 🔗 |
2283 | 判断一个数的数字计数是否等于数位的值 | [✓] | 哈希表 字符串 计数 | 🟢 | 🀄️ 🔗 |
2520 | 统计能整除数字的位数 | 数学 | 🟢 | 🀄️ 🔗 |