[算法]Google的面试题

fluke

Post by slashseed
简单的组合数学问题，鉴定完毕

搭车问你们一个问题：
大家用过diff，也用过win下的comp吧，有没有人发现，对于同一个比较，diff返回的不同处总是不多于win的呢，比如对于如下两个文件A,B
A:     B:
1      4
2      1
3      2
        3
diff返回B文件第一行多一个4,而comp返回每行都不一样，
请问diff是用什么方法来比较的呢

diff是不是找匹配?而comp弱智到按行号对比？我没有用过比较的程序。

mikeandmore

Post by Iambitious
这种题目属于非常简单的acm题目，属于非常经典的计数题目。

这是一个很有名的问题的一个变种。。。

问题是这样发现的。。。
一个天文学家在偶然间发现对数表的代1的几页会很快变的很脏，所以他认为在所有的正整数中带数字1的概率要高一些。。。当时没有人认为这个东西对，知道后来，有一个美国数学家得到答案，令人吃惊。。。
答案是 肯定的。。。（好像是ln(2)不大确定，我忘了。。。）
至于怎么证明的，我想可能只是一个极限吧，但是可能和Taylor级数有关。。。

（我是要学软件工程的。。。。）

zozoh

我用ruby 写的:

def count_1x10(d)
       
        return 1 if d==0
        return 2 if d==1
        return 21 if d==2
        s = d.to_s
        (d-2).times {s<<'0'}
        s << '1'
        return s.to_i
end

def count_nx10(n,d)
        return 0 if n==0
        return 1 if d==0
        return 2 if d==1 && n==1
        return 10+n if d==1       
        return count_1x10(d) if n==1
       
        m = count_1x10(d)-1
        return 10**d + m*n
end

def count_number(n)
        raise "n can not less than 0!!! =>" + n.to_s if n<0
        return 0 if n==0
        return 1 if n<10
        s = n.to_s
        m = s.length-1
        re = 0
        s.each_byte do |c|
                re += count_nx10(c.chr.to_i,m)
                m -= 1
        end
        pos = s.index('1')
        while pos && pos!=(s.length-1)
                re += s.slice(pos+1,s.length).to_i
                pos = s.index('1',pos+1)
        end
        return re
end

puts count_number(ARGV[0].to_i)

Iambitious

diff应该用的编辑距离的算法，comp就比较弱了，直接按行比较的

wide288

这网址不错,题目好玩.想玩编程来这就对了.

checkit

Post by xiaoarly
牛，这种题目，没几个人能够做得出来

数学系专业的，做这种题目，还好一点，计算机系，不适合做这种题目。

其实不懂计算机的话，做的答案将是缺乏效率的。

osfans

1. f=0
   
2. i=1
   
3. num=0
   
4. maxint=1111111110
   
5. while i<maxint:
   
6.    ones=str(i).count('1')
   
7.    f+=ones
   
8.    if(f==i):
   
9.       num+=1
   
10.       print 'the %d number is %d'%(num,f)
    
11.    if(ones==0 and i%10>1):
    
12.       i+=10-i%10
    
13.    else:
    
14.       i+=1
    
15.       

复制代码

来一个python的

frank55555

怎么大家把這個題目做的這么復雜呀?我不會編程.但我想也不用這么算呀?這不是很累.你以為計算機這樣工作不累嗎?

frank55555

怎么大家把這個題目做的這么復雜呀?我不會編程.但我想也不用這么算呀?這不是很累.你以為計算機這樣工作不累嗎?我認為這個很好算嗎?比如說2345有我少個?答案是234*1+235*1+245*1+345*1=1059個.用口算就可以算出來呀?個位不等于0就去掉個位+1(等于0則減10再去掉個位+1).再加上十位不等于0去掉十位(十位等于0則減100再去掉十位+1).............總共加起來就可以了.

比如:5203----------(520+1)*1+(513+1)*1+(503+1)*1+(203+1)*1=1743
       1003---------(100+1)*1+(93+1)*1+(3+1)*1+(3+1)*1=203
       13-----------(1+1)*1+(3+1)*1=6

searching

和大家说说我的想法吧，想了几天想出来的，将数减去少位数的最大那个，即（13-9）、
（1003-999），（5203-999）然后把减得的数大于10、1000、1000取10、1000、1000，
这一步的目的是求出最高位上有1的数目
然后将最高位的数字 X 少一位的数字的函数取值，即
1xFun(9)、1xFun(999)、5xFun(999)，
这一步的目的是是求出10，1000，5000内除最高位外应有1的数目

将上两步所求数字向加后，最高位舍去，求剩于数的函数值，即Fun(3) Fun(003) Fun(203)，而步骤也与上面相同，直至到最后一位

整个过程需要循环所给出数的位数次，而Fun(9)、Fun(99)、Fun(999)、Fun(9999)、
Fun(99999)、Fun(9999999)……的值容易求得为1、20、300、4000、50000、600000……
用一个数组把它们保存，到时候直接取值即可。

比如：
Fun(13)=(13-9)>10?10: (13-9) +1*1 +1=6
Fun(1003)=(1003-999)>1000?1000: (1003-999) +1*300 +1=305
Fun(5203)=(5203-999)>1000?1000: (5203-999) +2*300 + (203-99)>100?100203) + 2*20
                     + 1=1000+600+100+40+1=1741

不知道对还是不对，暂时就是想到这里，也不知道我说清楚了没，让大家先看看