【面试题】1到1000有多少个7?

作者: veaxen 分类: 笔试面试 发布时间: 2017-08-01 21:00

考官直接问,1到1000到多少个7?
要求,不编程,直接给出答案,并简单给出思路。

————————第一种思路——————————
首先应该有个合理的归类,我一开始就想到了一个合理的分类法,即
1到1000,每个数都看作3位数,而1000明显没有7,不考虑
那1看成001,19看成019,以此类推
这样每个数字可以用三个格子表示,就有了一个统一的表示方法
口口口

第一步,只考虑后面两个格子。
我最初只想第一种情况,X7,即07,17,一直到97,其中先不考虑77的特殊性(隔离的思想),这样从0~9有10个7,再考虑77,就有11个7。
还有一种情况,7X,即70,71,一直到79,情况同上,也有11个7。
这两种情况都算上了77里面的两个7,因此减去2。结果是22-2 = 20。

第二步,考虑第一个格子。
第一个格子,从0~9,即有10种上述情况,其中7比较特殊,我们先不把它当作7(隔离的思想),那么情况简单了,一共有10*20 = 200个7。

第三步,考虑刚才被隔离掉的7。
这一步容易想歪,觉得是不是+20呢? 其实应该仔细想下,701, 719, 722这些都多了1个7,那777呢?仔细想下,777里面的后面2个7也是前面已经算过了。
那就很明朗了。就是刚才的隔离,仅仅忽略了从00~99这100个数中前面含一个7的情况。
所以,最后的答案是200+100 = 300。

假定前面的结果用f(3)表示
不难归纳,1到10000,即f(4) = 10*f(3) + 1000即4000

————————另外一种思路——————————
题目问有多少个7,如果问有多少1,或者2,或者9呢?不难猜想1~9情况是一样的。先忽略掉1000里面多的一个1。
有没有可能求出有多少个0,然后再求出1~1000这些数字的字符总数,再减去0的个数后,再除以9呢?

第一步:求1~1000这些数字的字符总数
1位数,9个
2位数,90个2 = 180个(1~99有99个,减去9)
3位数,900个
3 = 2700个(类似上面10~99,这里是100~999)
4位数,1*4 = 4
总数是2700+180+9+4 = 2893个字符

第二步:求有多少个0
1位数,没有
2位数,只考虑X0的情况,从10~99,有9个
3位数,要考虑0X和X0两种情况,各11个,减去重复的2个,即211-2 = 20, 从100~999有9种情况,即920 = 180个
4位数,3个0
那结果是2700+180+9+4 - 180+9-3 = 2701个
这样减去1000里面多的那个1,刚好是2700个了。
那结果好办了,不考虑这个1,1~9都是出现2700/9 = 300次。

这个解法是间接求,比直接求更麻烦了些。

总结就是:
表示方法和分类很重要,多采用隔离法(高中物理最好用的方法之一),可以做到简化问题,方便分析。

如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!

一条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注