题目:输入一个整数n,求从1到n这n个整数的十进制表示中1出现的次数。 例如输入12,从1到12这些整数中包含1 的数字有1,10,11和12,1一共出现了5次。 据说这是一道google面试题,在何海涛的博客(http://zhedahht.blog.163.com/blog/static/25411174200732494452636/)中已有递归解法, 在阳振坤的博客中提出了一种非递归的算法(http://blog.sina.com.cn/s/blog_3fc85e260100mbss.html) 在这里,我给出这个算法的python实现:
$cat countone.py #!/usr/bin/python # # Find the number of 1 in the integers between 1 and N # Input: N - an integer # Output: the number of 1 in the integers between 1 and N # def CountOne(N): #make sure that N is an integer N = int(N) #convert N to chars a = str(N) #the lenth is string a n = len(a) i = 0 count = 0 while (i < n): if(i == 0): if(int(a[i]) == 1 ): count += int(a[1:])+1 elif(int(a[i]) > 1): count += 10 ** (n-1) elif(i == n - 1): if(int(a[i]) == 0): count += int(a[:n-1]) else: count += int(a[:n-1]) + 1 else: if(int(a[i]) == 0): count += int(a[:i]) * (10 ** (n - i - 1)) elif(int(a[j]) == 1): count += int(a[:i]) * (10 ** (n - i - 1)) + int(a[i+1:]) + 1 else: count += (int(a[:i]) + 1) * (10 ** (n - i -1)) i += 1 return count #Test code import sys if(__name__ == "__main__"): N = int(sys.argv[1]) n = CountOne(N) print "the number of '1' between 1 and %d is %d" % (N,n)