欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

剑指offer:Python 整数中1出现的次数(从1到n整数中1出现的次数)图解 绝对让你看懂!

程序员文章站 2024-03-07 18:30:45
...

题目描述

求出1 ~ 13的整数中1出现的次数,并算出100 ~ 1300的整数中1出现的次数?1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。请把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数(从1 到 n 中1出现的次数)。

思路和Python实现

看了下Python的解法,有投机心的,用字符串统计,或者用递归之类的,但是想想如果给的数是亿计呢?于是整理了其他的思路

思路一

详细图解 逐位遍历

  • 准备工作:假设 指针 代表当前位置,设为:midele_value,指针从最后的1位开始向左移动,每次以指针划分,分为三个部分,指针左侧为:高位区 high_value,指针右边:低位区 low_value;指针不断的移动,每次midele_value遇到的值,分为三类:0 ,1 ,2~9 ,下面分别讨论1可能出现的个数。

  • 移动时,如果遇上0,如下图,假如要让它变成1,那么 34591… 这样就比原来的数大了,所以出现1的情况,只能是前面各位为:3458 “1” 变化,从0~3458 总共有 3459个数(可以取0,即这个数是182190),结果发现就是前面存在的数(即是高位high_value),低位区总共的可能数是,有多少位数,每一位数都可以有0 ~ 9 的变化,加上所在位,就是 10 ^(后面的位数)。
    所以总共出现1的次数为:高位 * 10 ^(后面的位数)
    剑指offer:Python 整数中1出现的次数(从1到n整数中1出现的次数)图解 绝对让你看懂!

  • 移动时,如果遇到 2 ~ 9 的数,如下图,指针指向的数不需要借位,可以直接34590 “8”变化,所以前面总共有:0~34590 总共34591个数,
    即是:(高位+1)* 10 ^(后面的位数)
    剑指offer:Python 整数中1出现的次数(从1到n整数中1出现的次数)图解 绝对让你看懂!

  • 移动时,如果遇到 1,如下图,因为1就是我们要找的,所以可以这样,将1变成0,这样原来的数需要加上midele_value后面位数的数值,图中将1变成0就是:34590820 000 + 190 ;这样就变成了指针还是指向0的情况,那么按照前面得出的34590820 000 就是:高位 * 10 ^(后面的位数);紧接着,还有 指针+低位区 还没处理,190 ,指针指向1时所有出现1的可能为 100~190 总共 91个数,即是低位区+1。
    所以得出:高位 * 10 ^(后面的位数)+ 低位区 + 1
    剑指offer:Python 整数中1出现的次数(从1到n整数中1出现的次数)图解 绝对让你看懂!

  • 具体实现需要解决的问题:
    设置一个preceise移动指针,让它初始等于1,每次向左移动一位需要让它增大10倍,即是:preceise = preceise * 10 ,不断的循环移动,那么
    指针 所分成的三块区域 不断变化过程如下图:
    剑指offer:Python 整数中1出现的次数(从1到n整数中1出现的次数)图解 绝对让你看懂!
    剑指offer:Python 整数中1出现的次数(从1到n整数中1出现的次数)图解 绝对让你看懂!
    剑指offer:Python 整数中1出现的次数(从1到n整数中1出现的次数)图解 绝对让你看懂!

  • 如下图:高位区 等于0 ,指针指向最左侧的数,那么循环就结束
    剑指offer:Python 整数中1出现的次数(从1到n整数中1出现的次数)图解 绝对让你看懂!

  • 以 preceise =1 的情况考虑,它将数分成三块区域:high_value,midele_value 以及0,所以根据取一个数的每一个数的方法可以得出通式:
    high_value = n // (10 * preceise)
    midele_value = (n // preceise) % 10
    low_value = n % preceise
    preceise = preceise * 10

    (可以联想一下判回文数和水仙花数,是如何取到每一位的方法来思考该如何实现这个)

class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        preceise = 1
        high_value = 1
        # midele_value = 1
        # low_value = 1
        count = 0
        sum_num = 0
        while high_value != 0:
            high_value = n // (10 * preceise)
            midele_value = (n // preceise) % 10
            low_value = n % preceise
            preceise = preceise * 10

            if midele_value == 0:
                num = high_value * pow(10, count)
            elif midele_value > 1:
                num = (high_value + 1) * pow(10, count)
            else:
                num = high_value * pow(10, count) + low_value + 1
            sum_num += num
            count += 1
        return sum_num


obj = Solution()
print(obj.NumberOf1Between1AndN_Solution(131))

逐位遍历,其他思路

假设一个数 n = abcde ,其中abcde分别为十进制中各位上的数字。
如果要计算百位上1出现的次数,它要受到3方面的影响:百位上的数字,百位以下(低位)的数字,百位以上(高位)的数字。

  • 如果百位上数字为0,百位上可能出现1的次数由更高位决定。比如:12013,则可以知道百位出现1的情况可能是:100-199,1100-1199,2100-2199,……,11100-11199,一共1200个。正好等于更高位数字(12)乘以 当前位数(100)。
  • 如果百位上数字为1,百位上可能出现1的次数不仅受更高位影响还受低位影响。比如:12113,则可以知道百位受高位影响出现的情况是:100-199,1100-1199,2100-2199,…,11100-11199,一共1200个。等于更高位数字(12)乘以 当前位数(100)。但同时由于低位为13,百位出现1的情况还可能是:12100~12113,一共14个,等于低位数字(13)+1。
  • 如果百位上数字大于1(2-9),则百位上出现1的情况仅由更高位决定,比如12213,则百位出现1的情况是:100-199,1100-1199,2100-2199,…,11100-11199,12100-12199,一共有1300个,等于更高位数字+1(12+1)乘以当前位数(100)。
  • 从最低位开始,逐位遍历,统计出现1的次数
class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        i = 1  # 记录位数
        current = 0  # 记录当前位上的数
        before = 0  # 记录前边的数
        after = 0  # 记录后边的数
        count = 0  # 记录1出现的个数
        while (n // i) != 0:  # 位数到最高位为止
            current = ((n % (i * 10)) - (n % i)) / i
            before = n % i
            after = n // (i * 10)
            if current == 0:
                count += after * i
            elif current == 1:
                count += after * i + before + 1
            else:
                count += (after + 1) * i
            i = i * 10  # 每次循环,位数乘10
        return count


obj = Solution()
print(obj.NumberOf1Between1AndN_Solution(131))

思路二

数学归纳
整理来自:https://www.nowcoder.com/questionTerminal/bd7f978302044eee894445e244c7eee6

  • 个位:
    我们知道在个位数上,1会每隔10出现一次,例如1、11、21等等,我们发现以10为一个阶梯的话,每一个完整的阶梯里面都有一个1,例如数字22,按照10为间隔来分三个阶梯,在完整阶梯0-9,10-19之中都有一个1,但是19之后有一个不完整的阶梯,我们需要去判断这个阶梯中会不会出现1,易推断知,如果最后这个露出来的部分小于1,则不可能出现1(这个归纳换做其它数字也成立)。

    我们可以归纳个位上1出现的个数为:n/10 * 1+(n%10!=0 ? 1 : 0)

  • 十位
    现在说十位数,十位数上出现1的情况应该是10-19,依然沿用分析个位数时候的阶梯理论,我们知道10-19这组数,每隔100出现一次,这次我们的阶梯是100,例如数字317,分析有阶梯0-99,100-199,200-299三段完整阶梯,每一段阶梯里面都会出现10次1(从10-19),最后分析露出来的那段不完整的阶梯。我们考虑如果露出来的数大于19,那么直接算10个1就行了,因为10-19肯定会出现;如果小于10,那么肯定不会出现十位数的1;如果在10-19之间的,我们计算结果应该是k - 10 + 1。例如我们分析300-317,17个数字,1出现的个数应该是17-10+1=8个。

    那么现在可以归纳:十位上1出现的个数为:
    设k = n % 100,即为不完整阶梯段的数字
    归纳式为:(n / 100) * 10 + (if(k > 19) 10 else if(k < 10) 0 else k - 10 + 1)

  • 百位
    现在说百位1,我们知道在百位,100-199都会出现百位1,一共出现100次,阶梯间隔为1000,100-199这组数,每隔1000就会出现一次。这次假设我们的数为2139。跟上述思想一致,先算阶梯数 * 完整阶梯中1在百位出现的个数,即n/1000 * 100得到前两个阶梯中1的个数,那么再算漏出来的部分139,沿用上述思想,不完整阶梯数k199,得到100个百位1,100<=k<=199则得到k - 100 + 1个百位1。

    那么继续归纳百位上出现1的个数:

    设k = n % 1000
    归纳式为:(n / 1000) * 100 + (if(k >199) 100 else if(k < 100) 0 else k - 100 + 1)
    剑指offer:Python 整数中1出现的次数(从1到n整数中1出现的次数)图解 绝对让你看懂!

class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        i = 1  # 从个位开始计算,也可以从高为往低位计算
        count = 0  # 1的数量初始化为1
        while i <= n:  # 和n比较大小
            count += (n // (i*10))*i + (lambda x: min(max(x-i+1, 0), i))(n%(i*10))  
            # 个位,十位等1的个数整除去整,余数上1的个数采用匿名函数,简单一点,也可以使用if else
            i = i * 10  # 计算下一位的1的个数
        return count  # 返回