SelfDividingNumbers [source code]

public class SelfDividingNumbers {
static
/******************************************************************************/
class Solution {
    public List<Integer> selfDividingNumbers(int left, int right) {
        List<Integer> res_ls = new ArrayList<> ();
        assert left <= right && 1 <= left && right <= 10000;
        for (int i = left; i <= right; i++) {
            if (is_num_valid (i))
                res_ls.add (i);
        }
        return res_ls;
    }

    public boolean is_num_valid (int num) {
        int n = num;
        while (num > 0) {
            int digit = num % 10;
            if (digit == 0 || (n % digit) != 0)
                return false;
            num /= 10;
        }
        return true;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        SelfDividingNumbers.Solution tester = new SelfDividingNumbers.Solution();
    }
}

这个是一个easy的题目, 所以笨办法其实是很简单的, 就是在这个range里面, 对每一个数字进行判断就行了; 但是这里要潜意识里意识到一个可能的提升空间, 就是这个题目展开的方式, 看起来好像他在鼓励你用check a number的方式来完成generate numbers的任务, 但是这样的做法真的是最好的吗? 当基本的mechanism跟实际上最后的题目目标有点区别的时候, 很多时候, 理解这个区别带来的方法的变化, 往往能够解决复杂度的瓶颈;

我现在又在尝试这种跳跃式的思考方式了; 思考了一会儿, 完全没有思路; 那么这个时候就fallback到下一个方法: 先尽可能细致的模拟出笨办法的做法, 然后在这个实现的过程中, 去寻找优化的可能性;

我们现在要做的是生成一个list, 那么如果单纯的穷举, 最后你就需要对每一个range内的数字都进行一个拆分digit然后divide的操作; 如果想要在这个aggregate的过程当中达到复杂度的优化, 那么一个可能的角度就是找到重复工作; 比如这里, 相同的digit可能会被range里面不同的数字进行多次的divide, 这个是否可以利用?

想了半天想不出来, 直接开始写笨办法;

笨办法倒是一次就通过了, 没有什么意外的地方; 速度是6ms (64%), 倒是不是显得很慢, 所以这题的最优解也没有多先进?

editorial里面只给了一个naive的解法:

class Solution {  
    public List<Integer> selfDividingNumbers(int left, int right) {  
        List<Integer> ans = new ArrayList();  
        for (int n = left; n <= right; ++n) {  
            if (selfDividing(n)) ans.add(n);  
        }  
        return ans;  
    }  
    public boolean selfDividing(int n) {  
        for (char c: String.valueOf(n).toCharArray()) {  
            if (c == '0' || (n % (c - '0') > 0))  
                return false;  
        }  
        return true;  
    }  

    // Alternate implementation of selfDividing:  
    // public boolean selfDividing(int n) {  
    //     int x = n;  
    //     while (x > 0) {  
    //         int d = x % 10;  
    //         x /= 10;  
    //         if (d == 0 || (n % d) > 0) return false;  
    //     }  
    //     return true;  

}

注意他这里检查divide的做法, 有一个更简单的方法就是不用数学来拆分digit, 直接用string来做, 这个想法也是没有问题的, 而且其实也很方便;

submission里面基本也就是这个解法了; 也有无聊蛋疼的直接用穷举的方法来做, 不过这个就很无聊了;

discussion也没有什么特别好的东西, 这个题目好像是上个月才出来的新题目, 所以现在基本就是没有什么好解法流出来;

Problem Description

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.

Difficulty:Easy
Total Accepted:13.7K
Total Submissions:20.2K
Contributor:jkl0619
Companies
epic systems
Related Topics
math
Similar Questions
Perfect Number

Hint 1

For each number in the range, check whether it is self dividing by converting that number to a character array (or string in Python), then checking that each digit is nonzero and divides the original number.