[LeetCode]728. Self Dividing Numbers

发表于 | 分类于 | 评论数： | 阅读次数：
字数统计：492 字 | 阅读时长：3 分钟

728. Self Dividing Numbers

Easy

A self-dividing number is a number that is divisible by every digit it contains.

For example, 128 is a self-dividing number because 128 % 1 == 0, 128 % 2 == 0, and 128 % 8 == 0.

Also, a self-dividing number is not allowed to contain the digit zero.

Given a lower and upper number bound, output a list of every possible self dividing number, including the bounds if possible.

Example 1:

1
2
3
Input: 
left = 1, right = 22
Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22]

Note:

The boundaries of each input argument are 1 <= left <= right <= 10000.

题目解释：判断一个数是否是自除数，即数字对各个位的上数取余等于0；

方案一

思路：遍历所有数，并遍历每个数的每个位进行取余操作；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> selfDividingNumbers(int left, int right) {
        vector<int> output;
        for (int item = left; item <=right; ++item) {
            int out = item;
            bool is_valid = true;
            while (out && is_valid) {
                const int remain = out % 10;
                if (remain == 0 || item % remain) {
                    is_valid = false;
                }
                out /= 10;
            }
            if (is_valid) {
                output.push_back(item);
            }
        }
        return output;
    }
};

result:

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Self Dividing Numbers.

Memory Usage: 8.5 MB, less than 30.71% of C++ online submissions for Self Dividing Numbers.

方案二

数字用string转换，再遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> selfDividingNumbers(int left, int right) {
        vector<int> output;
        for (int item = left; item <=right; ++item) {
            const string str = to_string(item);
            bool is_valid = true;
            for (const char ch : str) {
                if(ch == '0' || item % (ch - '0')) {
                    is_valid = false;
                }
            }
            if (is_valid) {
                output.push_back(item);
            }
        }
        return output;
    }
};

result

Runtime: 8 ms, faster than 30.71% of C++ online submissions for Self Dividing Numbers.

Memory Usage: 8.6 MB, less than 21.41% of C++ online submissions for Self Dividing Numbers.

虽然可行，但是效率还是差了点；

讨论区还有对应的使用固定大小数组进行判断的方案，在空间占用上会相对优势些：

Correct C++ Solution(Numbers up to 9999) Better than 100% in runtime and 95% in storage-Better-than-100-in-runtime-and-95-in-storage>)

执行结果如下：

Runtime: 4 ms, faster than 86.79% of C++ online submissions for Self Dividing Numbers.

Memory Usage: 8.4 MB, less than 67.63% of C++ online submissions for Self Dividing Numbers.