LeetCode Self Dividing Numbers

本篇為LeetCode上演算法的簡單問題，Self Dividing Numbers。

題目如下：

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:

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.

此題輸入一整數陣列（陣列的整數範圍大於等於1，小於等於1000），判斷每個整數是否可被自身的每一位數的數所整除（也就是餘數等餘0）。位數有0的數不考慮，例如20不算，因為無法被個位數0整除。若該整數可以被自身所有的位數所整除，則加入陣列並回傳。

第一次想到的解法，轉成String然後拆成每一位數來除上數本身看是否整除。

public static List<Integer> selfDividingNumbers(int left, int right) {

    List<Integer> list = new ArrayList<>();
    A: for (; left <= right; left++) {
        if (left % 10 == 0)
            continue;

        for (char c : Integer.toString(left).toCharArray()) {
            int selfNumber = c - '0';
            if (selfNumber == 0 || left % selfNumber > 0) {
                continue A;
            }
        }
        list.add(left);
    }

    return list;
}

但上面的速度仍不夠好，因為使用Integer.toString將整數轉成字串時會消耗太多計算，改以餘數運算子取得每位數的數來除。

public static List<Integer> selfDividingNumbers(int left, int right) {

    List<Integer> list = new ArrayList<>();
    for (; left <= right; left++) {
        if (isSelfDivided(left)) {
            list.add(left);
        }
    }

    return list;
}

public static boolean isSelfDivided(int number) {
    if (number < 1) {
        return false;
    }
    int temp = number;
    while (temp >= 10) {
        int digit = temp % 10;
        if (digit == 0) {
            return false;
        } else if (number % digit != 0) {
            return false;
        }
        temp /= 10;
    }
    return number % temp == 0;
}