引用
首先多谢评论中的几位高手提供的另外几种算法思路!我发出这个博文也就是想表达这么一个意思:不要把算法思维都禁锢在那么几种逻辑方法内,事实上还有其他很多各种奇思妙想的更有趣的算法,就比如这个用数学特性来解题的算法。
如果各位只纠结于这个算法有没有BUG、有没有局限性、效率是否达到最佳,那么我只能说很遗憾,各位没有体会到我的目的。
我的目的只有一个:条条大路通罗马,不要禁锢自己的思想,我们的算法其实可以更有趣,享受编程吧!
假设这有一个各种字母组成的字符串,假设这还有另外一个字符串,而且这个字符串里的字母数相对少一些。从算法是讲,什么方法能最快的查出所有小字符串里的字母在大字符串里都有?
比如,如果是下面两个字符串:
String 1: ABCDEFGHLMNOPQRS
String 2: DCGSRQPOM
答案是true,所有在string2里的字母string1也都有。
如果是下面两个字符串:
String 1: ABCDEFGHLMNOPQRS
String 2: DCGSRQPOZ
答案是false,因为第二个字符串里的Z字母不在第一个字符串里。
这个算法题是我在外刊IT评论里看到的,本来题目没有什么出奇的地方,按照我的思路,也只能想到说用HashMap来查找,能实现最小的时间复杂度。
但是这篇文章里的某个面试官的算法,却让我眼前一亮,他用的是数学方法:
引用
他走到白板前,”如果这样呢 —— 假设我们有一个一定个数的字母组成字串 —— 我给每个字母分配一个素数,从2开始,往后类推。这样A将会是2,B将会是3,C将会是5,等等。现在我遍历第一个字串,把每个字母代表的素数相乘。你最终会得到一个很大的整数,对吧?然后 —— 轮询第二个字符串,用每个字母除它。如果除的结果有余数,这说明有不匹配的字母。如果整个过程中没有余数,你应该知道它是第一个字串恰好的子集了。这样不行吗?“
看到这个算法,我想大部分人都会产生“居然还能这么干”的想法吧!
我刚刚把这个算法用java简单实现了一下,当然只是提供思路,BUG是肯定有的,局限性也肯定是有的,不过用来看看算法的思考方向还是足够了:
package com.iteye.bolide74.tester;
public class Tester {
public static void main(String[] args) {
int[] prime = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47,
53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103 };
String strA = "ABCDEFGHIJKLMNO";
String strB = "AFGHIJX";
int strAlength = strA.length(), strBlength = strB.length();
long strA2primes = 1, strB2primes = 1;
for (int i = 0; i < strAlength; i++) {
strA2primes *= prime[(strA.charAt(i) - 'A')];
if (i < strBlength) {
strB2primes *= prime[(strB.charAt(i) - 'A')];
}
}
System.out.println(strA2primes % strB2primes == 0);
}
}
引用
(在这些陈年旧账里发现的一点技术瑕疵:字母有可能重复而字符串可能会很长,所以必须要有统计。用那个最幼稚的解决方案时,当在大字符串里找到一个字符后就把它删掉,当这样仍然是 O(n*m)次。在Hashtable里我们会有一个key->value的计数。Guy的方案在这种情况下仍然好用。)
引用自“一次谷歌面试趣事”:
http://www.aqee.net/2011/04/11/google-interviewing-story/
分享到:
相关推荐
经典谷歌,微软部分面试题的详细分析过程解答,另外还有一些锻炼思维能力的数学趣题。以上题目均节选源自《果壳网》,我已将上述试题转成PDF格式,便于下载和阅读。
程序员面试题精选 C++ 算法 微软 google 程序员面试题精选 C++ 算法 微软 google
google面试题google面试题
精选 数据结构 算法 微软 谷歌 IT经典 面试题 里面有丰富的编程题目,包含经典的数据结构、算法知识,还有微软谷歌的面试题,这些全是以往收集的,权当大放送。 ps:觉得好要来好评哦。
谷歌(Google)经典算法面试题,
真正的谷歌笔试面试题,让你领略互联网最伟大公司的风采,也为自己进入这些最著名的IT企业找准方向,明白哪些知识和技能是现代IT企业最渴求的!!
微软 腾讯 百度 谷歌 新浪 各种面试经典题集,经典再现
微软公司面试人员的面试题解答,google微软等大公司面试题,软件架构师的设计。
数据结构、算法、智力题,面试必考。包括百度、谷歌、腾讯、微软等IT巨头的题目。
C++基础面试题.docx C++开发工程师面试题库.docx C++技能测试试卷一及答案.docx C++技能测试试卷二及答案.docx c++笔试题汇总.pdf C++经典面试题库 附带参考答案.docx C++语言程序设计试题.docx C++面试题笔试题 CC+...
这是个人搜集的一线互联网大厂算法面试问题的Java实现,含谷歌、亚马逊、领英、雅虎、微软、Facebook、Airbnb等大厂,供各位研究学习Java算法,Java进阶!
Google21道面试题 Google公司的面试 google面试题2 GOOGLE面试题--答案
11谷歌面试题精讲
每年招聘的时候,做笔试难免会遇到一些经典的面试题,而好多是google已经出过的
算法面试专题课(Java版),Google面试官带你高质量刷题视频教程,2021最新,本套课程不讲算法基础知识,专攻算法题解。讲师作为诸多算法练习相关网站出题人,拥有多年出题及面试经验,将大厂主流经典的面试题全面归类...
google的面试题,很有挑战性...........
Google面试题
给大家分享一套课程——算法面试专题课(Java版),Google面试官带你高质量刷题视频教程,希望对大家面试有帮助。
常见算法笔试或面试题 笔试面试专栏:字符串 数组 vc题集 十道海量数据处理面试题与十个方法大总结 google全程面试题 其他一些公司的面试题
名牌有名牌的理由,就连招聘也与众不同,各个企业的面试题成了招聘后期的压轴好戏。今年的企业面试题目,说它百般刁难的有之,说它独出机杼的有之,说它故弄玄虚的有之。你怎么看呢?还是先来了解一下,看看面对这些...