Python程序员面试分类模拟5

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

给定一棵二叉树，它的每个结点都是正整数或负整数，如何找到一棵子树，使得它所有结点的和最大?正确答案：要求一棵二叉树的最大子树和，最容易想到的办法就是针对（江南博哥）每棵子树，求出这棵子树中所有结点的和，然后从中找出最大值。恰好二叉树的后序遍历就能做到这一点。在对二叉树进行后序遍历的过程中，如果当前遍历的结点的值与其左右子树和的值相加的结果大于最大值，则更新最大值。如下图所示：

在上面这个图中，首先遍历结点-1，这个子树的最大值为-1，同理，当遍历到结点9时，子树的最大值为9，当遍历到结点3的时候，这个结点与其左右孩子结点值的和(3-1+9=11)大于最大值(9)。因此，此时最大的子树为以3为根结点的子树，依此类推，直到遍历完整棵树为止。实现代码如下：

classBiTNode:

def__init__(self):

self.data=None

self.lchild=None

self.rchild=None

classTest:

def__init__(self):

self.maxSum=-2**31

"""

方法功能:求最大子树

输入参数:root:根结点;

maxRoot最大子树的根结点

返回值:以root为根结点子树所有结点的和

"""

deffindMaxSubTree(self,root,maxRoot):

ifroot==None:

return0

#求root左子树所有结点的和

1max=self.findMaxSubTree(root.lchild,maxRoot)

#求root右子树所有结点的和

rmax=self.findMaxSubTree(root.rchild,maxRoot)

sums=1max+rmax+root.data

#以root为根的子树的和大于前面求出的最大值

ifsums＞self.maxSum:

self.maxSum=sums

maxRoot.data=root.data

#返回以root为根结点的予树的所有结点的和

returnsums

"""

方法功能:构造二叉树

返回值:返回新构造的二叉树的根结点

"""

defconstructTree(self):

root=BiTNode()

node1=BiTNode()

node2=BiTNode()

node3=BiTNode()

node4=BiTNode()

root.data=6

node1.data=3

node2.data=-7

node3.data=-1

node4.data=9

root.lchild=node1

root.rchild=node2

node1.lchild=node3

node1.rchild=node4

node2.lchild=node2.rchild=node3.lchild=node3.rchild=\

node4.lchild=node4.rchild=None

returnroot

if__name__=="__main__":

#构造二叉树

test=Test()

root=test.constructTree()

maxRoot=BiTNode()#最大子树的根结点

test.findMaxSubTree(root,maxRoot)

print"最大子树和为:"+str(test.maxSum)

print"对应子捌的根结点为:"+str(maxRoot.data)

程序的运行结果为：

最大子树和为：11

对应子树的根结点为：3

算法性能分析：

这种方法与二叉树的后序遍历有相同的时间复杂度，即为O(N)，其中，N为二叉树的结点个数。[考点]如何求一棵二叉树的最大子树和

2.

在2.5亿个整数中找出不重复的整数，注意，内存不足以容纳这2.5亿个整数。正确答案：由于这道题目与前面的题目类似，也是无法一次性把所有数据加载到内存中，因此也可以采用类似的方法求解。

方法一：分治法

采用hash的方法，把这2.5亿个数划分到更小的文件中，从而保证每个文件的大小不超过可用的内存的大小。然后对于每个小文件而言，所有的数据可以一次性被加载到内存中，因此可以使用子典或set来找到每个小文件中不重复的数。当处理完所有的文件后就可以找出这2.5亿个整数中所有的不重复的数。

方法二：位图法

对于整数相关的算法的求解，位图法是一种非常实用的算法。对于本题而言，如果可用的内存空间超过1GB就可以使用这种方法。具体思路为：假设整数占用4B(如果占用8B，那么求解思路类似，只不过需要占用更大的内存)，4B也就是32位，可以表示的整数的个数为232。由于本题只查找不重复的数，而不关心具体数字出现的次数，因此可以分别使用2bit来表示各个数字的状态：用00表示这个数字没有出现过，01表示出现过1次，10表示出现了多次，11暂不使用。

根据上面的逻辑，在遍历这2.5亿个整数的时候，如果这个整数对应的位图中的位为00，那么修改成01，如果为01那么修改为10，如果为10那么保持原值不变。这样当所有数据遍历完成后，可以再遍历一遍位图，位图中为01的对应的数字就是没有重复的数字。[考点]如何在大量的数据中找出不重复的整数

3.

编写一个函数，根据两个文件的绝对路径算出其相对路径。例如a="/qihoo/app/a/b/c/d/new.c",b="/qihoo/app/1/2/test.c"，那么b相对于a的相对路径是"../../../../1/2/teSt.c"正确答案：首先找到两个字符串相同的路径(/aihoo/app)，然后处理不同的目录结构(a="/a/b/c/d/new.c",b="/1/2/test.c")。处理方法为：对于a中的每一个目录结构，在b前面加“../”，对于本题而言，除了相同的目录前缀外，a还有四级目录a/b/c/d，因此只需要在b="/1/2/test.c"前面增加四个"../"得到的"../../"/../1/2/test.c"就是b相对a的路径。实现代码如下：

defgetRelativePath(path1,path2):

ifpath1==Noneorpath2==None:

print"参数不合法\n"

return

relativePath=""

#用来指向两个路径中不同目录的起始路径

diff1=0

diff2=0

i=0

j=0

len1=len(path1)

len2=len(path2)

whilei＜len1andj＜len2:

#如果目录相同,那么往后遍历

