面试题:1 到 1000 之间有多少个 7?

共 1364字,需浏览 3分钟

 ·

2021-03-16 12:40

来源:architect19

https://blog.csdn.net/architect19/article/details/9398725

考官直接问,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次。

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


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

浏览 25
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报