题目描述:
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:
代码语言: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的整数倍。
但是整体来看这些规则未免有点复杂,所以最后笔者也就没有实现出来,在这里做一些想法记录。
同学们有其他想法的,欢迎在评论区留言!