C++博客 :: 首页 ::  :: 联系 ::  :: 管理

据说是Google面试题

Posted on 2006-09-08 13:05 chenger 阅读(1732) 评论(13)  编辑 收藏 引用 所属分类: Programming Stuff
从同学那儿听说了一个传说是Google面试题的题目:找出所有的正整数N,使得小于N的所有正整数的各位数字中所有的'1'的数目和N相等。

我的解法:

#include <iostream>
#include
<limits>
#include
<cstddef>

using
namespace std;

size_t calc_ones(size_t n)
{

    const
size_t save = n;
    size_t sum = 0,ten = 1,cnt = 1;
    if(n%10 > 1)
        sum =
1;
    n /=
10;
    for
(;n;n /= 10)
    {

        size_t
r = n%10;
        if
(r == 1)
            sum += save + (r*cnt -
10*n)*ten;
        else if(r != 0)
            sum += (
10 + r*cnt)*ten;
        ten *=
10;
        ++cnt;
    }
    return sum;
}

void solve()
{

    size_t
max = numeric_limits<size_t>::max();
    for
(size_t i = 1;i < max;++i)
        if
(calc_ones(i) == i)
            cout << i <<
"\n";
}


int
main()
{
    solve();

    return
0;
}


在VS2005下编译运行,输出结果为:

199992 199993 199994 199995 199996 199997 199998 199999 200000 1599992 1599993 1599994 1599995 1599996 1599997 1599998 1599999 1600000 1600001 2600000 13200000 13200001 35000000 35199992 35199993 35199994 35199995 35199996 35199997 35199998 35199999 35200000 117463827 500000000 500199992 500199993 500199994 500199995 500199996 500199997 500199998 500199999 500200000 501599992 501599993 501599994 501599995 501599996 501599997 501599998 501599999 501600000 501600001 502600000 513200000 513200001 535000000 535199992 535199993 535199994 535199995 535199996 535199997 535199998 535199999 535200000

可以证明,再往上就没有了。跑得比较慢,需要好几分钟。我考虑过进一步缩小检索的范围,应该是可以做到的,不过没有实现。

Update:上面的算法有很大的改进余地,主要来自张沈鹏同学给出的程序,我专门写了一篇文章来讨论,这里。或者可以直接看张沈鹏同学的文章

Feedback

# re: 据说是Google面试题  回复  更多评论   

2006-09-09 02:06 by erac
我的算法,不过和楼主第一个数字不一致,我是199991
int CountJustOneCnt(int i)
{
int j = i;
int iCount = 0;
while (j)
{
int remains = j % 10;
if (1 == remains)
{
iCount++;
}
j /= 10;
}

return iCount;
}

int main(int argc,char** argv)
{
int i = 1;
int iPreOneCount = -1;
while (i)
{
int iNowOneCount = iPreOneCount + CountJustOneCnt(i);
if (iNowOneCount == i)
{
cout<<"满足条件的数字是:"<<i<<endl;
getchar();
}
else
cout<<"不满足条件的数字是:"<<i<<endl;
i++;
iPreOneCount = iNowOneCount;
}
return 0;
}

# re: 据说是Google面试题  回复  更多评论   

2006-09-09 08:35 by chenger
我觉得你的算法有一点问题。在main函数的while循环里面,iNowOneCount应该是小于i的所有数的各位数字上1的个数吧?你的算法是把i本身也算在内的,跟我的定义不一样。当然这没什么,问题是iPreCount = -1。比如i=11的时候,结果应该是4(包括11在内),而这时候iNowCount = 3,显然不对。我的建议是把iPreCount 干脆设为0,对大于1的数,都能算出正确的结果。1就特殊对待了吧。

erac的算法好像是直接计算每一个数的各位1的个数然后加起来。我原来以为这样算比较慢,所以找了一个直接计算的公式,实际跑了一下,感觉差不太多。

# re: 据说是Google面试题  回复  更多评论   

2006-09-09 09:22 by erac
写错了哈。
看题目看错了。
现在对了:
int CountJustOneCnt(int i)
{
int j = i;
int iCount = 0;
while (j)
{
int remains = j % 10;
if (1 == remains)
{
iCount++;
}
j /= 10;
}

return iCount;
}

int main(int argc,char** argv)
{
int i = 1;
int iPreOneCount = 0;
while (i)
{
int iNowOneCount = iPreOneCount + CountJustOneCnt(i-1);
if (iNowOneCount == i)
{
cout<<"满足条件的数字是:"<<i<<endl;
getchar();
}
else
cout<<"不满足条件的数字是:"<<i<<endl;
i++;
iPreOneCount = iNowOneCount;
}
return 0;
}

# re: 据说是Google面试题  回复  更多评论   

2006-09-09 10:21 by Optimistic
面试题是要求如何写?实战还是手写?

# re: 据说是Google面试题  回复  更多评论   

2006-09-09 10:28 by chenger
@Optimistic
不清楚。面试的话可能是手写吧。

# re: 据说是Google面试题  回复  更多评论   

2006-09-14 22:32 by 张沈鹏
把这些数直接放入一个vector再find可以在1sec内完成:)
199992 199993 199994 199995 199996 199997 199998 199999 200000 1599992 1599993 1599994 1599995 1599996 1599997 1599998 1599999 1600000 1600001 2600000 13200000 13200001 35000000 35199992 35199993 35199994 35199995 35199996 35199997 35199998 35199999 35200000 117463827 500000000 500199992 500199993 500199994 500199995 500199996 500199997 500199998 500199999 500200000 501599992 501599993 501599994 501599995 501599996 501599997 501599998 501599999 501600000 501600001 502600000 513200000 513200001 535000000 535199992 535199993 535199994 535199995 535199996 535199997 535199998 535199999 535200000

# re: 据说是Google面试题  回复  更多评论   

2006-09-14 23:00 by chenger
@张沈鹏
能说详细一点吗?具体是用什么方法?

# re: 据说是Google面试题  回复  更多评论   

2006-09-16 10:58 by 张沈鹏
http://www.cppblog.com/zuroc/archive/2006/09/16/12540.html
有 run()

fastrun()

# re: 据说是Google面试题  回复  更多评论   

2006-09-16 15:37 by chenger
@张沈鹏
看了你的算法,写得比我的好。主要是little函数,我没有考虑到。

# re: 据说是Google面试题  回复  更多评论   

2006-09-17 15:51 by 绝缘电阻测试仪
楼主说的确实对我很有用,多谢了!@_@~~

# re: 据说是Google面试题  回复  更多评论   

2006-12-12 17:22 by heying0
楼主的代码着色是怎么处理的呢?是用的什么代码着色器呢?

# re: 据说是Google面试题  回复  更多评论   

2006-12-12 17:50 by chenger
@heying0
是用Vim格式化成html,然后再贴上来

# re: 据说是Google面试题  回复  更多评论   

2008-02-24 21:55 by raof01
楼主——麻烦你给出解题思路好不好?光看代码太费劲了,而且我不喜欢看代码。

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理