[Python算法]输入一个整数n，求从1到n这n个整数中1出现的次数

问题描述：输入一个整数n，求从1到n这n个整数中1出现的次数。

解答的思路：

把整数的每一位分开讨论，每一位的值记为weight。

1. 个位

比如个位：给定常数345，从1增加到345过程中，个位数变化从0-9变化了34轮，记为round，。每一轮的变化中，个位出现1只变化一次，所以移动出现34轮。
再考虑weight的值，
如果weight是5，大于0，说明第35轮变化是从0-5,1又出现了一次。我们记录1出现的次数为count，所以：

count = round + 1 = 34 + 1 = 35

如果weight = 0,则35轮不会开始，只有34轮。

count = round * 34

2. 十位

对于十位，从0到9变化过程中，寻找变化的规律。

与个位不同的是：
不同点：从1到345变化过程中，每增加10，十位才增加1，十位的weight才会增加1，所以对于345，十位从0-9变化3轮，记为round,每一轮1会出现10次，即

round * 10。

再考虑weight的值，
此时，weight=4,大于1，说明，说明第4轮出现了10次1，则：

count = round * 10 + 10 = 3 * 10 + 10

如果，weight=0(比如305),那么第四轮到0就结束了，则

count = round * 10 + 10 = 3 * 10 + 10

如果，weight=1(比如315),这里第4轮1出现的次数和个位有关，这里个位是5，那么第4轮1出现的次数为5+1次，可以记录个位的数为Laster,则

count = round * 10 + laster + 1 = 3 * 10 + 5 + 1

百位和十位类似。

3. 规律：

对于个位：

1. 如果个位大于0,出现1的次数为round * 1 + 1。
2. 如果个位等于0,出现1的次数为round*1。

对于十位以及更高位，
针对十位，Weight扫描到十位，每一位的基数为Base，比Weight低的位数记为laster。

则：

1. 如果weight=0,则出现1的次数为round*Base。
2. 如果weight=1,则出现1的次数为round*Base+laster+1。
3. 如果weight>1,则出现1的次数为round*Base+Base。

• 345 = (个位出现1的次数)+(十位出现1的次数)+(百位出现1的次数) = (34*1+1)+(3*10+10)+(0*100+100)=175
• 340 = (34*1)+(3*10+10)+(0*100+100)=174
• 304 = (30*1+1)+(3*10)+(0*100+100)=161
• 315 = (31*1+1)+(3*10+5+1)+(0*100+100)=168

4. 实现代码

这里用到的测试用例有三种：
1.功能测试（输入10,345,340,305,315)
2.边界测试（输入-1,0,1）
3.性能测试（暂时选择一个大整数）

class Solution(object):
	def countOne(self, n):
		"""
		:type n: int
		:rtype: int 
		"""
		if n<1:
			return 0
		count = 0
		base = 1
		round = n
		while round > 0:
			weight = round % 10
			round = round // 10
			count = count + round * base 
			if (weight == 1):
				count = count + (n % base) + 1
			elif weight > 1:
				count = count + base
			base = base * 10		
		return count 
	
if __name__ == "__main__":
	so = Solution()
	
	#功能测试
	print("输出10出现1的次数", so.countOne(10))
	print("输出345出现1的次数", so.countOne(345))
	print("输出340出现1的次数", so.countOne(340))
	print("输出305出现1的次数", so.countOne(305))
	print("输出315出现1的次数", so.countOne(315))
	
	#边界测试
	print("输出0出现1的次数", so.countOne(0))
	print("输出1出现1的次数", so.countOne(1))
	print("输出-1出现1的次数", so.countOne(-1))
	
	#性能测试(这里选了较大的整数)
	print("输出315315315315315315315315315315315315315315315315315315出现1的次数", 
	so.countOne(315315315315315315315315315315315315315315315315315315))

5. 复杂度分析

while循环的次数为n的位数，logn(以10为底),循环体内执行的次数都是常数级，所以总体的时间复杂度为O(logn)。

6. 扩展

输入一个整数n，求从1到n这n个整数中k(0,1,2,3…9)出现的次数.

未完待续。。。