加载中…
个人资料
阿里正祥
阿里正祥 新浪个人认证
  • 博客等级:
  • 博客积分:0
  • 博客访问:1,518
  • 关注人气:636
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
正文 字体大小:

题目:输入一个整数n,求从1到n这n个整数的十进制表示中1出现的次数的非递归解法

(2010-11-11 22:01:26)
标签:

算法

题目:输入一个整数n,求从1到n这n个整数的十进制表示中1出现的次数。
例如输入12,从1到12这些整数中包含1 的数字有1,10,11和12,1一共出现了5次。

据说这是一道google面试题,在何海涛的博客(http://zhedahht.blog.163.com/blog/static/25411174200732494452636/)中已有递归解法,思考了下,觉得也可以用以下的非递归解法:

把该正整数表示为十进制的字符串:an-1an-2…a0,其中an-1为最高位,a0为最低位(个位),按最高位、最低位、中间位来分别分析其中1出现的次数:

  • 最高位(an-1)出现数字1的次数:

如果an-1 == 1,则为1bn-2…b0,且 0 <= 整数(bn-2…b0) <= 整数(an-2…a0),累计 (an-2…a0)+1个;

否则,an-1 > 1,则为1xn-2…x0,其中(xn-2…x0)为任意(n-1)位整数,累计10n-1个;

  • 最低位(a0)出现数字1的次数:

如果a0 == 0,则为bn-1…b11,且 0 <= 整数(bn-1…b1) < 整数(an-1…a1),累计 (an-1…a1)个;

否则a0 >= 1,则为bn-1…b11,且 0 <= 整数(bn-2…b0) <= 整数(an-1…a1),累计 (an-1…a1)+1个;

  • 中间位(ai)ai出现数字1的次数,0 < i < (n-1)

如果ai == 0,则为bn-1…bi+11xi-1…x0,且 0 <= 整数(bn-1…bi+1) < 整数(an-1…ai+1)(xi-1…x0)为任意i位数,累计 (an-1…ai+1)*10i个;

如果ai == 1,则除了ai == 0的情形外,还有一种情形:an-1…ai+11ci-1…c0,且0 <= (ci-1…c0) <= ai-1…a0,有(ai-1…a0)+1个,累计:(an-1…ai+1)*10i+(ai-1…a0)+1(an-1…ai+1ai-1…a0)+1个

否则,ai > 1,则为bn-1…bi+11xi-1…x0,且 0 <= 整数(bn-1…bi+1) <= 整数(an-1…ai+1)(xi-1…x0)为任意i位数,累计 ((an-1…ai+1)+1)*10i个;

 

0

阅读 收藏 喜欢 打印举报/Report
  

新浪BLOG意见反馈留言板 欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 产品答疑

新浪公司 版权所有