Python程序员面试分类真题12

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

设计一个程序，当输入一个字符串时，要求输出这个字符串的所有排列。例如输入字符串abc，要求输出由字符a、b、c所能排列出来的所有字符串：abc，acb，bac，bca，cba，cab。

（分数：16.50）__________________________________________________________________________________________

正确答案：(这道题主要考察对递归的理解，可以采用递归的方法来实现。当然也可以使用非递归的方法来实现，但是与递归法相比，非递归法难度增加了很多。下面分别介绍这两种方法。

方法一：递归法

下面以字符串abc为例介绍对字符串进行全排列的方法。具体步骤如下：

(1)首先固定第一个字符a，然后对后面的两个字符b与c进行全排列；

(2)交换第一个字符与其后面的字符，即交换a与b，然后固定第一个字符b，接着对后面的两个字符a与c进行全排列；

(3)由于第(2)步交换了a和b破坏了字符串原来的顺序，因此，需要再次交换a和b使其恢复到原来的顺序，然后交换第一个字符与第三个字符(交换a和c)，接着固定第一个字符c，对后面的两个字符a与b求全排列。

在对字符串求全排列的时候就可以采用递归的方式来求解，实现方法如下图所示：

在使用递归方法求解的时候，需要注意以下两个问题：(1)逐渐缩小问题的规模，并且可以用同样的方法来求解子问题；(2)递归一定要有结束条件，否则会导致程序陷入死循环。本题目递归方法实现代码如下：

#交换字符数组下标为i和j对应的字符

defswap(str,i,j):

tmp=str[i]

str[i]=str[j]

str[j]=tmp

"""

方法功能:对字符串中的字符进行全排列

输入参数:str为待排序的字符串,start为待排序的子字符串的首字符下标

"""

defPermutation(str,start):

ifstr==Noneorstart＜0:

return

#完成全排列后输出当前排列的字符串

ifstart==len(str)-1:

print".join(str),

else:

i=start

whilei＜len(str):

#交换start与i所在位置的字符

swap(str,start,i)

#固定第一个字符,对剩余的字符进行全排列

Permutation(str,start+1)

#还原start与i所在位置的字符

swap(str,start,i)

i+=1

defPermutation_transe(s):

str=list(s)

Permutation(str,0)

if__name__=="__main__":

s="abc"

Permutation_transe(s)

程序的运行结果为：

abcacbbacbcacbacab

算法性能分析：

假设这种方法需要的基本操作数为f(n)，那么f(n)=n*f(n-1)=n*(n-1)*f(n-2)…=n!。所以，算法的时间复杂度为O(n!)。算法在对字符进行交换的时候用到了常量个指针变量，因此，算法的空间复杂度为O(1)。

方法二：非递归法

递归法比较符合人的思维，因此，算法的思路以及算法实现都比较容易。下面介绍另外一种非递归的方法。算法的主要思想为：从当前字符串出发找出下一个排列(下一个排列为大于当前字符串的最小字符串)。

通过引入一个例子来介绍非递归算法的基本思想：假设要对字符串“12345”进行排序。第一个排列一定是“12345”，依此获取下一个排列："12345"-＞"12354"-＞"12435"-＞"12453"-＞"12534"＞"12543"-＞"13245"-＞…。从“12543”->“13245”可以看出找下一个排列的主要思路为：(1)从右到左找到两个相邻递增(从左向右看是递增的)的字符串，例如“12543”，从右到左找出第一个相邻递增的子串为“25”；记录这个小的字符的下标为pmin；(2)找出pmin后面的比它大的最小的字符进行交换，在本例中‘2’后面的子串中比它大的最小的字符为‘3’，因此，交换‘2’和‘3’得到字符串“13542”；(3)为了保证下一个排列为大于当前字符串的最小字符串，在第(2)步中完成交换后需要对pmin后的子串重新组合，使其值最小，只需对pmin后面的字符进行逆序即可(因为此时pmin后面的子字符串中的字符必定是按照降序排列，逆序后字符就按照升序排列了)，逆序后就能保证当前的组合是新的最小的字符串。在这个例子中，上一步得到的字符串为“13542”，pmin指向字符‘3’，对其后面的子串“542”逆序后得到字符串“13245”；(4)当找不到相邻递增的子串时，说明找到了所有的组合。

需要注意的是，这种方法适用于字符串中的字符是按照升序排列的情况。因此，非递归方法的主要思路为：(1)首先对字符串进行排序(按字符进行升序排列)；(2)依次获取当前字符串的下一个组合直到找不到相邻递增的子串为止。实现代码如下：

#交换字符数组下标为i和j对应的字符

defswap(str,i,j):

tmp=str[i]

str[i]=str[j]

str[j]=tmp

"""

方法功能:翻转字符串

输入参数:begin与end分别为字符串的第一个字符与最后一个字符的下标

"""

defReverse(str,begin,end):

i=begin

j=end

whilei＜j:

swap(str,i,j)

i+=1

j-=1

"""

方法功能:根据当前字符串的组合

输入参数:str:字符数组

返回值:还有下一个组合返回True,否则返回False

"""

defgetNextPermutation(str):

end=len(str)-1#字符串最后一个字符的下标

cur=end#用来从后向前遍历字符串

suc=0#cur的后继

tmp=0

whilecur!=0:

#从后向前开始遍历字符串

suc=cur

cur-=1

ifstr[cur]＜str[suc]:

#相邻递增的字符,cur指向较小的字符

#找出cur后面最小的字符tmp

tmp=end

whilestr[tmp]＜str[cur]:

tmp-=1

#交换cur与tmp

swap(str,cur,tmp)

#把cur后面的子字符串进行翻转

Reverse(str,suc,end)

returnTrue

returnFalse

"""

方法功能:获取字符串中字符的所有组合

输入参数:str:字符数组

"""

defPermutation(s):

ifs==Noneorlen(s)＜1:

print"参数不合法"

return

str=list(s)

str.sort()#升序排列字符数组

printstr

print".join(str),

whilegetNextPermutation(str):

print".join(str),

if__name__=="__main__":

s="abc"

Permutation(s)

程序的运行结果为：

abcacbbacbcacabcba

算法性能分析：

首先对字符串进行排序的时间复杂度为O(n2)，接着求字符串的全排列，由于长度为n的字符串全排列个数为n!，因此Permutation函数中的循环执行的次数为n!，循环内部调用函数getNextPermutation，getNextPermutation内部用到了双重循环，因此它的时间复杂度为O(n2)。所以求全排列算法的时间复杂度为O(n!*n2)。)解析：[考点]如何求一个字符串的所有排列2.

