这两天看到一个很有意思的面试题:考官直接问,1 到 1000 到多少个 7?

要求,不编程,直接给出答案,并简单给出思路。

 

C/C++的学习裙【七一二 二八四 七零五 】,无论你是小白还是进阶者,是想转行还是想入行都可以来了解一起进步一起学习!裙内有开发工具,很多干货和技术资料分享!

 

第一种思路

首先应该有个合理的归类,我一开始就想到了一个合理的分类法,即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次。

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

总结

 

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

 

内容来源于网络如有侵权请私信删除

文章来源: 博客园

原文链接: https://www.cnblogs.com/zm131417-/p/14286197.html

你还没有登录,请先登录注册
  • 还没有人评论,欢迎说说您的想法!

相关课程

3637 49元 98元 5折