计数问题

题目：输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。
例如输入12，从1到12这些整数中包含1 的数字有1，10，11和12，1一共出现了5次。
分析：这是一道广为流传的google面试题。用最直观的方法求解并不是很难，但遗憾的是效率不是很高；而要得出一个效率较高的算法，需要比较强的分析能力，并不是件很容易的事情。当然，google的面试题中简单的也没有几道。
一、直觉法
   首先我们来看最直观的方法，分别求得1到n中每个整数中1出现的次数，
    
    然后把它们加起来就行了。
   
    然而， google 的面试不是这么容易 让你过关的。
    因为这种方法的复杂度是 O( n ) ,对较大的整数，运算时间太长
二、 新方法
    我们通过分析数字的规律，找出加快计算速度的方法。
0 - 9 之间    所有数字中 出现的 1 为   1 个

0 –99       十位的1 有 10个
               去掉十位后， 有10组 0~9
               所以 共有   10 + 10 个
0 ~ 999   之间
             百位的1 有 100 = 10^2 个
             去掉百位后有 10组 : 0~99
             所以共有 10^2 + 10 * ( 10^1 + 10   )
0 ~ 9999    之间千位为1的共 1000= 103 个1
                去掉千位后 共有10组 0~999
       所以有： 10^3 + 10*( 10^2 + 10 * ( 10^1 + 10*1    ) ) 个1
计算 0 ~ 9999…9
        ┣──╁ 共 n 个 9   中1的个数F9( n) 的计算方案

F9( 0 ) = 0

F9( 1) = 1

F9( 2) = 10 + 10 * F9(1)

F9( 3) = 10^2 + 10 * F9(2)
F9( n ) = 10^n-1 + 10 * F9( n-1)
计算 1 ~ abcdefg 的方法

令 1 ~ abcdefg    之间 出现 1 的个数 记为 Q(    abcdefg )
设 m = len( “abcdefg”)

若   a=1 则有 F9( m-1 ) + (bcdefg+1) 个高位 1 + Q( bcdefg )
否则 a>1 ( a=0不考虑)

        则有           F9( m-1) + 10^( m-1) 个 高位1 +

                       (a-1)* ( F9(m-1) ) + Q( bcdefg )

         即： a * F9(m-1) + 10^( m-1 )个 高位1   +   Q( bcdefg )
注：
   F9( m-1) 是 从1 到 (m-1)个9 组成的数 之间的Q
   如 F9( 2 ) 相当于 Q（99）
  
   此处为了提方运算速度，我们把 F9 提前算出。


#coding=gbk
import time
def nowTime():
    return time.time()
# 题目：从1到n的正数中1出现的次数
# 这是一道广为流传的google面试题。
# 直觉算法
# 计算一个正数n中 1 出现的次数
def calcOnesFromOneNumber ( n ):
    s = str( n )
    m = 0
    for x in s:
        if x=="1":
            m = m+1
    return m
# 计算一个正数1 到 n 中 1 出现的次数
# 该算法复杂度 > O( n )
def QQ( n ):
    sm = 0
    for i in range(1,n+1):
        sm = sm + calcOnesFromOneNumber( i )
    return sm
# F10 依次为 10 的 0、1、2.。。次方的值
# F9 依次为    当n= 0, 9、99、999、9999....时 1~ n 的中出现 1 的次数
F10 = [ 1 ]
F9 = [ 0 ]
T = 1
for i in range( 1,30):
    F9.append( T + 10*F9[ i-1])
    T = T * 10
    F10.append( T )
# 新方法 计算    一个正数1 到 n 中 1 出现的次数

def Q( n ):
    if n<1:
        return 0
    if (1<=9):
        return 1
    s = str( n )
    m = len( s)
    n1 = int(s[1:])
    if s[0]=='1':
        return F9[ m-1 ] + (n1+1) + Q( n1 )
    else:
        return int(s[0]) *F9[ m-1 ] + F10[m-1] + Q( n1 )
