Python程序员面试分类真题14

Python程序员面试分类真题14(总分：100.00，做题时间：90分钟)面试题(总题数：6，分数：100.00)1.

给定一个字符串数组，找出数组中最长的字符串，使其能由数组中其他的字符串组成。例如给定字符串数组[“test”，“tester”，“testertest”，“testing”，“apple”，“seattle”，“banana”，“batting”，“ngcat”，“batti”，“bat”，“testingtester”，“testbattingcat”]。满足题目要求的字符串为“testbattingcat”，因为这个字符串可以由数组中的字符串“test”，“batti”和“ngcat”组成。

（分数：16.50）__________________________________________________________________________________________

正确答案：(既然题目要求找最长的字符串，那么可以采用贪心法，首先对字符串由大到小进行排序，从最长的字符串开始查找，如果能由其他字符串组成，那么就是满足题目要求的字符串。接下来就需要考虑如何判断一个字符串能否由数组中其他的字符串组成，主要的思路为：找出字符串的所有可能的前缀，判断这个前缀是否在字符数组中，如果在，那么用相同的方法递归地判断除去前缀后的子串是否能由数组中其他的子串组成。

以题目中给的例子为例，首先对数组进行排序，排序后的结果为：[“testbattingcat”，“testingtester”，“testertest”，“testing”，“seattle”，“batting”，“tester”，“banana”，“apple”，“ngcat”，“batti”，“test”，“bat”]。首先取“testbattingcat”进行判断，具体步骤如下：

(1)分别取它的前缀“t”，“te”，“tes”都不在字符数组中，“test”在字符数组中。

(2)接着用相同的方法递归地判断剩余的子串“battingcat”，同理，“b”，“ba”都不在字符数组中，“bat”在字符数组中。

(3)然后判断“tingcat”，通过判断发现“tingcat”不能由字符数组中其他字符组成。因此，回到上一个递归调用的子串接着取字符串的前缀进行判断。

(4)回到上一个递归调用，待判断的字符串为“battingcat”，当前比较到的前缀为“bat”，接着取其他可能的前缀“batt”，“battt”都不在字符数组中，“battti”在字符数组中。接着判断剩余子串“ngcat”。

(5)通过比较发现“ngcat”在字符数组中。因此，能由其他字符组成的最长字符串为“testbattingcat”。

实现代码如下：

classLongestWord:

#方法功能:判断字符串strs是否在字符串数组中

deffind(self,strArray,strs):

i=0

whilei＜len(strArray):

ifstrs==strArray[i]:

returnTrue

i+=1

returnFalse

"""

方法功能:判断字符串word是否能由数组strrArray中的其他单词组成

参数:word为待判断的后缀子串,length待判断字符串的长度

"""

defisContain(self,strArray,word,length):

lens=len(word)

#递归的结束条件,当字符串长度为0时,说明字符串已经遍历完了

iflens==0:

returnTrue

#循环取字符串的所有前缀

i=1

whilei=lens:

#取到的子串为自己

ifi==length:

returnFalse

strs=word[0:i]

ifselffind(strArray,strs):

#查找完字符串的前缀后,递归判断后面的子串能否由其他单词组成

ifself.isContain(strArray,word[i:],length):

returnTrue

i+=1

returnFalse

#方法功能:找出能由数组中其他字符串组成的最长字符串

defgetLogestStr(self,strArray):

#对字符串由大到小排序

strArray=sorted(strArray,key=len,reverse=True)

printstrArray

#贪心地从最长的字符串开始判断

i=0

whilei＜len(strArray):

ifself.isContain(strArray,strArray[i],len(strArray[i])):

returnstrArray[i]

i+=1

#如果没找到,那么返回空串

returnNone

if__name__=="__main__":

strArray=["test',"tester","testertest","testing","apple","seattle","banana","batting","ngcat","batti","bat","testingtester","testbattingcat"]

lw=LongestWord()

logestStr=lw.getLogestStr(strArray)

iflogestStr!=None:

print"最长的字符串为:"+logestStr

else:

print"不存在这样的字符串"

程序的运行结果为：

最长的字符串为：testbattingcat

算法性能分析：

排序的时间复杂度为O(nlogn)，假设单词的长度为m，那么有m种前缀，判断一个单词是否在数组中的时间复杂度为O(mn)，由于总共有n个字符串，因此，判断所需的时间复杂度为O(m*n2)。因此，总的时间复杂度为O(nlogn+m*n2)。当n比较大的时候，时间复杂度为O(n2)。)解析：[考点]如何找到由其他单词组成的最长单词2.

用递归的方法实现一个求字符串中连续出现相同字符的最大值，例如字符串“aaabbcc”中连续出现字符‘a’的最大值为3，字符串“abbc”中连续出现字符‘b’的最大值为2。

（分数：16.50）__________________________________________________________________________________________

正确答案：(如果不要求采用递归的方法，那么算法的实现就非常简单，只需要在遍历字符串的时候定义两个额外的变量curMaxLen与maxLen，分别记录与当前遍历的字符重复的连续字符的个数和遍历到目前为止找到的最长的连续重复字符的个数。在遍历的时候，如果相邻的字符相等，那么执行curMaxLen+1；否则，更新最长连续重复字符的个数，即maxLen=max(curMaxLen，maxLen)，由于碰到了新的字符，因此curMaxLen=1。

题目要求用递归的方法来实现，通过对非递归方法进行分析可以知道，在遍历字符串的时候，curMaxLen与maxLen是最重要的两个变量，那么在进行递归调用的时候，通过传入两个额外的参数(curMaxLen与maxLen)就可以采用与非递归方法类似的方法来实现，实现代码如下：

defgetMaxDupChar(s,startIndex,curMaxLen,maxLen):

#字符串遍历结束,返回最长连续重复字符串的长度

ifstartIndex==len(s)-1:

returnmax(curMaxLen,maxLen)

#如果两个连续的字符相等,那么在递归调用的时候把当前最长串的长度加1

iflist(s)[startIndex]==list(s)[startIndex+1]:

returngetMaxDupChar(s,startIndex+1,curMaxLen+1,maxLen)

#两个连续的子串不相等,求出最长串max(curMaxLen,maxLen),

#当前连续重复字符串的长度变为1

else:

returngetMaxDupChar(s,startIndex+1,1,max(curMaxLen,maxLen))

if__name__=="__main__":

print"abbc的最长连续重复子串长度为:"+str(getMaxDupChar("abbc",0,1,1))

print"aaabbcc的最长连续重复子串长度为:"+str(getMaxDupChar("aaabbcc",0,1,1))

程序的运行结果为：

abbc的最长连续重复子串长度为：2

aaabbcc的最长连续重复子串长度为：3

算法性能分析：

由于这种方法对字符串进行了一次遍历，因此，算法的时间复杂度为O(N)。这种方法也没有申请额外的存储空间。)解析：[考点]如何统计字符串中连续的重复字符个数3.

假设L=＜a1,a2...,an＞是n个不同的实数的序列，L的递增子序列是这样一个子序列Lin=＜ak1,ak2,...,akm＞，其中，k1＜k2＜...＜km且ak1＜ak2＜...＜akm。求最大的m值。

（分数：16.50）__________________________________________________________________________________________

正确答案：(方法一：最长公共子串法

对序列L=＜a1,a2,...,an＞按递增进行排序得到序列LO=＜b1,b2,...,bn＞。显然，L与LO的最长公共子序列就是L的最长递增子序列。因此，可以使用求公共子序列的方法来求解。

方法二：动态规划法

由于以第i个元素为结尾的最长递增子序列只与以第i-1个元素为结尾的最长递增子序列有关，因此，本题可以采用动态规划的方法来解决。下面首先介绍动态规划方法中的核心内容递归表达式的求解。

以第i个元素为结尾的最长递增子序列的取值有两种可能：

(1)1，第i个元素单独作为一个子串(L[i]＜=L[i-1])；

(2)以第i-1个元素为结尾的最长递增子序列加1(L[i]＞L[i-1])。

由此可以得到如下的递归表达式：假设maxLen[i]表示以第i个元素为结尾的最长递增子序列，那么

(1)maxLen[i]=max[1,maxLen[j]+1],j＜iandL[j]＜L[i]

(2)maxLen[0]=1

根据这个递归表达式可以非常容易地写出实现的代码：

#函数功能:求字符串L的最长递增子串的长度

defgetMaxAscendingLen(strs):

lens=len(strs)

maxLen=[None]*lens

maxLen[0]=1

maxAscendingLen=1

i=1

whilei＜lens:

maxLen[i]=1#maxLen[i]的最小值为1;

j=0

whilej＜i:

iflist(strs)[j]＜list(strs)[i]andmaxLen[j]＞maxLen[i]-1:

maxLen[i]=maxLen[j]+1

maxAscendingLen=maxLen[i]

j+=1

i+=1

returnmaxAscendingLen

if__name__=="__main__":

s="xbcdza"

print"最长递增子序列的长度为:"+str(getMaxAscendingLen(s))

程序的运行结果为：

xbcdza最长递增予序列的长度为：4

算法性能分析：

由于这种方法用双重循环来实现，因此，这种方法的时间复杂度为O(N2)，此外由于这种方法还使用了N个额外的存储空间，因此，空间复杂度为O(N)。)解析：[考点]如何求最长递增子序列的长度4.

给定一个字符串，找出这个字符串中最长的重复子串，比如给定字符串“banana”，子字符串“ana”出现2次，因此最长的重复子串为“ana”。

（分数：16.50）__________________________________________________________________________________________

正确答案：(由于题目要求最长重复子串，显然可以先求出所有的子串，然后通过比较各子串是否相等从而求出最长公共子串，具体的思路为：首先找出长度为n-1的所有子串，判断是否有相等的子串，如果有相等的子串，那么就找到了最长的公共子串；否则找出长度为n-2的子串继续判断是否有相等的子串，依次类推直到找到相同的子串或遍历到长度为1的子串为止。这种方法的思路比较简单，但是算法复杂度较高。下面介绍一种效率更高的算法：后缀数组法。

后缀数组是一个字符串的所有后缀的排序数组。后缀是指从某个位置i开始到整个串末尾结束的一个子串。字符串r从第i个字符开始的后缀表示为Suffix(i)，也就是Suffix(i)=r[i...len(r)]。例如：字符串“banana”的所有后缀如下：

所以“banana”的后缀数组为：[5,3,1,0,4,2]。由此可以把找字符串的重复子串的问题转换为从后缀排序数组中通过对比相邻的两个子串的公共串的长度。在上例中3:ana与1:anana的最长公共子串为ana。这也就是这个字符串的最长公共子串。实现代码如下：

classCommonSubString:

#找出最长的公共子串的长度

defmaxPrefix(self,s1,s2):

i=0

whilei＜len(s1)andi＜len(s2):

iflist(s1)[i]==list(s2)[i]:

i+=1

else:

break

i+=1

returni

#获取最长的公共子串

defgetMaxCommonStr(self,txt):

n=len(txt)

#用来存储后缀数组

suffixes=[None]*n

longestSubStrLen=0

longestSubStr=None

#取到后缀数组

i=0

whilei＜n:

suffixes[i]=txt[i:]

i+=1

#对后缀数组排序

suffixes.sort()

i=1

whilei＜n:

tmp=self.maxPrefix(suffixes[i],suffixes[i-1])

iftmp＞longestSubStrLen:

longestSubStrLen=tmp

longestSubStr=suffixes[i][0:i+1]

i+=1

returnlongestSuloStr

if__name__=="__main__":

txt="banana"

c=CommonSubString()

print"最常的公共子串为:"+c.getMaxCommonStr(txt)

算法性能分析：

这种方法在生成后缀数组的复杂度为O(N)，排序的算法复杂度为O(NlogN*N)，最后比较相邻字符串的操作的时间复杂度为O(N)，所以算法的时间复杂度为O(NlogN*N)。此外，由于申请了长度为N的额外的存储空间，因此空间复杂度为O(N)。)解析：[考点]求一个串中出现的第一个最长重复子串5.

给定一个字符串，求串中字典序最大的子序列。字典序最大的子序列是这样构造的：给定字符串a0a1…an-1，首先在字符串a0a1…an-1中找到值最大的字符ai，然后在剩余的字符串ai+1…an-1中找到值最大的字符aj然后在剩余的aj+1…an-1中找到值最大的字符ak…直到字符串的长度为0，则aiajak…即为答案。

（分数：16.50）__________________________________________________________________________________________

正确答案：(方法一：顺序遍历法最直观的思路就是首先遍历一次字符串，找出最大的字符ai，接着从ai开始遍历再找出最大的字符，依此类推直到字符串长度为0。

以“acbdxmng”为例，首先对字符串遍历一遍找出最大的字符‘x’，接着从‘m’开始遍历找出最大的字符‘n’，然后从‘g’开始遍历找到最大的字符为‘g’，因此“acbdxmng”的最大子序列为“xng”。实现代码如下：

#方法功能:求串中字典序最大的子序列

defgetLargestSub(src):

ifsrc==None:

returnNone

lens=len(src)

largestSub=[None]*(lens+1)

k=0

i=0

whilei＜lens:

largestSub[k]=list(src)[i]

j=i+1

whilej＜lens:

#找出第i个字符后面最大的字符放到largestSub[k]中

iflist(src)[j]＞largestSub[k]:

largestSub[k]=list(src)[j]

i=j

j+=1

k+=1

i+=1

return".join(largestSub[0:k])

if__name__=="__main__":

s="acbdxmng"

result=getLargestSub(s)

ifresult==None:

print"字符串为空"

else:

printresult

程序的运行结果为：

xng

算法性能分析：

这种方法在最坏的情况下(字符串中的字符按降序排列)时间复杂度为O(n2)；在最好的情况下(字符串中的字符按升序排列)时间复杂度为O(n)。此外这种方法需要申请n+1个额外的存储空间，因此，空间复杂度为O(n)。

方法一：逆序遍历法

通过对上述运行结果进行分析，发现an-1一定在所求的子串中，接着逆序遍历字符串，大于或等于an-1的字符也一定在子串中，依次类推，一直往前遍历，只要遍历到的字符大于或等于子串首字符，就把这个字符加到子串首。由于这种方法首先找到的是子串的最后一个字符，最后找到的是子串的第一个字符，因此，在实现的时候首先按照找到字符的顺序把找到的字符保存到数组中，最后再对字符数组进行逆序，从而得到要求的字符。以”acbdxmng”为例，首先，字符串的最后一个字符‘g’一定在子串中，接着逆向遍历找到大于或等于‘g’的字符‘n’加入到子串中“gn”(子串的首字符为‘n’)，接着继续逆向遍历找到大于或等于‘n’的字符‘x’加入到子串中“gnx”，接着继续遍历，没有找到比‘x’大的字符。最后对子串“gnX”逆序得到“xng”。实现代码如下：

defgetLargestSub(src):

ifsrc==None:

returnNone

lens=len(src)

largestSub=[None]*(lens+1)

#最后一个字符一定在子串中

largestSub[0]=list(src)[lens-1]

i=lens-2

j=0

#逆序遍历字符串

whilei＞0:

iford(list(src)[i])＞=ord(largestSub[j]):

j+=1

largestSub[j]=list(src)[i]

i-=1

#largestSub[j+1]="

largestSub-largestSub[0:j+1]

#对子串进行逆序

i=0

whilei＜j:

tmp=largestSub[i]

largestSub[i]=largestSub[j]

largestSub[j]=tmp

i+=1

j-=1

return".join(largestSub)

if__name__=="__mam__":

s="acbdxmng"

result=getLargestSub(s)

ifresult==None:

print"字符串为空"

else:

printresult

算法性能分析：

这种方法只需要对字符串遍历一次，因此，时间复杂度为O(n)。此外，这种方法需要申请n+1个额外的存储空间，因此空间复杂度为O(n)。)解析：[考点]如何求解字符串中字典序最大的子序列6.

给定一个能判断一个单词是否为另一个单词的子字符串的方法，记为isSubstring。如何判断s2是否能通过旋转s1得到(只能使用一次isSubstring方法)。例如：“waterbottle”可以通过字符串“erbottlewat”旋转得到。

（分数：17.50）__________________________________________________________________________________________

正确答案：(如果题目没有对isString使用的限制，那么可以通过求出s2进行旋转的所有组合，然后与s1进行比较。但是这种方法的时间复杂度比较高。通过对字符串旋转进行仔细分析，发现对字符串s1进行旋转得到的字符串一定是s1s1的子串。因此可以通过判断s2是否是s1s1的子串来判断s2能否通过旋转s1得到。例如：s1=“waterbottle”，那么s1s1=“waterbottlewaterbottle”，显然s2是s1s1的子串，因此s2能通过旋转s1得到。实现代码如下：

#函数功能:判断str2是否为str1