找出两个字符串的最长公共子串，例如字符串“abccade”与字符串“dgcadde”的最长公共子串为“cad”。

（分数：16.50）__________________________________________________________________________________________

正确答案：(对于这道题而言，最容易想到的方法就是采用蛮力法，假设字符串s1与s2的长度分别为len1和len2(假设len1＞=len2)，首先可以找出s2的所有可能的子串，然后判断这些子串是否也是s1的子串，通过这种方法可以非常容易地找出两个字符串的最长子串。当然，这种方法的效率是非常低下的，主要原因为：s2中的大部分字符需要与s1进行很多次的比较。那么是否有更好的方法来减少比较的次数呢?下面介绍两种通过减少比较次数从而降低时间复杂度的方法。

方法一：动态规划法

通过把中间的比较结果记录下来，从而可以避免字符的重复比较。主要思路如下：

首先定义二元函数f(，j)：表示分别以s1[i]，s2[j]结尾的公共子串的长度，显然，f(0，j)=0(j≥0)，f(i，0)=0(i≥0)，那么，对于f(i+1，j+1)而言，则有如下两种取值：

(1)f(i+1，j+1)=0，当str1[i+1]!=str2[j+1]时；

(2)f(i+1，j+1)=f(i，j)+1，当str1[i+1]==str2[j+1]时；

根据这个公式可以计算出f(i，j)(0≤i≤len(s1)，0≤j≤len(s2))所有的值，从而可以找出最长的子串，如下图所示。

通过上图所示的计算结果可以求出最长公共子串的长度max与最长子串结尾字符在字符数组中的位置maxI，由这两个值就可以唯一确定一个最长公共子串为“cad”。这个子串在数组中的起始下标为：maxI-max=3，子串长度为max=3。实现代码如下：

"""

方法功能:获取两个字符串的最长公共字串

输入参数:str1和str2为指向字符的指针

"""

defgetMaxSubStr(str1,str2):

len1=len(str1)

len2=len(str2)

sb="

maxs=0#maxs用来记录最长公共字串的长度

maxI=0#用来记录最长公共字串最后一个字符的位置

#申请新的空间来记录公共字串长度信息

M=[([None]*(len1+1))foriinrange(len2+1)]

i=0

whilei＜len1+1:

M[i][0]=0

i+=1

j=0

whilej＜len2+1:

M[0][j]=0

j+=1

#通过利用递归公式填写新建的二维数组(公共字串的长度信息)

i=1

whilei＜len1+1:

j=1

whilej＜len2+1:

iflist(str1)[i-1]==list(str2)[j-1]:

M[i][j]=M[i-1][j-1]+1

ifM[i][j]＞maxs:

maxs=M[i][j]

maxI=i

else:

M[i][j]=0

j+=1

i+=1

#找出公共字串

i=maxI-maxs

whilei＜maxI:

sb=sb+list(str1)[i]

i+=1

returnsb

if__name__=="__main__":

str1="abccade"

str2="dgcadde"

printgetMaxSubStr(str1,str2)

程序的运行结果为：

cad

算法性能分析：

由于这种方法使用了二重循环分别遍历两个字符数组，因此时间复杂度为O(m*n)(其中，m和n分别为两个字符串的长度)。此外，由于这种方法申请了一个m*n的二维数组，因此，算法的空间复杂度也为O(m*n)。很显然，这种方法的主要缺点为申请了m*n个额外的存储空间。

方法二：滑动比较法

如下图所示，这种方法的主要思路为：保持s1的位置不变，然后移动s2，接着比较它们重叠的字符串的公共子串(记录最大的公共子串的长度maxLen以及最长公共子串在s1中结束的位置maxLenEnd1)，在移动的过程中，如果当前重叠子串的长度大于maxLen，那么更新maxLen为当前重叠子串的长度。最后通过maxLen和maxLenEnd1就可以找出它们最长的公共子串。实现方法如下图所示：

如上图所示，这两个字符串的最长公共子串为“bc”，实现代码如下：

defgetMaxSubStr(s1,s2):

len1=len(s1)

len2=len(s2)

maxLen=0

tmpMaxLen=0

maxLenEnd1=0

sb="

i=0

whilei＜len1+len2:

s1begin=s2begin=0

tmpMaxLen=0

ifi＜len1:

slbegin=len1-i

else:

s2begin=i-len1

j=0

while(s1begin+j＜len1)and(s2begin+j＜len2):

iflist(s1)[s1begin+j]==list(s2)[s2begin+j]:

tmpMaxLen+=1

else:

if(tmpMaxLen＞maxLen):

maxLen=tmpMaxLen

maxLenEnd1=s1begin+j

else:

tmpMaxLen=0

j+=1

iftmpMaxLen＞maxLen:

maxLen=tmpMaxLen

maxLenEnd1=s1begin+j

i+=1

i=maxLenEnd1-maxLen

whilei＜maxLenEnd1:

sb=sb+list(s1)[i]

i+=1

returnsb

if__name__=="__main__":

str1="abccade"

str2="dgcadde"

printgetMaxSubStr(str1,str2)

算法性能分析：

这种方法用双重循环来实现，外层循环的次数为m+n(其中，m和n分别为两个字符串的长度)，内层循环最多执行n次，算法的时间复杂度为O((m+n)*n)。此外，这种方法只使用了几个临时变量，因此算法的空间复杂度为O(1)。)解析：[考点]如何求两个字符串的最长公共子串3.

