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)
#include <stdio.h>

int countone(int num)
{
int cnt = 0;
while(num)
{
if(num%[……]

继续阅读

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

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

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

做法:

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

2、新指针到位后,和root一起next,知道新指针到了NULL。此时输出root指针当前的data即可。
int ll_last_k(struct Node* root, int k)
{
// Make two ptr diff k di[……]

继续阅读

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

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

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

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

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

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

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

继续阅读

两道面试题……

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

1、反转字符串单词。
输入I am coder4
输出coder4 am i
#include <iostream>
#include <vector>
#include <sstream>
using std::endl;
using std::cout;
using std::istringstream;
using std::vec[……]

继续阅读