2016/04/01• 重楼夕瑶欧阳 •17 评论 • 匹配 , 字符串 , 简洁 , 算法 , 轮询 , 面试
今天早上看到一个很有意思的面试题,题干是如何判断一个给定的小字符串,长度记为m,属于一个给定的大字符串,长度记为n,两个字符串都是纯小写字母。要求算法复杂度低,缺陷小。无论我想到排序,轮询,算法复杂度都在m*n附近。一个有意思的答案是,给26个字母赋值,值为2、3、5、7等素数。然后遍历大字符串,做积,得到一个大数,再遍历小字符串,用它去除大数,如果结果是整数,则是,否则不是。
666这方法好厉害
是吧,无论字符串长短,字母是否重复,都适用,而且算法复杂度只有m+n,远远小于m*n。突然发现自己的创新思维实在是少得可怜。技术的差距远远不是努力学习可以弥补的,更重要的是思考方式和角度以及探索创新的培养。
昨天看到一个李白喝酒的问题用的枚举,直接对整数进行位运算,我已经很惊讶了,今天这个更是吃惊,我感觉上学期都白学了。
你给科普一下呗
我网上搜的,现在没电脑,你可以百度搜索李白喝酒(10次花,5次店),具体方法就是把花和店看成两种状态,对应与二进制的0和1,然后枚举,所有的可能就是2的15次方,然后对这些数进行一位一位的判断,是1就当成遇店,0当成遇花。 ~~~~~~~~~~~~ 我自己是用递归做的,全部可能组成一棵二叉树,然后搜索判断,开一个15个元素的数组记录每一层二叉树,最后在叶子判断是否符合条件,符合就输出,当然,中间还加入了判断,把不可能的直接剪掉。你可是网络工程师呀,我就是个大一的。
总感觉你在逗我
我是很认真在回复啊,只不过不是时刻抱着手机而已
我只是想说你不应该不知道李白喝酒的枚举这种方法。
感觉很厉害的样子哦
这种思维很开放,值得我们学习
如果小字符串是’ab’, 大字符串是’bzzzza’,请你告诉我,小字符串是否在大字符串中?
可能我表述不清,题目本来的意思是,小字符串和大字符串都是字母集合,不是排序。谢谢你的一针见血
话说回来,我更想感叹的是这种思维,而不是这个题目本身
确实厉害,能从这种角度考虑问题…估计只有靠天才灵光一现了…
这不是那个说去谷歌碰到的问题吗?
嗯,是的
stringL.Contains(stringS)就好了嘛
登录 忘记密码 注册用户
一个月内自动登录
最新评论
666这方法好厉害
赞
是吧,无论字符串长短,字母是否重复,都适用,而且算法复杂度只有m+n,远远小于m*n。突然发现自己的创新思维实在是少得可怜。技术的差距远远不是努力学习可以弥补的,更重要的是思考方式和角度以及探索创新的培养。
赞
昨天看到一个李白喝酒的问题用的枚举,直接对整数进行位运算,我已经很惊讶了,今天这个更是吃惊,我感觉上学期都白学了。
赞
你给科普一下呗
赞
我网上搜的,现在没电脑,你可以百度搜索李白喝酒(10次花,5次店),具体方法就是把花和店看成两种状态,对应与二进制的0和1,然后枚举,所有的可能就是2的15次方,然后对这些数进行一位一位的判断,是1就当成遇店,0当成遇花。
~~~~~~~~~~~~
我自己是用递归做的,全部可能组成一棵二叉树,然后搜索判断,开一个15个元素的数组记录每一层二叉树,最后在叶子判断是否符合条件,符合就输出,当然,中间还加入了判断,把不可能的直接剪掉。你可是网络工程师呀,我就是个大一的。
赞
总感觉你在逗我
赞
我是很认真在回复啊,只不过不是时刻抱着手机而已
赞
我只是想说你不应该不知道李白喝酒的枚举这种方法。
赞
感觉很厉害的样子哦
赞
这种思维很开放,值得我们学习
赞
如果小字符串是’ab’, 大字符串是’bzzzza’,请你告诉我,小字符串是否在大字符串中?
2 赞
可能我表述不清,题目本来的意思是,小字符串和大字符串都是字母集合,不是排序。谢谢你的一针见血
赞
话说回来,我更想感叹的是这种思维,而不是这个题目本身
赞
确实厉害,能从这种角度考虑问题…估计只有靠天才灵光一现了…
赞
这不是那个说去谷歌碰到的问题吗?
赞
嗯,是的
赞
stringL.Contains(stringS)就好了嘛
赞