整数中1出现的次数

题目

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

 1 # -*- coding:utf-8 -*-
 2 class Solution:
 3     def NumberOf1Between1AndN_Solution(self, n):
 4         if n<0:
 5             return 0
 6         # 将n转换为字符串
 7         strn = str(n)
 8         return self.NumberOf1Between1(strn)
 9 
10     def NumberOf1Between1(self,strn):
11         # 注意，strn为空时
12         if len(strn)==0:
13             return 0
14         first = int(strn[0])
15         # 字符串长度只有一位
16         if len(strn)==1 and first==0:
17             return 0
18         if len(strn)==1 and first>0:
19             return 1
20         # 处理最高位
21         numFirstDigit=0
22         if first==1:
23             numFirstDigit = int(strn[1:])+1 # eg：12345， 最高位是1，10000到12345中最高位是1的总数为2346
24         if first>1:
25             numFirstDigit= self.PowerBase(len(strn)-1) # 例如：21345，最高位是2时，此时10000到21345，最高位是1的有10000个，10的4次方
26         #1在其他位
27         numOther = first*(len(strn)-1)*self.PowerBase(len(strn)-2) # 除去最高位，有一位为1，其他0-9，10种选择，排列组合
28         
29         numrec = self.NumberOf1Between1(strn[1:])
30         return numFirstDigit+numOther+numrec
31     def PowerBase(self,length):
32         return pow(10,length)