Easy

题目描述

自除数是指一个数能被它包含的每一位数字整除。

例如，128 是一个自除数，因为 128 % 1 == 0，128 % 2 == 0，128 % 8 == 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
  • 对于范围内的每个数字，通过将该数字转换为字符数组（或 Python 中的字符串）来检查它是否为自除数，然后检查每个数字是否非零并且能整除原数字。

解题思路

这道题需要判断一个数是否为自除数，然后找出给定范围内所有的自除数。

解题思路：

  1. 暴力遍历法：遍历 [left, right] 范围内的每个数，对每个数判断是否为自除数
  2. 自除数判断：对于每个数字，需要提取它的每一位数字，检查是否满足以下条件：
    • 该位数字不为 0（题目要求）
    • 原数字能被该位数字整除

具体实现步骤：

  • 遍历范围内每个数字
  • 对每个数字，通过取模和除法操作逐位提取数字
  • 检查每一位是否为 0，如果是则跳过该数字
  • 检查原数字是否能被该位数字整除，如果不能则跳过
  • 如果所有位数字都满足条件，则将该数字加入结果

时间复杂度主要取决于数字的位数，由于题目限制最大为 10^4，所以每个数字最多 4 位，效率较高。

这是一个直接的模拟题，没有复杂的算法技巧，重点在于正确实现数字的位数提取和判断逻辑。

代码实现

class Solution {
public:
    vector<int> selfDividingNumbers(int left, int right) {
        vector<int> result;
        
        for (int num = left; num <= right; num++) {
            if (isSelfDividing(num)) {
                result.push_back(num);
            }
        }
        
        return result;
    }
    
private:
    bool isSelfDividing(int num) {
        int original = num;
        
        while (num > 0) {
            int digit = num % 10;
            if (digit == 0 || original % digit != 0) {
                return false;
            }
            num /= 10;
        }
        
        return true;
    }
};

class Solution:
    def selfDividingNumbers(self, left: int, right: int) -> List[int]:
        def is_self_dividing(num):
            original = num
            while num > 0:
                digit = num % 10
                if digit == 0 or original % digit != 0:
                    return False
                num //= 10
            return True
        
        result = []
        for num in range(left, right + 1):
            if is_self_dividing(num):
                result.append(num)
        
        return result

public class Solution {
    public IList<int> SelfDividingNumbers(int left, int right) {
        var result = new List<int>();
        
        for (int num = left; num <= right; num++) {
            if (IsSelfDividing(num)) {
                result.Add(num);
            }
        }
        
        return result;
    }
    
    private bool IsSelfDividing(int num) {
        int original = num;
        
        while (num > 0) {
            int digit = num % 10;
            if (digit == 0 || original % digit != 0) {
                return false;
            }
            num /= 10;
        }
        
        return true;
    }
}

/**
 * @param {number} left
 * @param {number} right
 * @return {number[]}
 */
var selfDividingNumbers = function(left, right) {
    const result = [];
    
    for (let num = left; num <= right; num++) {
        if (isSelfDividing(num)) {
            result.push(num);
        }
    }
    
    return result;
};

function isSelfDividing(num) {
    const str = num.toString();
    
    for (let i = 0; i < str.length; i++) {
        const digit = parseInt(str[i]);
        if (digit === 0 || num % digit !== 0) {
            return false;
        }
    }
    
    return true;
}
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O((right - left + 1) × log₁₀(max(right)))
空间复杂度O(1)（不考虑输出数组的空间）

说明：

  • 时间复杂度：需要遍历 [left, right] 范围内的每个数字，对每个数字需要检查其每一位，数字的位数为 log₁₀(数字)
  • 空间复杂度：只使用了常数级别的额外空间来存储临时变量

相关题目