n = 123456
print ("-----新方法计算 1 至 ", n,"之间 1 出现的次数")
a = nowTime()
print( Q(n) )
b=nowTime()
print( "用时:", b-a)
print ("-----直觉法计算 1 至 ", n,"之间 1 出现的次数")
print ( QQ( n ))
c=nowTime()
print( "用时:", c-b)
print ( "*******************************")
n = 21345
print ("-----新方法计算 1 至 ", n,"之间 1 出现的次数")
a = nowTime()
print( Q(n) )
b=nowTime()
print( "用时:", b-a)
print ("-----直觉法计算 1 至 ", n,"之间 1 出现的次数")
print ( QQ( n ))
c=nowTime()
print( "用时:", c-b)
运行结果
-----新方法计算 1 至 123456 之间 1 出现的次数
93553
用时: 0.010999917984
-----直觉法计算 1 至 123456 之间 1 出现的次数
93553
用时: 0.495000123978
*******************************
-----新方法计算 1 至 21345 之间 1 出现的次数
18821
用时: 0.0119998455048
-----直觉法计算 1 至 21345 之间 1 出现的次数
18821
用时: 0.174000024796

讨论：
  
   直觉法程序比较简单， 用时长一点，但可用作对新方法的验证。

评论

发表评论

此博客中的热门博文

AVR Tutorial - Input / Output

图片
Overview You cannot imagine to use microcontroller without using any of its i/o pins. Finally its all about : taking input , processing it and generating output ! Thus i/o registers and their correct settings is indispensable part while learning to program any uC. We will learn how to use AVR ports and actually ‘code’ for writing/reading data to/from port pins. It is slightly confusing for beginners, however once you understand it, you will certainly appreciate the way it is designed. NOTE : I will frequently refer to ‘configuring pin’ or simply ‘pin’. Remember, a port has multiple pins. Thus in order to change setting for one port, you have to change setting for all port pins of that port. To change setting for one single pin of the port, you have to change a particular bit in associated register. Got that ? If not read this para again. Registers AVR is 8 bit microcontroller. All its ports are 8 bit wide. Every port has 3 registers associated with it each one with 8 bits...
阅读全文

AVR ADC Analog to Digital Converter

图片
What is an ADC? An ADC, or Analog to Digital Converter, allows one to convert an analog voltage to a digital value that can be used by a microcontroller. There are many sources of analog signals that one might like to measure. There are analog sensors available that measure temperature, light intensity, distance, position, and force, just to name a few. Introduction The AVR ADC The AVR ADC allows the AVR microcontroller to convert analog voltages to digital values with few to no external parts. The author wrote this tutorial with the ATMega128 in mind, though other AVRs use similar hardware. The ADC built into the ATMega128 is capable of 10 bit resolution. The ATMega128 microcontroller has 8 ADC channels, allowing up to 8 analog sources to be attached to the microcontroller. The 8 ADC channels are connected to the internal DAC through a device called a multiplexer. The multiplexer connects the 8 ADC channels (the 8 pins of Port F on the ATMega128) to the internal ADC. One channel...
阅读全文

Introduction to REST

Building Web Services the REST Way Roger L. Costello I will first provide a brief introduction to REST and then describe how to build Web services in the REST style. What is REST? REST is a term coined by Roy Fielding in his Ph.D. dissertation [1] to describe an architecture style of networked systems. REST is an acronym standing for Representational State Transfer. Why is it called Representational State Transfer? The Web is comprised of resources. A resource is any item of interest. For example, the Boeing Aircraft Corp may define a 747 resource. Clients may access that resource with this URL: http://www.boeing.com/aircraft/747 A representation of the resource is returned (e.g., Boeing747.html). The representation places the client application in a state . The result of the client traversing a hyperlink in Boeing747.html is another resource is accessed....
阅读全文