面试基础常见问题之一,基本流程如下,1,2点是容易忽视的点

1)处理空白字符;

2)处理符号字符;

3)处理数值字符;

4)返回结果。

int atoi(const char* str)
{
    int result = 0;
    int sign = 0;
    assert(str != NULL);
    // proc whitespace characters
    while (*str==' ' || *str=='\t' || *str=='\n')
        ++str;
    // proc sign character
    if (*str=='-')
    {
        sign = 1;
        ++str;
    }
    else if (*str=='+')
    {
        ++str;
    }
    // proc numbers
    while (*str>='0' && *str<='9')
    {
        result = result*10 + *str - '0';
        ++str;
    }
    // return result
    if (sign)
        result *= -1;
    return result;
}

还真的有公司笔试考了这个填空,每次看到这个都记得不太准,kmp算法的难点就是求next数组,
遂回来仔细研究了下求next串的方法,kmp算法中主串不用回溯的的原因就是因为可以利用已知匹配来确认子串的滑动距离。

设s=” s1 s2 … sn ”, t=” t1 t2 … tm ”,在匹配过程中,当si≠ tj(1≤i≤n-m+1,1≤j≤m)时,存在(前面的j-1个字符已匹配):
si-j+1 … si-1 = t1 t2 … tj-1
若模式中存在可互相重叠的最长的真子串,满足:
t1 t2 … tk-1 =tj-k+1 tj-k+2 … tj-1

