本篇為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
, and128 % 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;
}
沒有留言:
張貼留言