JZ43 从1到n整数中1出现的次数

发表于 分类于 本文字数： 805 阅读时长 ≈ 3 分钟

JZ43 从1到n整数中1出现的次数

描述

输入一个整数 n ，求 1～n 这 n 个整数的十进制表示中 1 出现的次数

例如， 1~13 中包含 1 的数字有 1 、 10 、 11 、 12 、 13 因此共出现 6 次

注意：11 这种情况算两次

数据范围： $1≤n≤30000$

进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(lognn)$

示例1 

1
2
输入：13
返回值：6

示例2

1
2
输入：0
返回值：0

题解

两种有趣的解法，首先是把数字转换为字符串拼接起来，然后统计1的个数即可。

1
2
3
4
5
6
7
8
# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        str_n = ''
        for i in range(1, n + 1):
            str_n += str(i)
        res = str_n.count('1')
        return res

另一种则是逐位求得该位可能为1的情况再累加，此时分三种情况：

$以514036为例，百位B=0时$

1
2
3
因为要使得B处等于1，所以左侧不能是，因为5141CC一定大于5140CC
所以左侧可能的取值为[0,513]，右侧可能的取值为[0,99]
所以此时B可能为1的情况有514*(99+1)种

$以514136为例，百位B=1时$

1
2
3
同理我们可以分析到当左侧为514且B=1时，右侧只可能位于[0,36]之间，此时有36种情况
再加上左侧不为514的情况，与前面所述相同，当左侧不取514时，右侧的取值范围就是[0,99]
所以此时可能的情况有(36+1) + (514+(99+1)

$以514436为例，百位B>1时$

1
2
与B=0时相似，但是此时左侧可以取到514,故左侧取值为[0,514],右侧分析相同
此时情况总共有(514+1)*(99+1)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
    # 利用组合数解题
    # 依次遍历每一个数位，计算该位为1的数有多少个，将结果累加返回
    # 每个数位计算的时候，对除去该位的前缀，后缀分别计算组合数
    # 同时需要保证组合出的数字在n的范围之内，所以将情况分为三种，该数位原本为1或者为0，或者为其他
class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        # write code here
        if n == 1:  # 边界情况
            return 1
        ans = 0  # 最后返回的1的个数
        x = str(n)  # n的字符串形式，便于前缀后缀的数字转换
        for i in range(len(x)):  # 遍历每一个数位，计算该数位为1同时整个数在n之内的整数个数
            pre = int(x[:i]) if x[:i] else 0  # 前缀，没有前缀为0
            l = len(x[i + 1:])  # 后缀的长度
            # 该位原本为0的时候，合法数的前缀必小于pre，范围为[0,pre)，共有pre种，后缀任意均合法，共有10**l种
            if x[i] == '0':
                ans += pre * 10 ** l
            # 该位原本为1的时候，合法数有两种
            # 一种是前缀范围为[0,pre)，共有pre种，后缀任意
            # 另一种是前缀为pre，后缀范围[0,suf]，共suf+1种
            elif x[i] == '1':
                suf = int(x[i+1:]) if x[i+1:] else -1  # 后缀范围，没有后缀为-1
                ans += pre * 10 ** l + suf + 1
            # 其他情况下，合法数前缀范围[0,pre]，后缀任意
            else:
                ans += (pre+1) * 10 ** l
        return ans