根据上式,求next串的过程,可以理解为模式串自身匹配自身,则有t1 t2 … tk-1 =tj-k+1 tj-k+2 … tj-1,而t(k) == t(j) , 则next[j+1] = next[j] + 1,否则就next[j+1] = next[k`] + 1 ,这个k`要一直0或者t(j) = t(next[k]) …

书上的代码都是字符串从下标1开始,next也从下标1开始。。。这些贴出从下标0开始的


void get_next(const char *s, int *next)
{
     int i=0,j=-1;
     next[0] = -1;
     while(s[i])
     {
          if( j == -1 || s[i] == s[j])
          {
              i++;
              j++;
              next[i] = j;
          }
          else
              j = next[j];
     }
 }

 int kmpfind(const char *t, const char *s,int *next)
 {
     int i = 0,j=0;
     int lena = strlen(t);
     int lenb = strlen(s);
     while(i < lena && j < lenb)
     {
                if(j == -1 || t[i] == s[j])
                {
                     i++;
                     j++;
                     if(s[j] == '\0')
                        return i - j;
                 }
                else
                    j = next[j];
     }
     return -1;
 }
, ,

转载的文章,作者是申音,《创业家》杂志的主编,在没有去T实习前,就看到过,通过在T的实习,感触更深。

————————————————————————————————————————————————

我有两个朋友。

L的公司在上海,大半时间跑广东。他是华南某所不太知名的大学毕业的,小眼睛质朴男,多年以前还是个文学青年。哥们做手机网游的,我见他使过好几款手机, 但最贵的一个也不过1千多块钱。比起什么Web2.0、移动互联网的概念,他更关心珠三角的几千万农民工和城市边缘的大学生“蚁族”,怎么关心?在东莞的 夜宵摊上跟他们拼啤酒,在富士康厂区外网吧里刷夜,跟靠做他们生意开上宝马的便利店老板扯淡……

W猫在北京中关村。他从小就是个脑袋很大眼睛发亮的天才少年,数理化成绩很好,逻辑思维超强,英文和中文一般流利。在首都某著名大学毕业后,W 直接去美国名校拿了硕士,接着回国创业。我一直觉得,他是硅谷Geek们的中国版。诸如iPad之类的新技术玩意,我总能第一时间从他那儿找到。他也是国内把玩Facebook、Twitter、Groupon、Foursqure的人。啥叫互联网的未来,W做的网站就代表互联网的未来。

W比L拥有更多的掌声和名声。但遗憾的是,他做了好几个连投资人都觉得很酷的网站,却始终没有挣到大钱。原因不外如下:要么是起个大早,却被一大堆抄近道的同行给围追堵截;要么因为资金接济不上,只能让一个更有资源实力的大公司直接吃掉,还有的不知道触了哪根高压线被主管部门直接暂停。

L的生意是实实在在每天都能数着钱的,他都已经可以打高尔夫了,但他并不想告诉无关人他挣到钱了。说了也没人信,几十万月薪不到2000的打工仔拿着 300块钱买的山寨机玩L公司做的游戏,每月给他贡献过百元的ARPU值,换句话说,他们收入的十来分之一都心甘情愿地送给L了。我有时也想不通,W针对的客户明明是北京、上海这些大城市中最有消费能力的精英。为什么他们舍得花钱买最贵的手机,换最新的笔记本电脑,下最好的馆子,在网上却什么都要免费。

圈里公认,只要是W做的事情必定引来围观。同行也好,媒体人、营销人也罢,口口相传,网站流量和用户量几乎是一条直线往上蹿。但奇怪的是,过了没多久就停止上升势头,开始跟中老年同志的心脏一样来回震荡。我也问过L,他的这些草根用户没几个有自己的电脑,更谈不上3G,究竟是怎么发掘的?L笑笑说,网吧都不是最有效的渠道。厂区周边有很多便利店,工人一下班就聚到哪儿。老板提供一台电脑,里面装了各种手机用的游戏、MP3、电影,再备一本类似早年K歌房里的“点歌簿”。不用上网,拿根USB数据线,想要什么下什么。还有更方便的,用手推车直接送到宿舍门口。

有次跟L吃饭,他提问我:如果一款游戏要打入45万富士康工人的市场,该请哪位代言人合适?我先猜周杰伦,摇头,丫目标受众是城市,又猜春哥也不对,她只杀伤学生和少妇,怒了,决定猜当红的凤娇,还是被鄙视!正确答案是凤凰传奇,有百度歌手榜单为证。备选是慕容晓晓。完全超出我知识范围,还好我没猜韩寒。

过去W单纯地以为凭技术就能改变社会,现在他知道你可以不过问政治,但政治会来过问你。不过,要让一个海归精英学会怎么跑门子疏通关系确实有点臊。L曾经愤青过,但如今很务实,好的商人都是知道怎么看《新闻联播》的。他挺关心运营商的人事变动和扫黄整顿,还搞过几次工友联谊会,虽然目的是为了推广他的游戏。前一段富士康工人“12连跳”,他很严肃地跟我说,这事他们有责任。我吓一跳。L讲,那些一想不开就跳楼的年轻人正是他的衣食父母。一部手机通常就是这些工人唯一的娱乐设备,与厂外世界交流的唯一媒介。他们有责任让工人们更快乐。

我所认识的投资人都对W评价很高,但却更爽快给L投钱。因为他们的心里也明镜似的:在中国,做精英的只能赚吆喝,做草根的才能赚着钱。腾讯、百度不就是最好的例子嘛。

上海那位梳分头打摩丝的笑星说过一句经典:我是喝咖啡的,北方那两位是吃大蒜的。咖啡是舶来品,感觉很洋气,吃大蒜却有益身心。今年炒大蒜的都挣了很多钱,没听说谁倒腾咖啡挣了钱。中国的互联网好像也是一样?

我曾经突发奇想,如果把W和L对调位置,情况会不一样吗?他们会更理解各自商业的长短吗?后来想想觉得这事不太可能。

W所追求的互联网,其实是一个“美式的互联网”。在美国,信息革命是从上个世纪60年代开始的,从1950后到1990后都是“数字化的一代”。他们之间并没有太大的“数字鸿沟”,他们的生意与生活,工作与娱乐都与互联网分不开。这也是为什么80后的扎克伯格能够和50后的乔布斯、60后的贝索斯、70后的佩奇同台竞技的原因。

同时,美国的社会结构是一颗“橄榄”,没有那么大的贫富差距、地区差异、城乡之别,所以,美国的互联网可以说是“全民的互联网”。

但当下中国的社会结构,原本我们以为它会是一座“金字塔”,但越来越变成一颗“图钉”。W和L一个站在削尖的头上,一个站在遥远的钉帽上。中国没有一个所谓 “全民的互联网”,中国的互联网是人为割裂的。它既存在于精英的Think笔记本上,也存在于草根的MTK山寨机中。我们的精英也许和美国同步,草根却与越南同步。

事实上,中国的“数字化一代”只存在于北上广等一些大城市,20-40岁之间的几千万中产阶级。剩下的几亿中国互联网用户归根结底都只是QQ用户。互联网改变不了这个现状,能改变它的也许需要更宏大的社会变革和经济变革?

我相信,L看穿了所谓“中国的互联网”的本质。哪些精英们的欲望从来不缺乏满足的渠道,太多的企业在追逐宠坏其实有限的一群客户。相反,有一大批“数字化贫民”却没有办法利用互联网改变自己的命运,没有条件通过网络让自己的生活质量飞升,只能沉醉于廉价的虚拟娱乐中。L的商业很符合本土国情,很和谐社会,但他能够走出国门吗?

我一直相信,终有一天,W能做点“代表先进互联网”的事情,让美国人也能跟着咱们屁股后面学。可现实的磨难会不会打消他的意志呢?

按照哲学家柏拉图的“洞穴”理论,每个人从出生开始就呆在自己挖的一个洞穴里,我们所见的世界只不过是被阳光抛到洞穴墙壁上的影像,而我们这些洞穴的居民却把它当作是真实的世界,因为我们没有见到过其他的东西。而真实的世界却是在洞穴之外,在有太阳的地方。

不管看这个BLOG的各位精英们是否承认,我们和某些人——一群数量比我们大得多的人(中国的农民工、刚毕业的大学生等等,大概3亿人),完全生活在两个不同的世界。如果能关注那一群人,还会有很多机会。但很有可能,我们永远都走不出自己呆的洞穴。

, ,

距离深圳回来已经半个多月了,才想起来应该要记录一下,自己理想的公司,第一次实习,实习的感悟,归结起来就几个关键词——微创新、用户体验、食物、互联网的商业模式。

1. 中国互联网
刚去公司没多久就碰上了“狗日的腾讯”事件,慢慢的理解了公司后,觉得应该更理性的看待此事,腾讯这样大鳄的对中国的互联网的存在确实有影响,如果自己以后做IT,也势必会碰到这种问题,必须把市场更加细分。其实看看百度、淘宝、网易、搜狐、新浪的产品目录,其实大家也都在做,所以即使没有腾讯,也会有百度之类的,腾讯最无语的应该是那个弹右下角的小窗。另外,从商业角度考虑,如何使公司利润的最大化才是公司的目标,这个也无可厚非,争论这个本没有意思,只是有时候的确不太厚道,可惜中国互联网的环境就这样。。。唉。。。

2. 用户体验
中国互联网的创新,其实。。。最近几年火的东西几乎是W先生从国外抄回来的,社交网络、微博、团购等,有关在中国互联网产业,创新的概念我觉得最好的解读就是周鸿伟的“微创新”。“用户体验”四个字,在公司是被奉为最重要的原则的,有点明白了为什么大家都做同一件东西,最后总是腾讯抢到果实。在腾讯,用户体验真的是被做到极致,举个简单的例子,在对一款产品进行用户体验测试时,会使用眼动仪来观测用户的视线是否会停留在一个细节上超过几秒,如果这个细节是被精心设计的并且没有达到期望的停留时间,则这个细节设计就是失败了。

3. 控制体重
同去的syn同学在实习两个月整整胖了两圈,每晚8点都要免费的自助夜宵,他总是各种肉。。。然后又拿各种面包和饮料。。唉,嘴馋的同学一定要注意控制。

从实习过程中学习到了很多在学校无法接触的东西,从商业的角度去接触互联网、体验产品,理解互联网的商业模式,马上就要签工作了,不管以后签不签腾讯,或者签公司的其他部门,甚至其他公司,都是很感谢腾讯给的这次的实习机会的。

,