Tag Archives: 面试

求从1到n中1出现的次数

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

例如输入12,从1到12这些整数中包含1 的数字有1,10,11和12,1一共出现了5次。

编程之美上的原题

基本思路1:

每次判断各位是否为1,计数。然后依次/=10即可。

时间复杂度O(N*lgN)

思路2:

可以用归纳法搞出一个递推公式。

但是如书上所述,这个递推公式是有范围限制的,n最大为11111111[……]

继续阅读

求单向链表倒数第 k 个结点

题目:输入一个单向链表,输出该链表中倒数第 k 个结点。

传统做法是获取到链表的长度n,然后走n-k布,此方法弱爆了……

做法:

1、指定一个新的指针,走k步。如果k布之内就到了NULL,显然无倒数第k这说法,返回错误即可。

2、新指针到位后,和root一起next,知道新指针到了NULL。此时输出root指针当前的data即可。

 

大量数据取k个最大值并排序

需求是这样的,我们都知道,在信息检索中,经常要取top-k(一共k,而不是第k)个得分最大的文档,并且从大到小排序。

而且文档规模很大,最少也要上千万。

话说这是一道很可以拿来面试的题啊。

我们不考虑Hadoop神马的,就说说单机怎么搞。

最傻的做法就是把1000万个都存储下来,然后sort,然后取min(k, vec.size())。

这样有两个缺点:
1、内存占用非常大,其实我们只要保留最大的1000个,但这样就要保存N个。在1000万的测试中,它要占用68M[……]

继续阅读

两道面试题……

传说百度面试题,都是字符串处理的……我目前这水平也就做这种水题了,下午莫名其妙被面试,坐等被虐了。

1、反转字符串单词。
输入I am coder4
输出coder4 am i

2、将string形式的浮点数转化成double/float,只允许一次遍历。
输入:123.456(string)
输出:123.456(double/float)