《剑指offer》-31-整数1出现的次数

题目描述 求出1-13的整数中1出现的次数,并算出100-1300的整数中1出现的次数？为此他特别数了一下1-13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。 整数1出现的次数 1 、不考虑时间效率的解法很好理解，可以直接完成

class Solution: def NumberOf1Between1AndN_Solution(self, n): # write code here ret = 0 for i in range(n+1): for s in str(i): if s == '1': ret += 1 return ret

2、另一种思路-找规律 1位数，1-9中，1一共出现了1次； 2位数，10-99中，10-19的十位上一共出现了101=10次，对于每个十位开头的数字10-19、20-29，每个数个位上出现的是1-9中1出现的次数，共有9个区间91=9次； 3位数，100-999，100-199百位上出现了10**2=100次，对于每个百位数开头，例如100-199，200-299，低位上其实就是0-99这个区间上1出现的次数，一共9个区间 9*19=171次； 由此推测，对于1-9，10-99，100-999，每个n位数中包含1的个数公式为： f(1) = 1 f(2) = 9 * f(1) + 10 ** 1 f(3) = 9 * f(2) + 10 ** 2 f(n) = 9 * f(n-1) + 10 ** (n-1)

通过以上分析，我们可以确定对于任意一个给定的数，例如23456这个5位数，10000之前的数中包含的个数是确定的了，为f(1)+f(2)+f(3)+f(4),这是一个递归的过程，对此可以求出1-4位中包含1的总数，函数如下所示：

def get_1_digits(n): """ 获取每个位数之间1的总数 :param n: 位数 """ if n <= 0: return 0 if n == 1: return 1 current = 9 * get_1_digits(n-1) + 10 ** (n-1) return get_1_digits(n-1) + current

通过上面的分析，我们知道了23456中，1-10000之间一共出现了多少个1.下一步需要分析10000-23456中包含的1 我们首先把最高位单独拿出来分析一下，求出最高位上1的个数，如果最高位是1，则最高位上一共会出现的1的次数是低位上数字+1，例如12345，最高位上一共出现了2346个1；如果最高位大于1，则会一共出现的次数是10000-19999一共10**4个数。 然后，根据最高位的不同，计算出该高位前面的相同位数范围中的所有数中1的个数。例如对于34567，需要计算出10000-19999，20000-29999中一的个数，这时候计算一的个数，也就是计算0-9999中1的个数，这就可以转化成上面的f(n)来计算了，调用上面函数可以直接得到，然后用得到的值和最高位和1的差值（这里最高位是3）相乘就可以了。 分析完上面的部分后，我们现在只剩下最高位后面的部分了，我们发现剩下的部分还是一个整数，例如23456剩下了3456，这时候直接使用递归处理剩下的3456就行了。具体代码如下：

def allnums(n): if n == 0: return 0 if 0<n<10: return 1 digit = get_digits(n) high = int(str(n)[0]) low = n - high*10**(digit-1) low_nums = pre(digit - 1) #最高位之前的1的个数 if high == 1: high_nums = low + 1 all_nums = high_nums else: high_nums = 10**(digit-1) all_nums = high_nums + low_nums*(high - 1) return low_nums + all_nums + allnums(low)

对于上面使用的get_digits函数，是用来求给定的n是几位数的。代码如下：

def get_digits(n): a = 0 if n == 0: return 0 while n: n //= 10 #整除 a += 1 return a

放一起：

class Solution: def NumberOf1Between1AndN_Solution(self, n): # write code here # 法一 # ret = 0 # for i in range(n+1): # for s in str(i): # if s == '1': # ret += 1 # return ret # 法二 def get_digits(n): a = 0 if n == 0: return 0 while n: n //= 10 a += 1 return a def pre(n): if n == 0: return 0 if n == 1: return 1 nums = 10**(n-1) + pre(n-1)*9 return nums + pre(n-1) def allnums(n): if n == 0: return 0 if 0<n<10: return 1 digit = get_digits(n) high = int(str(n)[0]) low = n - high*10**(digit-1) low_nums = pre(digit - 1) #最高位之前的1的个数 if high == 1: high_nums = low + 1 all_nums = high_nums else: high_nums = 10**(digit-1) all_nums = high_nums + low_nums*(high - 1) return low_nums + all_nums + allnums(low) return allnums(n)

转自Python解决 从1到n整数中1出现的次数