iflist(path1)[i]==list(path2)[j]:

iflist(path1)[i]=='/':

diff1=i

diff2=j

i+=1

j+=1

else:

#不同的目录

#把path1非公共部分的目录转换为"/

diff1+=1#跳过目录分隔符/

whilediff1＜len1:

#碰到下一级目录

iflist(path1)[diff1]=='/':

relativePath+="../"

diff1+=1

#把path2的非公共部分的路径加到后面

diff2+=1

relativePath+=path2[diff2:]

break

returnrelativePath

if__name__=="__main__":

path1="/qihoo/app/a/b/c/d/new.c"

path2="/qihoo/app/1/2/test.c"

printgetRelativePath(path1,path2)

程序的运行结果为：

../../../../1/2/test.c

算法性能分析：

这种方法的时间复杂度与空间复杂度都为O(max(m,n))(其中，m、n分别为两个路径的长度)。[考点]如何求相对路径

4.

给定一个没有排序的链表，去掉其重复项，并保留原顺序，例如链表1-＞3-＞1＞5-＞5-＞7,去掉重复项后变为1-＞3-＞5-＞7。正确答案：方法一：顺序删除

主要思路为：通过双重循环直接在链表上进行删除操作。外层循环用一个指针从第一个结点开始遍历整个链表，然后内层循环用另外一个指针遍历其余结点，将与外层循环遍历到的指针所指结点的数据域相同的结点删除。如下图所示：

假设外层循环从outerCur开始遍历，当内层循环指针innerCur遍历到上图实线所示的位置(outerCur.data==innerCur.data)时，需要把innerCur指向的结点删除。具体步骤如下：

(1)用tmp记录待删除的结点的地址。

(2)为了能够在删除tmp结点后继续遍历链表中其余的结点，使innerCur指向它的后继结点：innerCUFinnerCur.next。

(3)从链表中删除tmp结点。

实现代码如下：

classLNode:

def__new__(self,x):

self.data=x

self.next=None

"""

**方法功能:对带头结点的无序单链表删除重复的结点

**输入参数:head:链表头结点

"""

defremoveDup(head):

ifhead==Noneorhead.next==None:

return

outerCur=head.next#用于外层循环,指向链表第一个结点

innerCur=None#用于内层循环用来遍历outerCur后面的结点

innerPre=None#innerCur的前驱结点

whileouterCur!=None:

innerCur=outerCur.next

innerPre=outerCur

whileinnerCur!=None:

#找到重复的结点并删除

ifouterCur.data==innerCur.data:

innerPre.next=innerCur.next

innerCur=innerCur.next

else:

innerPre=innerCur

innerCur=innerCur.next

outerCur=outerCur.next

if__name__="__main__":

i=1

head=LNode()

head.next=None

tmp=None

cur=head

whilei＜7:

tmp=LNode()

ifi%2=0:

tmp.data=i+1

elifi%3=0:

tmp.data=i-2

else:

tmp.data=i

tmp.next=None

cur.next=tmp

cur=tmp

i+=1

print"删除重复结点前:",

cur=head.next

whilecur!=None:

printcur.data,

cur=cur.next

removeDup(head)

print"\n删除重复结点后:",

cur=head.next

whilecur!=None:

printcur.data,

cur=cur.next

程序的运行结果为：

删除重复结点前：131557

删除重复结点后：1357

算法性能分析：

由于这种方法采用双重循环对链表进行遍历，因此，时间复杂度为O(N2)，其中，N为链表的长度，在遍历链表的过程中，使用了常量个额外的指针变量来保存当前遍历的结点、前驱结点和被删除的结点，因此，空间复杂度为O(1)。

方法二：递归法

主要思路为：对于结点cur，首先递归地删除以cur.next为首的子链表中重复的结点，接着从以cur.next为首的子链表中找出与cur有着相同数据域的结点并删除，实现代码如下：

defremoveDupRecursion(head):

ifhead.nextisNone:

returnhead

pointer=None

cur=head

#对以head.next为首的予链表删除重复的结点

head.next=removeDupRecursion(head.next)

pointer=head.next

#找出以head.next为首的子链表中与head结点相同的结点并删除

whilepointerisnotNone:

ifhead.data=pointer.data:

cur.next=pointer.next

pointer=cur.next

else:

pointer=pointer.next

cur=cur.next

returnhead

"""

方法功能:对带头结点的单链删除重复结点输入参数:head:链表头结点

"""

defremoveDup(head):

if(headisNone):

return

head.next=removeDupRecursion(head.next)

算法性能分析：

这种方法与方法一类似，从本质上而言，由于这种方法需要对链表进行双重遍历，因此，时间复杂度为O(N2)，其中，N为链表的长度。由于递归法会增加许多额外的函数调用，因此，从理论上讲，该方法效率比方法一低。

方法三：空间换时间

通常情况下，为了降低时间复杂度，往往在条件允许的情况下，通过使用辅助空间来实现。具体而言，主要思路为：

(1)建立一个HashSet，HashSet中的内容为已经遍历过的结点内容，并将其初始化为空。

(2)从头开始遍历链表中的所有结点，存在以下两种可能性：

1)如果结点内容已经在HashSet中，那么删除此结点，继续向后遍历。

2)如果结点内容不在HashSet中，那么保留此结点，将此结点内容添加到HashSet中，继续向后遍历。[考点]如何从无序链表中移除重复项

5.

有一个由大小写字母组成的字符串，请对它进行重新组合，使得其中的所有小写字母排在大写字母的前面(大写字母或小写字母之间不要求保持原来次序)。