从1到1000的整数中1出现的次数，含有多少个“1”

来源：蜘蛛抓取(WebSpider) 时间：2017-06-19 22:44 标签： 从读入的整数数据中

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

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

从1到n依次遍历，对于每一个數字都检查一遍它有几个1然后累加即可，时间复杂度是O(N*logN)

例如103这样的数字：

所以对于每一位来说这一位数字是1的情况是由这一位本身、這一位的所有高位、这一位的所有低位，共同决定的总结一下，对于abXcd来说：

  • X=0时如果ab=01，那么就有这100个数字都是X位是1的数字

其实这道问题茬《编程之美》第134页有详解看不懂可以看看书。

我要回帖

更多关于 从读入的整数数据中 的文章

 

随机推荐