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)就好了嘛
赞