单词接龙问题

昨天看到其他部门的技能鉴定题目,相对我们部门偏应用的题目,他们的相对更加偏重算法。题目描述如下:

有一种单词接龙的游戏,就是连续的两个单词,第一个单词的尾要和第二个单词的头是一样的。
例如: cat tell log google就是一个单词接龙。

定义最少单词接龙是单词个数最少的接龙,定义最短单词接龙是单词字母个数总和最少的接龙。 假设所有单词都是由小写字母组成,现在给定一堆单词,给定龙头和龙尾,求出最少单词接龙和最短单词接龙。

当时在招聘,一时也没反应过来。下午回来的时候,仔细一想,这不就是最短路径问题么?

把26个小写字母看成是结点,那么每个单词就是从某个结点到另外一个结点的单向路径。
上面的接龙如果在加上单词gc, cookie,就是下面的图表示:
单词接龙

最少单词接龙,就是每条路径的权值为1,求两个结点之间的最短路径。
最短单词接龙,就是每条路径的权值为单词的长度,求两个结点之间的最短路径。

另外,关于一些特殊情况和注意点:

对于存在多个单词,他们的首尾字母相同的话,只记录长度最短的为路径的权值即可。

结点的存储可以不用链接表,因为只有26个字母,用二维数组即可,实时增加单词也容易处理。

求最短路径的算法,参考经典的Dijkstra最短路径算法,这里就不详述了。 关于Dijkstra,可以参考百度百科中的条目

有道云笔记使用感受

在笔记这个领域,网易的有道笔记的确是做得不错的。跟everynote相比,也不落下风, 相对来说,我使用有道笔记的频率要高许多,下面就简单说说我的使用体验。

pc版,ipad和Android版,我都有使用。在pc上我更倾向于网页收藏,但这个网页插件好像只有ie版,不是特别方便。 当然,我在电脑上工作的时候,还是用来记录一些材料,快速想法等。总体来说,我觉得网页插件还是不如everynote的方便。 不过,有道的空间要大不少,在保留网页的时候有很大优势。同时,智能提取正文也是很舒心的功能。

对于ipad,输入其实是没有优势的,我很多是采用涂鸦,录音,照片等方式进行录入,语音识别?尝试过,但感觉综合的速度并不快, 特别是出错的时候,容易打断思路,纠正成本很高。对于ipad来说,更多的时候是阅读,如果能从浏览器上直接保存到笔记上去就最好了, 就像稍后阅读功能。所以ipad的使用体验感觉是要差一些的。

手机Android版,大多数输入都是在这个版本上完成的,手机拼音的输入方式效率是不错的。在地铁上半小时,能完成好几百字的输入。 只是屏幕太小了,阅读,涂鸦并不方便,主要以文字输入为主,有时候也做一下录音。

对于我来说,每天在办公室的时间占据了大多数,不幸的是,公司不允许使用这一类工具。这大大的减少了我使用pc版的频率。 所以我使用的场景基本是在地铁上,主要是用来记录一些想法,思路,用一些要点记录下来,便于以后整理发布。 有需要的话,还可以通过邮件分享,不过pc上的邮件分享功能好像不能用。 总体来说,这个版本还是很好用的。

上面就是我的使用感受。在这个产品的帮助下,我完成了数十篇的草稿,记录了很多思路和计划,有兴趣的童鞋都来试试吧!

excel读书心得

上周因为要处理一些数据的统计分析,没有自己写脚本分析,而是采用了excel进行处理。 不过,我以前没用过excel的统计分析功能,于是找了本书来学习一下,现学现用。这本书的书名叫«你早该这么学excel»。

我想很多人学excel,都感觉需要好多技巧,外边大多数的书籍也是教技巧的。可惜这本书没介绍什么技巧,只是介绍了处理数据的一些原则。 反正,我感觉效果挺好的,根据这本书学习了一下,也能完成我想做的事情,并且显得有模有样,这就行了。

书里边介绍了作者伍昊的三大表理论。其中天下第一表,就是原始数据表,首要就是表格规范,数据格式化,无统计信息,表格列要齐全。 所有的统计都是根据原始数据表,并通过透视表来做的。当然,对于稳定的数据,他使用参数表的概念,采用自动生成方式。

这套原则很简单,并且有效。推荐大家看看,特别是经常接触excel的童鞋。

DES加解密总结

DES是广泛使用的分组对称加密算法,它要求待加密数据要8位对齐,所以在数据不足8位时候会出现padding的情况, 所以有可能因为padding不同,而出现加解密结果不一样,这种情况在异构系统间的数据通信特别容易出现,例如java和cpp系统之间的通信。 如果在开发过程中,遇到不同语言加解密结果不一样的情况,应该关注一下补齐方式。 关于补齐方式,请参考http://en.wikipedia.org/wiki/Padding_%28cryptography%29

