0728-自除数

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:31 2023-09-13 16:06:31 Updated    

自除数 _ _ 是指可以被它包含的每一位数整除的数。

  • 例如，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

方法一：直接判断

遍历范围 [\textit{left}, \textit{right}] 内的所有整数，分别判断每个整数是否为自除数。

根据自除数的定义，如果一个整数不包含 0 且能被它包含的每一位数整除，则该整数是自除数。判断一个整数是否为自除数的方法是遍历整数的每一位，判断每一位数是否为 0 以及是否可以整除该整数。

遍历整数的每一位的方法是，每次将当前整数对 10 取模即可得到当前整数的最后一位，然后将整数除以 10。重复该操作，直到当前整数变成 0 时即遍历了整数的每一位。

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
class Solution:
    def selfDividingNumbers(self, left: int, right: int) -> List[int]:
        def isSelfDividing(num: int) -> bool:
            x = num
            while x:
                x, d = divmod(x, 10)
                if d == 0 or num % d:
                    return False
            return True
        return [i for i in range(left, right + 1) if isSelfDividing(i)]
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public List<Integer> selfDividingNumbers(int left, int right) {
        List<Integer> ans = new ArrayList<Integer>();
        for (int i = left; i <= right; i++) {
            if (isSelfDividing(i)) {
                ans.add(i);
            }
        }
        return ans;
    }

    public boolean isSelfDividing(int num) {
        int temp = num;
        while (temp > 0) {
            int digit = temp % 10;
            if (digit == 0 || num % digit != 0) {
                return false;
            }
            temp /= 10;
        }
        return true;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public IList<int> SelfDividingNumbers(int left, int right) {
        IList<int> ans = new List<int>();
        for (int i = left; i <= right; i++) {
            if (IsSelfDividing(i)) {
                ans.Add(i);
            }
        }
        return ans;
    }

    public bool IsSelfDividing(int num) {
        int temp = num;
        while (temp > 0) {
            int digit = temp % 10;
            if (digit == 0 || num % digit != 0) {
                return false;
            }
            temp /= 10;
        }
        return true;
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    bool isSelfDividing(int num) {
        int temp = num;
        while (temp > 0) {
            int digit = temp % 10;
            if (digit == 0 || num % digit != 0) {
                return false;
            }
            temp /= 10;
        }
        return true;
    }

    vector<int> selfDividingNumbers(int left, int right) {
        vector<int> ans;
        for (int i = left; i <= right; i++) {
            if (isSelfDividing(i)) {
                ans.emplace_back(i);
            }
        }
        return ans;
    }
};
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
bool isSelfDividing(int num) {
    int temp = num;
    while (temp > 0) {
        int digit = temp % 10;
        if (digit == 0 || num % digit != 0) {
            return false;
        }
        temp /= 10;
    }
    return true;
}

int* selfDividingNumbers(int left, int right, int* returnSize){
    int * ans = (int *)malloc(sizeof(int) * (right - left + 1));
    int pos = 0;
    for (int i = left; i <= right; i++) {
        if (isSelfDividing(i)) {
            ans[pos++] = i;
        }
    }
    *returnSize = pos;
    return ans;
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var selfDividingNumbers = function(left, right) {
    const ans = [];
    for (let i = left; i <= right; i++) {
        if (isSelfDividing(i)) {
            ans.push(i);
        }
    }
    return ans;
}

const isSelfDividing = (num) => {
    let temp = num;
    while (temp > 0) {
        const digit = temp % 10;
        if (digit === 0 || num % digit !== 0) {
            return false;
        }
        temp = Math.floor(temp / 10);
    }
    return true;
};
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func isSelfDividing(num int) bool {
    for x := num; x > 0; x /= 10 {
        if d := x % 10; d == 0 || num%d != 0 {
            return false
        }
    }
    return true
}

func selfDividingNumbers(left, right int) (ans []int) {
    for i := left; i <= right; i++ {
        if isSelfDividing(i) {
            ans = append(ans, i)
        }
    }
    return
}

复杂度分析

  • 时间复杂度：O(n \log \textit{right})，其中 n 是范围内的整数个数，right 是范围内的最大整数。对于范围内的每个整数，需要 O(\log \textit{right}) 的时间判断是否为自除数。

  • 空间复杂度：O(1)。除了返回值以外，使用的额外空间为 O(1)。

 Comments
On this page
0728-自除数