实现字符串的反转，要求不使用任何系统方法，且时间复杂度最小。

（分数：16.50）__________________________________________________________________________________________

正确答案：(字符串的反转主要通过字符的交换来实现，需要首先把字符串转换为字符数组，然后定义两个索引分别指向数组的首尾，再交换两个索引位置的值，同时把两个索引的值向中间移动，直到两个索引相遇为止，则完成了字符串的反转。根据字符交换方法的不同，可以采用如下两种实现方法。

方法一：临时变量法

最常用的交换两个变量的方法为：定义一个中间变量来交换两个值，主要思路为：假如要交换a与b，通过定义一个中间变量temp来实现变量的交换：temp=a;a=b;b=a。实现代码如下：

defreverseStr(str):

ch=list(str)

lens=len(ch)

i=0

j=lens-1

whilei＜j:

tmp=ch[i]

ch[i]=ch[j]

ch[j]=tmp

i+=1

j-=1

return".join(ch)

if__name__=="__main__":

str="abcdefg"

print"字符串"+str+"翻转后为:",

printreverseStr(str)

程序的运行结果为：

字符串abcdefg翻转后为：gfedcba

算法性能分析：

这种方法只需要对字符数组变量遍历一次，因此时间复杂度为O(N)(N为字符串的长度)。

方法二：直接交换法

在交换两个变量的时候，另外一种常用的方法为异或的方法，这种方法主要基于如下的特性：a^a=0、a^0=a以及异或操作满足交换律与结合律。假设要交换两个变量a与b，则可以采用如下方法实现：

a=a^b:

b=a^b;//b=a^b=(a^b)^b=a^(b^b)=a^0=a

a=a^b;//a=a^b=(a^b)^a=(b^a)^a=b^(a^a)=b^0=b

实现代码如下：

defreverseStr(strs):

ch=list(strs)

lens=len(ch)

i=0

j=lens-1

whilei＜j:

#Python中不能直接对字符串进行异或操作,所以借助ord和chr函数。

ch[i]=chr(ord(ch[i])^ord(ch[j]))

ch[j]=chr(ord(ch[i])^ord(ch[j]))

ch[i]=chr(ord(ch[i])^ord(ch[j]))

i+=1

j-=1

return".join(ch)

算法性能分析：

这种方法只需要对字符数组遍历一次，因此时间复杂度为O(N)(N为字符串的长度)。与方法一相比，这种方法在实现字符交换的时候不需要额外的变量。)解析：[考点]如何对字符串进行反转4.

