Python程序员面试分类模拟8

Python程序员面试分类模拟8简答题1.

假设L=＜a1,a2...,an＞是n个不同的实数的序列，L的递增子序列是这样一个子序列Lin=＜ak1,ak2,...,akm＞，其中，k1＜k2＜...＜k（江南博哥）m且ak1＜ak2＜...＜akm。求最大的m值。正确答案：方法一：最长公共子串法

对序列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)。[考点]如何求最长递增子序列的长度

2.

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

最直接的方法就是对于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:

returnTrue

j+=1

returnFalse

if__name__=="__main__":

str1="abcdef"

str2="acf"

isContain=isContain(str1,str2)

priitstr1+"与"+str2,

ifisContain:

print"有包含关系"

else:

print"没有包含关系"

算法性能分析：

这种方法只需要对两个数组分别遍历一遍，因此，时间复杂度为O(m+n)(其中m、n分别为两个字符串的长度)，与方法一比，本方法的效率有了明显的提升，但是其缺点是申请了52个额外的存储空间。[考点]如何判断两个字符串的包含关系

3.

给定一个有序链表，其中每个结点也表示一个有序链表，结点包含两个类型的指针：

(1)指向主链表中下一个结点的指针(在下面的代码中称为“正确”指针)

(2)指向此结点头的链表(在下面的代码中称之为“down”指针)。

所有链表都被排序。请参见以下示例：

实现一个函数flatten()，该函数用来将链表扁平化成单个链表，扁平化的链表也应该被排序。例如，对于上述输入链表，输出链表应为3-＞6-＞8-＞11-＞15-＞21-＞22-＞30-＞31-＞39-＞40-＞45-＞50。正确答案：本题的主要思路为使用归并排序中的合并操作，使用归并的方法把这些链表来逐个归并。具体而言，可以使用递归的方法，递归地合并已经扁平化的链表与当前的链表。在实现的过程可以使用down指针来存储扁平化处理后的链表。实现代码如下：

classNode:

def__init__(self,data):

self.data=data

#self.next=None

self.right=None

self.down=None

#self.head=None

classMergeList:

def__init__(self):

self.head=None

#用来合并两个有序的链表*

defmerge(self,a,b):

#如果有其中一个链表为空,直接返回另外一个链表

ifa==None:

returnb

ifb==None:

returna

#把两个链表头中较小的结点赋值给result

ifa.data＜b.data:

result=a

result.down=self.merge(a.down,b)

else:

result=b

result.down=self.merge(a,b.down)

returnresult

#把链表扁平化处理

defflatten(self,root):

ifroot==Noneorroot.right==None:

returnroot

#递归处理root.right链表

root.right=self.flatten(root.right)

#把root结点对应的链表与右边的链表合并

root=self.merge(root,root.right)

returnroot

#把data插入到链表头

definsert(self,head_ref,data):

new_node=Node(data)

new_node.down=head_ref

head_ref=new_node

#返回新的表头结点

returnhead_ref

defprintList(self):

temp=self.head

whiletemp!=None:

printtemp.data,

temp=temp.down

print'\n'

if__name__=="__main__":

L=MergeList()

#构造链表

L.head=L.insert(L.head,31)

L.head=L.insert(L.head,8)

L.head=L.insert(L.head,6)

L.head=L.insert(L.head,3)

L.head.right=L.insert(L.head.right,21)

L.head.right=L.insert(L.head.right,11)

L.head.right.right=L.insert(L.head.right.right,50)

L.head.right.right=L.insert(L.head.right.right,22)

L.head.right.right=L.insert(L.head.right.right,15)

L.head.right.right.right=L.insert(L.head.right.right.right,55)

L.head.right.right.right=L.insert(L.head.right.right.right,40)

L.head.right.right.right=L.insert(L.head.right.right.right,39)

L.head.right.right.right=L.insert(L.head.right.right.right,30)

#扇平化链表

L.head=L.flatten(L.head)

L.printList()

程序的运行结果为：

36811152122303139405055[考点]如何展开链接列表

4.

二叉树的镜像就是二叉树对称的二叉树，就是交换每一个非叶子结点的左子树指针和右子树指针，如下图所示，请写出能实现该功能的代码。注意：请勿对该树做任何假设，它不一定是平衡树，也不一定有序。

正确答案：从上图可以看出，要实现二叉树的镜像反转，只需交换二叉树中所有结点的左右孩子即可。由于对所有的结点都做了同样的操作，因此，可以用递归的方法来实现，由于需要调用printTreeLayer层序打印二叉树，这种方法中使用了队列来实现，实现代码如下：

fromcollectionsimportdeque

classBiTNode:

def__init__(self):

self.data=None

self.lchild=None

self.rchild=None

#对二叉树进行镜像反转

defreverseTree(root):

ifroot==None:

return

reverseTree(root.lchild)

reverseTree(root.rchild)

tmp=root.lchild

root.lchild=root.rchild

root.rchild=tmp

defarraytotree(arr,start,end):

root=None

ifend＞=start:

root=BiTNode()

mid=(start+end+1)/2

#树的根结点为数组中间的元素

root.data=arr[mid]

#递归的用左半部分数组构造root的左子树

root.lchild=arraytotree(arr,start,mid-1)

#递归的用右半部分数组构造root的右子树

root.rchild=arraytotree(arr,mid+1,end)

else:

root=None

returnroot

defprintTreeLayer(root):

ifroot==None:

return

queue=deque()

#树根结点进队列

queue.append(root)

whilelen(queue)＞0:

p=queue.popleft()

#访问当前结点

printp.data,

#如果这个结点的左孩子不为空则入队列

ifp.lchild!=None:

queue.append(p.lchild)

#如果这个结点的右孩子不为空则入队列

ifp.rchild!=None:

queue.append(p.rchild)

if__name__=="__main__":

arr=[1,2,3,4,5,6,7]

root=arraytotree(arr,0,len(arr)-1)

print"二叉树层序遍历结果为:",

printTreeLayer(root)

print'\n'

reverseTree(root)

print"反转后的二叉树层序遍历结果为:",

printTreeLayer(root)

程序的运行结果为：

二叉树层序遍历结果为：4261357

反转后的二叉树层序遍历结果为：4627531

算法性能分析：

由于对给定的二叉树进行了一次遍历，因此，时间复杂度为O(N)。[考点]如何对二叉树进行镜像反转

5.

给定一趟旅途旅程中所有的车票信息，根据这个车票信息找出这趟旅程的路线。例如：给定下面的车票：(“西安”到“成都”)，(“北京”到“上海”)，(“大连”到“西安”)，(“上海”到“大连”)。那么可以得到旅程路线为：北京-＞上海，上海-＞大连，大连-＞西安，西安-＞成都。假定给定的车票不会有环，也就是说有一个城市只作为终点而不会作为起点。正确答案：对于这种题目，一般而言可以使用拓扑排序进行解答。根据车票信息构建一个图，然后找出这张图的拓扑排序序列，这个序列就是旅程的路线。但这种方法的效率不高，它的时间复杂度为O(N)。这里重点介绍另外一种更加简单的方法：hash法(python中可以使用字典实现)。主要的思路为根据车票信息构建一个字典，然后从这个字典中找到整个旅程的起点，接着就可以从起点出发依次找到下一站，进而知道终点。具体的实现思路为：

(1)根据车票的出发地与目的地构建字典。

Tickets={("西安"到"成都"),("北京"到"上海"),("大连"到"西安"),("上海"到"大连")}

(2)构建Tickets的逆向字典如下(将旅程的起始点反向)：

ReverseTickets={("成都"到"西安"),("上