【剑指Offer】31整数中1出现的次数（从1到n整数中1出现的次数）

亦凉 2022-05-11 16:14 186阅读 0赞

## 题目描述 ##

求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。

时间限制：1秒；空间限制：32768K

## 解题思路 ##

### 思路一 ###

对于一个数s利用循环移位和除10取余数的方法记录出现了几次1，再对从1到n的所有数遍历记录结果。算法复杂度高。

# -*- coding:utf-8 -*-
    class Solution:
        def NumberOf1Between1AndN_Solution(self, n):
            # write code here
            count = 0
            while n > 0: #遍历1到n中每个数
                s = n
                while s > 0: #记录当前数s中1的个数
                    if s%10 == 1:
                        count += 1
                    s = s//10 #数s去掉最后一位
                n -= 1
            return count

### 思路二 ###

按位计算，记录每一位上会出现多少个1，累加返回结果。

# -*- coding:utf-8 -*-
    class Solution:
        def NumberOf1Between1AndN_Solution(self, n):
            # write code here
            count = 0 #记录结果
            tmp = n
            base = 1  #记录当前位数
            while tmp:
                last = tmp % 10 #最后一位数
                tmp = tmp / 10  #右移一位
                count += tmp * base
                # 最后一位为1的情况比较特殊，单独讨论
                if last == 1:
                    count += n % base + 1
                elif last > 1:
                    count += base
                base *= 10
            return count