leetcode-728-Self Dividing Numbers

2018-05-21 18:23:54 浏览数 (1)

题目描述:

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 == 0128 % 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:

代码语言:javascript复制
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.

要完成的函数:

vector<int> selfDividingNumbers(int left, int right) 

说明:

1、要判断一个数是不是可自分的,看该数字是不是可整除数字上的每一位。比如128可整除8,可整除2,可整除1,所以128可自分。

现在给定一个左界限和一个右界限,要求返回包含左界限和右界限在内的所有可自分数。

2、最简单的思路就是,从左界限开始,逐个判断是不是可自分数,直到右界限。

每个数判断的过程也很简单。如下述代码:

代码语言:javascript复制
    bool dividable(int a)
    {
        int b=a,t=0;
        while(b)
        {
            t=b;
            if(t==0||a%t!=0)//如果出现某一位是0或者不整除的情况
                return false;
            b/=10;
        }
        return true;
    }
    vector<int> selfDividingNumbers(int left, int right) 
    {
        vector<int>res;
        for(int i=left;i<=right;i  )
        {
            if(dividable(i))
                res.push_back(i);
        }
        return res;
    }

代码十分简单,实测4ms,beats 100% of cpp submissions。

3、一些其他想法(不太重要):

其实最开始的时候,笔者对于上述做法,觉得应该会超时的,可能还得像输出质数那道题一样,能够生成的就不要用逐个判断。

因此在想一些条件,比如10以内的数,全都是可自分的。

比如十几的数,要逐个判断。

比如二十几的数,只需要判断22,24,26,28,因为要整除十位的2,需要个位是2的整数倍。

比如三十几的数,只需要判断33,36,39,因为要整除十位的3,需要个位是3的整数倍。

四十几,就只有44,48。

五十几,就只有55。六十几,66。七十几,77。八十几,88。九十几,99。

一百以上的,从111开始考虑(之前都带0),百位是1不需要考虑,后面的十位和个位,和两位数一样的判断逻辑。

二百以上的,还是可以推出一些规则,比如248,后面的十位和个位需要是百位数值2的整数倍。

但是整体来看这些规则未免有点复杂,所以最后笔者也就没有实现出来,在这里做一些想法记录。

同学们有其他想法的,欢迎在评论区留言!

0 人点赞