关于传说中的皮裤Guy的面试题

原文位于此处
http://bbs.jointforce.com/topic/19531

我似乎找到了一个O(m+n)的算法,同样简洁但是没有数字相乘造成太大数字的风险,无论多长的两个字符串,都只需要消耗一个8个字节的额外内存用于计算。

简单的说就是运用位运算,由于大小写字母总共有52个,所以可用一个长整型64位,每一位代表其中某一个字母。先遍历短字符串,对位掩码进行位设置操作,比如存在a则设置最低位为1。

然后遍历长字符串,对每个字母所代表的位进行清0,比如存在a则设置最低位为0。

遍历过后,如果64位长整型仍然非0,则证明短字符串不是长字符串的子集。

以上,叙述比较简单抽象…………实在是没精神多写啊………………

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • Spring Cloud为开发人员提供了快速构建分布式系统中一些常见模式的工具(例如配置管理,服务发现,断路器,智...
    卡卡罗2017阅读 134,981评论 19 139
  • 转自 www.jianshu.com/p/bd1bfc0c34b8 作为一个程序员,在找工作的过程中,都会遇到笔试...
    灬黑客灬阅读 4,431评论 1 118
  • 傻傻傻的分不清,鹿晗到底是男还是女 其实我有一种冲动,就是跑到鹿晗的面前,扒下他的裤衩,确认一下鹿晗是男还是女 尽...
    虾聊阅读 3,024评论 0 49
  • 倒影-休闲篇 东湖边 杨柳下 春水泛绿细浪花 几只黄鸭戏暖水 风吹杨柳摆 柳影湖中飘 逗得鱼虾成群转 乐得小鸭嘎嘎...
    winner永勤阅读 338评论 0 0
  • 在一个女孩的世界里,“努力”和“更努力”从来都是两条路,一条路让你勉强成为“基本款”,另一条才能让你有更大的几率成...
    living19阅读 200评论 0 0