换位字符串是指组成字符串的字符相同，但位置不同。例如：由于字符串“aaaabbc”与字符串“abcbaaa”就是由相同的字符所组成的，因此它们是换位字符。

（分数：16.50）__________________________________________________________________________________________

正确答案：(在算法设计中，经常会采用空间换时间的方法以降低时间复杂度，即通过增加额外的存储空间来达到优化算法性能的目的。就本题而言，假设字符串中只使用ASCH字符，由于ASCII字符共有256个(对应的编码为0～255)，在实现的时候可以通过申请大小为256的数组来记录各个字符出现的个数，并将其初始化为0，然后遍历第一个字符串，将字符对应的ASCII码值作为数组下标，把对应数组的元素加1，然后遍历第二个字符串，把数组中对应的元素值减1。如果最后数组中各个元素的值都为0，那么说明这两个字符串是由相同的字符所组成的；否则，这两个字符串是由不同的字符所组成的。实现代码如下：

"""

方法功能:判断两个字符串是否为换位字符串

输入参数:s1与s2为两个字符串

返回值:如果是返回true,否则返回false

"""

defcompare(s1,s2):

result=True

bCount=[None]*256

i=0

whilei＜256:

bCount[i]=0

i+=1

i=0

whilei＜len(s1):

bCount[ord(list(s1)[i])-ord('0')]+=1

i+=1

i=0

whilei＜len(s2):

bCount[ord(list(s2)[i])-ord('O')]-=1

i+=1

i=0

whilei＜256:

ifbCount[i]!=0:

result=False

break;

i+=1

returnresult;

if__name__=="__main__":

str1="aaaabbc";

str2="abcbaaa";

printstr1+"和"+str2,

ifcompare(str1,str2):

print"是换位字符"

else:

print"不是换位字符"

程序的运行结果为：

aaaabbc和abcbaaa是换位字符

算法性能分析：

这种方法的时间复杂度为O(N)。)解析：[考点]如何判断两个字符串是否为换位字符串5.

