Leetcode之2出现的次数

115 阅读 0 评论 76 点赞

我是靠谱客的博主喜悦百褶裙，这篇文章主要介绍Leetcode之2出现的次数，现在分享给大家，希望可以做个参考。

题目：

编写一个方法，计算从 0 到 n (含 n) 中数字 2 出现的次数。

示例:

输入: 25
输出: 9
解释: (2, 12, 20, 21, 22, 23, 24, 25)(注意 22 应该算作两次)
提示：

n <= 10^9

代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def numberOf2sInRange(self, n: int) -> int:
        s= str(n) 
        x= 2
        count = 0
        for i in range(len(s)):
            current = int(s[i])
            high = 0 if s[:i]=='' else int(s[:i])
            low =0 if s[i+1:]=='' else int(s[i+1:])
            if current>x:
                count+=(high+1)*(10**len(s[i+1:]))
            elif current<x:
                count += (high) * (10 ** len(s[i + 1:]))
            else:
                count +=(high) * (10 ** len(s[i + 1:]))+low+1
        return count

想法：

算法核心思想是分别统计每位（个、十、百、千位等等）出现待查数（比如这道题的2）的次数，然后求和，实现O(n)复杂度

比如我们要统计下面三个数百位上出现2的次数，无非就三种情况，大于2，小于2，等于2

情况1（百位大于2），如：12313
要想百位出现2，由于当前百位是3，那么最终的次数只依赖于更高位
00200-00299 100个数
01200-01299 100个数
...
12200-12299 100个数
所有百位出现2的总个数为从0到12 共13个100，即13*100=1300
即百位3的左侧那部分12加上1共13个百位为1的总数，从0到12共13个数吧，手指头加上脚指头数一数哈，同样，从200到299共100个数哈
结论1：当前位大于2=（当前位的左边部分+1）*10**当前位的右半部分的长度，这里就是（12+1）*10**len('13') 那要是左半边为空即开头呢，如345百位是3也大于2，左边为空呢，为空就是0喽，直接就是(0+1)*10**len('45')，也就是200-299喽

情况2（百位小于2），如12113
要想百位出现2，由于当前位是1，那么最终的次数同样依赖于更高位，只不过会比上面的情况少最后一种
00200-00299 100个数
01200-01299 100个数
...
11200-11299 100个数
那么加起来就是（12）*10**len('13')
结论2：当前位小于2=（当前位的左边部分）*10**当前位的右半部分的长度，这里就是 12*10**len('13')

情况3（百位2等于2），如12213
这种情况稍微复杂那么一丢丢，百位出现2的情况不仅依赖于左半边，还依赖于右半边，不过想通了也就不难了
我们可以将这个数分成两部分：
首先我们取前三位不大于121的所有情况，就是上面的结论2
00200-00299 100个数
01200-01299 100个数
...
11200-11299 100个数，还是12*100个数，（12咋来的？从0到11共12个数哇，100咋来的？从0到99共100个数哇）
其次我们取前三位是122的情况，
12200-12213 这一共是14个数，总的加起来就是百位是2的所有情况了
结论三：当前位等于2=（当前位的左边部分）*10**当前位的右半部分的长度+当前位的右半部分+1 ，这里就是 12*10**len('13')+13+1 13+1就是从0到13共几个数