google面试题精讲ppt课件.ppt

Google面试题精讲1提纲关于面试一些例题例1被3和5整除的数的和例2合法单词例3和0交换的序列排序例4放到结尾的序列排序例5BFS及其推广例6单词对总结2关于面试各个公司有没有自己的题库题库里的题目来源员工网络笔试和面试笔试:没有交流面试展现思路给面试官好印象3例1被3和5整除的数的和例1给定一个数n,求不超过n的所有的能被3或者5整除的数的和。例如:n=9,答案3+6+5+9=23。分析:数学问题被3整除的数,3,6,9,…[n/3]*3被5整除的数,5,10,15,[n/5]*5重复的数同时是3和5的倍数15,30,…[n/15]*15注意点?n的范围4例1续等差数列求和公式x是首项,y是项数,d是公差(x+x+d*(y–1))*y/2,注意y=0也适用关键是项数!加x=3,d=3,y=n/3加x=5,d=5,y=n/5减x=15,d=15,y=n/155例2合法字符串例2字符串只有可能有A、B、C三个字母组成,如果任何紧邻的三个字母相同,就非法。求长度为n的合法字符串有多少个?比如:ABBBCA是非法,A是合法的。分析:动态规划的思路——真的要枚举么?dp[i][0]:长度为i的、最后两位不同的合法串的个数dp[i][1]:长度为i的、最后两位相同的合法串的个数递推:dp[i][0]=(dp[i-1][0]*2+dp[i-1][1]*2)dp[i][1]=dp[i-1][0]6例2续初值dp[1][0]=3,dp[1][1]=0结果dp[n][0]+dp[n][1]空间优化dp[i][0,1]只与dp[i-1][0,1]相关,可以省掉高维时间复杂度O(n)7例3和0交换的排序例3一个整数组里包含0-(n-1)的排列(0到(n-1)恰好只出现一次),如果每次只允许把任意数和0交换,求排好顺序至少交换多少次。(PAT1067)分析:组合数学里的圈。例如0占了1的位置,1占了2的位置,2占了0的位置。一个排列,总可以划分为若干个不相交的圈上例我们交换0和1,再交换0和2,则排好顺序了8例3续一个长度为m的圈,如果包含0,则交换(m-1)次可以恢复所有的数到原位如果一个长度为m的圈不包含0,则交换(m+1)次可以恢复所有的数到原位例如1在2的位置,2在3的位置,3在1的位置我们先交换0和任意一个数,例如交换0和1则变成1在0的位置,0在2的位置,2在3的位置,3在1的位置。9例3续2代码10