先说说java这里,java api已经集成了DES加解密算法,如果不指定补齐方式的话,默认的补齐方式是使用PKCS5Padding, 这种情况下,长度不足8字节的部分,填充“0x01”—“0x08”,如不 足1字节,则填充1个“0x01”,如不足2字节,则填充2个“0x02”,以此类推。更具 体的描述,参考What Is PKCS5Padding? 如果我们指定补齐方式,如使用DES/ECB/NoPadding的话(其中ECB是加密的模式,也是默认的加密方式),就需要自己手动补齐,例如补空格字符。 现在的代码为了和后台的加解密结果一致,采用的是手动补齐的方式,即NoPadding方式。

如果cpp实现的padding方式和java的不一致,就可能导致加解密失败。在我们的系统里边,cpp实现的padding是补\0的。 这个字符在显示的时候就直接被当成结束符了,无需特殊处理。所以,如果使用java加密,cpp解密的话, java这边也要使用补\0的做法,如果使用java解密的话,就只能使用trim进行处理了。

以我们这边使用的两个DES相关的接口为例,用户鉴权接口在配置里边有使用trim进行处理,而wlan密码认证接口没有使用trim处理。 因此按现在使用补空格的方法,在用户鉴权接口是能成功的,但在wlan密码认证接口里边是会导致认证失败的。

如果需要更多关于加密补齐的资料,可以参考Using Padding in Encryption

那些年,我读过的技术书

这几天发烧很反复,反而有点时间用来整理一下思路。想了很多以前的事情,回忆的感觉是很复杂的。 突然想写写接触的技术书,现在工作的时间占据了大多数,看书的时间并不多, 但是每年看的书是有点越来越多的感觉,只是很少有特别深刻的,大概是因为平时的读书习惯就是不求甚解,又或者是这种方式很适合我。

C程序设计,谭浩强的教材估计是人手一册了。这也是我第一次接触编程语言,虽然我还是没学懂怎么写代码。 回头来看,这本书的确写得不怎样,比起那本c语言传世之作差太远了,里边错误也不少。

数据结构(用面向对象方法与C++语言描述),黄色皮的这本,应该是第一版。 说起这本书,我当年也是没学明白,主要是我太懒了,还有就是这语言真有点复杂。 这门课程每一两周就有一个课程设计,要编程的那种。我基本都是抄袭的,有一次我下决心想自己解决, 结果就是整了一通宵,双向链表编译都没通过。不过还好老师手下留情,最后还是62分勉强通过。 这门课程是到了毕业以后花3个月自学的,算是自己迄今为止看得最认真的一本书了,简直可以用改变我的职业生涯来形容。

计算机网络,第四版,这也是大学的教材,纯英文版本,这本书是认识网络的通用书籍,是本很好的书, 不过,并不是我从上面学到多少,我也是毕业以后才回去读的。我对这本书很有印象,主要是因为有一次我在图书馆, 看到我同学的书已经翻烂了,而我的书还是新的,要知道这是一本大几百页的英文书。顿时觉着这个世界很可怕, 别说自己不努力,即使你再努力,总有比你聪明的人比你还努力。难怪人家成绩如此的好。

Linux系统管理技术手册,这是我毕业以后买的一本大部头英文书。我对linux有个比较系统的认识也源于这本书。 不知有没有人在装系统的时候不小心把win也删除了没有?我就试过,后来在一次面试中被人当笑话了。 虽然工作的时候也有接触这linux,但那一年春节放假的时候,我觉得我应该认真学习一下,而且我们还是有十几天假期的。 于是到书店把这本书扛回去了,硬是在春节的时候看完。当然,只是看书很多是没概念的,于是我把家里的系统格了换成linux,公司也装上双系统,强迫自己适应。我对以前的公司环境还是心存感激的,很free的感觉。

设计模式,四人帮的大作,我买了有好几年了,一直来来去去的翻,始终没有通读,而我也读过不少模式方面的书, 但这本书一直保留在我的在读列表中,总感觉没读懂。直到最近这两年,有些开窍了,有时虽然不能想到利用哪种模式, 或者是哪种模式,但直觉告诉我,就应该这么写。我想,我逐渐从这些设计模式上找到设计原则的味道了。

其他书籍?没有第一时间在我脑子里边出现,即使我认同是一本好书,但也就仅仅是一本好书罢了。 相对来说,我很少看java的专题书,我跟偏爱通用类。而数据库,即使毕业后一两年, 我都是对数据库技术有点不屑的感觉,所以学得很少,直到最近这两年我才接触得多一些。

娱乐而已,勿当真。