剑指Offer 43.1~n整数中1出现的次数 | LeetCode 233.数字1的个数 （Python）

剑指Offer 43.1~n整数中1出现的次数

给定一个整数n，计算所有小于等于n的非负整数中数字1出现的个数。

输入： 13
输出： 3
解释： 数字1出现在以下数字中：1，10，11，12，13

LeetCode 233.数字1的个数

两题是同一个题。

解题思路

老实说，我本人很怕做这类型的题目，需要找到数学规律，还得保证代码的逻辑性。
解决这个问题需要理解一个核心概念：
对于每一个位的数字，受到当前位，高位以及低位三方面的影响。

下面举例子来说明，假设输入为101314，先来看看十位：

输入：101314
当前位的数字：1
高位：1013
低位：14

我们可以先观察：
10～100中，十位上出现1的有10, 11, 12, 13, 14, 15, 16, 17, 18, 19这10个数字
100～200中，十位上出现1的有110, 111, 112, 113, 114, 115, 116, 117, 118, 119这10个数字
...
1000~1100中，十位上出现1的有1010，1011,1012,1013,1014,1015,1016,1017,1018,1019这10个数字
得到一条规律：
我们在不考虑其他位置的情况下（如百位、千位），每100（其实是10~20内）有10个十位上为1的数字。

因此我们可以将101314划分为101300和14来看：
对于高位1013来说，也就是我们有1013个100，那么高位决定的数字有1013 X 10 = 10130；
对于低位4来说，十位出现1的只有10, 11，12, 13, 14这5个数字。

为什么低位是5个？
这点非常重要，如果当前十位上是2，那么就有10个了（10~20内）；
事实上当前十位上是1，所以没有“完整”的10个数字。

结论：高位+低位有10135个数字

当前位的数字大于1时，情况又会稍微有点不一样，现在我们来看看百位：

输入：101314
当前位：3
高位：101
低位：314

同样我们可以推导得出：每1000个数字（其实是100~200内），百位上出现1的有100个。

我们将101314分为10100和314来看：
而对于高位101来说，也就是我们有101个1000，百位出现1的数字有101 × 100 = 10100个；
对于低位313来说，因为已经包含了100~200这个区间，所以也有100个；
因此101314百位上出现1的数字有10100 + 100 = 10200个。

还有一种特殊情况，就是当前位等于0，现在我们来看看万位：

输入：101314
当前位：0
高位（比十位高的数字）：1
低位（比十位低的数字）：1314

这种情况下，对于高位1来说，只有10000~20000中的1w个数字，
而低位1314还没进入10000~20000，所以不会有。

因此，我们可以按照当前位是否等于1，是否大于1，是否等于0（是否小于1），分为3种情况：
最终得到：

个位出现1的个数： 10132个
十位出现1的个数： 10135个
百位出现1的个数： 10200个
千位出现1的个数： 10315个
万位出现1的个数： 10000个
十万位出现1的个数： 1315个

代码解析

class Solution:
    def countDigitOne(self, n: int) -> int:
        if n <= 0 : return 0
        
        operator = 1
        count = 0
        
        while n // operator:
            curr = n % (operator * 10) // operator
            high = n // (operator * 10)
            low = n % (operator)
            
            # 根据当前位的3种情况，进行计数
            if curr == 1:
                count += high * operator + low + 1
            if curr == 0:
                count += high * operator
            if curr > 1:
                count += (high+1) * operator
            
            operator *= 10
        
        return count

Q&A

1.会不会存在重复计算的问题？

题目要求的是求数字1的个数。虽然110百位上和十位上都为1，但求的是每位上为1的个数。
110这一个数字算两次而不是一次，因此不会存在重复的情况。

2.除法要用//取整

在Python2中除法运算符默认取整；而在Python3中则不是，因此要用//运算符。

2019.7.23 修改例子表述

最后

以上就是强健硬币为你收集整理的剑指Offer 43.1~n整数中1出现的次数 | LeetCode 233.数字1的个数 （Python）的全部内容，希望文章能够帮你解决剑指Offer 43.1~n整数中1出现的次数 | LeetCode 233.数字1的个数 （Python）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。