[collect]读《编程之美》有感:1的个数-数字x的个数


原文地址:

http://blog.csdn.net/hinyunsin/article/details/6321406

题目是这样的:

给定一个十进制的正整数N,写下从1开始,到N的所有整数,然后数一下其中出现的所有”1″的个数

例如:

N=2,写下1,2。这样只出现了1个”1″。

N=12,我们会写下1,2,3,4,5,6,7,8,9,10,11,12。这样1的个数是5.

问题是:
    1. 写出一个函数f(N),返回1到N之间出现”1″的个数,比如f(12)=5
    2. 在32为整数范围内,满足条件”f(N)=N”的最大的N是多少?

书中的解法二是:通过分析”小于等于N的数在每一位上可能出现1的次数”之和来得到这个结果。下面是分析过程/方法

给定一个数字N,假定从低位(个位)到高位(十位,百位,千位。。。),他的第i位为B,i位的高位部分为A,i位的地位部分为C,因此,我们得到这样的计算公式:

N=A*10i+B*10i-1+C,我们用N=(A)B(C)来描述:例如i=3,那么12345=12*103+3*102+45,12345=(12)3(45)(A=12,B=3,C=45)

在i这个位置,B为1的数值有哪些:

1:假设B>1,从(0)1(*)~(A)1(*)(*表示C中每一位均可以是任意数字)范围内的数字都小于(A)B(C),总共有:(A+1)*10i

例如12345,其中(0)1(00)~(12)1(99)就是第3为为1的所有情况,大小时13*103

2:假设B=1,则从(0)1(*)~(A-1)1(*)范围内和(A)1(0~C)范围内的所有数字都<=(A)B(C),总共有:A*10i+(C+1)个

3:假设B=0,则从(0)1(*)~(A-1)1(*)范围内的所有数字都小于(A)B(C),总共有:A*10i 个

稍微思考一下,会发现,这个方式不只是对查找1的个数有用,对于1~9这9个数字的个数均有效,唯一不同的是,这里的B不再同1比较大小,而是跟要统计的数字比较大小

因此我们得到这样通用的解法:

给定一个十进制的正整数N,写下从1开始,到N的所有整数,然后数一下其中出现的所有”x”的个数,其中1<=x<=9。分析方法:

N=A*10i+B*10i-1+C,我们用N=(A)B(C)来描述:例如i=3,那么12345=12*103+3*102+45,12345=(12)3(45)(A=12,B=3,C=45)

在i这个位置,B为1的数值有哪些:

1:假设B>x,从(0)x(*)~(A)x(*)(*表示C中每一位均可以是任意数字)范围内的数字都小于(A)B(C),总共有:(A+1)*10i

例如12345,其中(0)1(00)~(12)1(99)就是第3为为1的所有情况,大小时13*103

2:假设B=x,则从(0)x(*)~(A-1)x(*)范围内和(A)x(0~C)范围内的所有数字都<=(A)B(C),总共有:A*10i+(C+1)个

3:假设B<x,i 个

对于整数零,稍微有点特殊:

    1. 假设B>0,如果A>0,也就是i不是N的最高位,则从(1)0(*)~(A)0(*)(而不是(0)x(*)~(A)x(*),因为这里x=0)范围内的数字都小于(A)B(C),总共是是A*10i个,如果A=0,这样的数字是不存在的
    2. 假设B=0,则A>0,从(1)0(*)~(A)0(*)范围内和(A)0(0~*)范围内的所有数字都<=(A)B(C),总共有:(A-1)*10i+(C+1)个
    3. 最后要+1,因为0没有被计算进去,对于任意正整数,0总是小于它的。
贴上python代码如下:
#!/usr/bin/python
#coding=utf-8
#Filename: numCount.py
'''
Create on 2011-04-12
@author: boyce
@contact: [email protected]
@version 1.0
'''
def sums(val, num):
    iCount = 0	#总数初值设为0
    iFactor = 1	#提前设置权值为1,即个位
    iLowerNum = 0
    iCurrNum = 0
    iHigherNum = 0

    if num == 0:
        while (val / iFactor) != 0:
            iLowerNum = val - (val / iFactor) * iFactor
            iCurrNum = (val / iFactor) % 10
            iHigherNum = val / (iFactor * 10)
            if iCurrNum == 0:
                iCount += (iHigherNum - 1) * iFactor + iLowerNum + 1
            elif iHigherNum > 0:
                iCount += iHigherNum * iFactor
            iFactor *= 10
        return iCount + 1

    while (val / iFactor) != 0:
        iLowerNum = val - (val / iFactor) * iFactor
        iCurrNum = (val / iFactor) % 10
        iHigherNum = val / (iFactor * 10)
        if iCurrNum < num:
            iCount += iHigherNum * iFactor
        elif iCurrNum == num:
            iCount += iHigherNum * iFactor + iLowerNum + 1
        else:
            iCount += (iHigherNum + 1) * iFactor
        iFactor *= 10
    return iCount

if __name__ == '__main__':
    num = 33333
    print '0: ', sums(num, 0)
    print '1: ', sums(num, 1)
    print '2: ', sums(num, 2)
    print '3: ', sums(num, 3)
    print '4: ', sums(num, 4)
    print '5: ', sums(num, 5)
    print '6: ', sums(num, 6)
    print '7: ', sums(num, 7)
    print '8: ', sums(num, 8)
    print '9: ', sums(num, 9)

后记:我自己后来也照着这个思路写了个PHP版的,但是和这个Python版的比起来太搓了,就没有放上来……


《“[collect]读《编程之美》有感:1的个数-数字x的个数”》 有 2 条评论

  1. 程序员面试题精选100题(47)-数组中出现次数超过一半的数字[算法]
    http://zhedahht.blog.163.com/blog/static/25411174201085114733349/

    找出数组中出现次数超过一半的数(时间复杂度O(n))
    http://blog.csdn.net/cyuyanenen/article/details/51749903

    面试题:如何找出数组里出现次数超过总数1/3的数
    http://xindoo.me/articles/1111
    `
    给你一个数组nums,如何找nums中出现次数超过总数的1/3的数,要求时间复杂度O(N)和空间复杂度O(1)。

    遍历nums,在遍历过程中如果凑够3个不一样的就丢掉这3个数。
    `

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注