给定由字母组成的字符串s1和s2，其中，s2中字母的个数少于s1，如何判断s1是否包含s2?即出现在s2中的字符在s1中都存在。例如s1=“abcdef"，s2=“acf”，那么s1就包含s2；如果s1=“abcdef”，s2=“acg”，那么s1就不包含s2，因为s2中有“g”，但是s1中没有“g”。

（分数：16.50）__________________________________________________________________________________________

正确答案：(方法一：直接法

最直接的方法就是对于s2中的每个字符，通过遍历字符串s1查看是否包含该字符。实现代码如下：

defisContain(str1,str2):

len1=len(str1)

len2=len(str2)

#字符串ch1比ch2短

iflen1＜len2:

i=0

whilei＜len1:

j=0

whilej＜len2:

iflist(str1)[i]==list(str2)[j]:

break

j+=1

if(j＞=len2):

returnFalse

i+=1

else:

#字符串ch1比ch2长

i=0

whilei＜len2:

j=0

whilej＜len1:

if(list(str1)[j]==list(str2)[i]):

break

j+=1

ifj＞=len1:

returnFalse

i+=1

returnTrue

if__name__=="__main__":

str1="abcdef'

str2="acf"

isContain=isContain(str1,str2)

priritstr1+"与"+str2,

if(isContain):

print"有包含关系"

else:

print"没有包含关系"

程序的运行结果为：

abcdef与acf有包含关系

算法性能分析：

这种方法的时间复杂度为O(m*n)，其中，m与n分别表示两个字符串的长度。

方法二：空间换时间法

首先，定义一个flag数组来记录较短的字符串中字符出现的情况，如果出现，那么标记为1，否则标记为0，同时记录flag数组中1的个数count；接着遍历较长的字符串，对于字符a，若原来flag[a]==1，则修改flag[a]=0，并将count减1；若flag[a]==0，则不做处理。最后判断count的值，如果count==0，那么说明这两个字符有包含关系。实现代码如下：

defisContain(s1,s2):

k=0#字母对应数组的下标

#用来记录52个字母的出现情况

flag=[None]*52

i=0

whilei＜52:

flag[i]=0

i+=1

count=0#记录段字符串中不同字符出现的个数

len1=len(s1)

len2=len(s2)

#shortStr,longStr分别用来记录较短和较长的字符串

#maxLen,minLen分别用来记录较长和较短字符的长度

iflen1＜len2:

shortStr=s1

minLen=len1

longStr=s2

maxLen=len2

else:

shortStr=s2

minLen=len2

longStr=s1

maxLen=len1

#遍历短字符串

i=0

whilei＜minLen:

#把字符转换成数组对应的下标(大写字母0～25,小写字母26～51)

iford(list(shortStr)[i])＞=ord('A')andord(list(shortStr)[i])＜=ord('Z'):

k=ord(list(short,Str)[i])-ord('A')

else:

k=ord(list(shortStr)[i])-ord('a')+26

ifflag[k]==0:

flag[k]=1

count+=1

i+=1

#遍历长字符串

j=0

whilej＜maxLen:

iford(list(longStr)[j])＞=ord('A')andord(list(longStr)[j])＜=ord('Z'):

k=ord(list(longStr)[j])-ord('A')

else:

k=ord(list(longStr)[j])-ord('a')+26

ifflag[k]==1:

flag[k]=0

count-=1

ifcount==0: