最容易想到的方法就是尝试所有可能的路径，找出可达的一条路。显然这种方法效率非常低下，这里重点介绍一种效率更高的回溯法。主要思路为：当碰到死胡同的时候，回溯到前一步，然后从前一步出发继续寻找可达的路径。算法的主要框架为：

申请一个结果矩阵来标记移动的路径 　　if　到达了目的地 　　打印解决方案矩阵 　　else 　　(1)在结果矩阵中标记当前为1(1表示移动的路径)。 　　(2)向右前进一步，然后递归地检查，走完这一步后，判断是否存在到终点的可达的 路线。 　　(3)如果步骤(2)中的移动方法导致没有通往终点的路径，那么选择向下移动一步， 然后检查使用这种移动方法后，是否存在到终点的可达的路线。 　　(4)如果上面的移动方法都会导致没有可达的路径，那么标记当前单元格在结果矩阵 中为0，返回false，并回溯到前一步中。

   根据以上框架很容易进行代码实现。示例代码如下：
   class Maze:
   def __init__(self):
   self.N=4
   #打印从起点到终点的路线
   def printSolution(self,sol):
   i=0
   while i＜self.N:
   j=0
   while j＜self.N:
   print sol[i][j],
   j+=1
   print '\n'
   i+=1
   #判断x和y是否是一个合理的单元
   def isSafe(self,maze,x,y):
   return x＞=0 and x＜self.N and y＞=0 and\
   y＜self.N and maze[x][y]==1
   """
   使用回溯的方法找到一条从左上角到右下角的路径
   maze表示迷宫,x、y表示起点,sol存储结果
   """
   def getPath(self,maze,x,y,sol):
   #到达目的地
   if x==self.N-1 and y==self.N-1:
   sol[x][y]=1
   return True
   #判断maze[x][y]是否是一个可走的单元
   if self.isSafe(maze,x,y):
   #标记当前单元为1
   sol[x][y]=1
   #向右走一步
   if self.getPath(maze,x+1,y,sol):
   return True
   #向下走一步
   if self.getPath(maze,x,y+1,sol):
   return True
   #标记当前单元为0用来表示这条路不可行,然后回溯
   sol[x][y]=0
   return False
   return False
   

   if __name__=="__main__":
   rat=Maze()
   maze=[[1,0,0,0],
   [1,1,0,1],
   [0,1,0,0],
   [1,1,1,1]]
   sol=[[0,0,0,0],
   [0,0,0,0],
   [0,0,0,0],
   [0,0,0,0]]
   if not rat.getPath(maze,0,0,sol):
   print "不存在可达的路径"
   else:
   rat.printSolution(sol)
   程序的运行结果为：
   1 0 0 0
   1 1 0 0
   0 1 0 0
   0 1 1 1

[考点] 如何求解迷宫问题

最容易想到的方法是首先找出两个数组的交集，然后再把这个交集存储在一个临时数组中，最后再找出这个临时数组与第三个数组的交集。这种方法的时间复杂度为O(N1+N2+N3)，其中N1、N2和N3分别为三个数组的大小。这种方法不仅需要额外的存储空间，而且还需要额外的两次循环遍历。下面介绍另外一种只需要一次循环遍历、而且不需要额外存储空间的方法，主要思路为：
   假设当前遍历的三个数组的元素分别为ar1[i]、ar2[j]、ar3[k]，则存在以下几种可能性：
   (1)如果ar1[i]、ar2[j]和ar3[k]相等，则说明当前遍历的元素是三个数组的公共元素，可以直接打印出来，然后通过执行i+，j+，k+，使三个数组同时向后移动，此时继续遍历各数组后面的元素。
   (2)如果ar1[i]＜ar2[j]，则执行i+来继续遍历ar1中后面的元素，因为ar1[i]不可能是三个数组公共的元素。
   (3)如果ar2[j]＜ar3[k]，同理可以通过j+来继续遍历ar2后面的元素。
   (4)如果前面的条件都不满足，说明ar1[i]＞ar2[j]而且ar2[j]＞ar3[k]，此时可以通过k+来继续遍历ar3后面的元素。
   实现代码如下：
   def findCommon(ar1,ar2,ar3):
   i=0
   j=0
   k=0
   n1=len(ar1)
   n2=len(ar2)
   n3=len(ar3)
   #遍历三个数组
   while i＜n1 and j＜n2 and k＜n3:
   #找到了公共元素
   if ar1[i]==ar2[j] and ar2[j]==ar3[k]:
   print ar1[i],
   i+=1
   j+=1
   k+=1
   #ar[i]不可能是公共元素
   elif ar1[i]＜ar2[j]:
   i+=1
   #ar2[j]不可能是公共元素
   elif ar2[j]＜ar3[k]:
   j+=1
   #ar3[k]不可能是公共元素
   else:
   k+=1
   

   if __name__=="__main__":
   ar1=[2,5,12,20,45,85]
   ar2=[16,19,20,85,200]
   ar3=[3,4,15,20,39,72,85,190]
   fidCommon(ar1, ar2, ar3)
   程序的运行结果为：
   20 85
   算法性能分析：
   这种方法的时间复杂度为O(N1+N2+N3)。

[考点] 如何从三个有序数组中找出它们的公共元素

方法一：蛮力法
   最简单的方法就是遍历两个集合，针对集合中的每个元素判断是否有交集，如果有，则求出它们的交集，实现代码如下：
   class MySet:
   def __init__(self,mins,maxs):
   self.mins=mins
   self.maxs=maxs
   def getMin(self):
   return self.mins
   def setMin(self,mins):
   self.mins=mins
   def getMax(self):
   return self.maxs
   def setMax(self,maxs):
   self.maxs=maxs
   

   def getlntersection(s1,s2):
   if s1.getMin()＜s2.getMin():
   if s1.getMax()＜s2.getMin():
   return None
   elif s1.getMax()＜=s2.getMax():
   return MySet(s2.getMin(),s1.getMax())
   else:
   return MySet(s2.getMin(),s2.getMax())
   elif s1.getMin()＜=s2.getMax():
   if s1.getMax()＜=s2.getMax():
   return MySet(s1.getMin(),s1.getMax())
   else:
   return MySet(s1.getMinO,s2.getMax())
   else:
   return None
   

   def getlntersection2(11,12):
   result=[]
   i=0
   while i＜len(11):
   j=0
   while j＜len(12):
   s=getIntersection(11[i,12[j])
   if s!=None:
   result.append(s)
   j+=1
   i+=1
   return result
   

   if __name__="__main__":
   11=[]
   12=[]
   11.append(MySet(4,8))
   11.append(MySet(9,13))
   12.append(MySet(6,12))
   result=getIntersection2(11,12)
   i=0
   while i＜len(result):
   print "["+str(result[i].getMin())+","+str(result[i].getMax())+"]"
   i+=1
   代码运行结果为：
   [6,8]
   [9,12]
   算法性能分析：
   这种方法的时间复杂度为O(n²)。
   方法二：特征法
   上述这种方法显然没有用到集合有序的特点，因此，它不是最佳的方法。假设两个集合为s1，s2。当前比较的集合为s1[i]和s2[j]，其中，i与j分别表示的是集合s1与s2的下标。可以分为如下几种情况：
   1)s1集合的下界小于s2的上界，如下图所示：
   
   在这种情况下，s1[i]和s2[j]显然没有交集，那么接下来只有s1[i+1]与s2[j]才有可能会有交集。
   2)s1的上界介于s2的下界与上界之间，如下图所示：
   
   在这种情况下，s1[i]和s2[j]有交集(s2[j]的下界和s1[i]的上界)，那么接下来只有s1[i+1]与s2[j]才有可能会有交集。
   3)s1包含s2，如下图所示：
   
   在这种情况下，s1[i]和s2[j]有交集(交集为s2[j])，那么接下来只有s1[i]与s2[j+1]才有可能会有交集。
   4)s2包含s1，如下图所示：
   
   在这种情况下，s1[i]和s2[j]有交集(交集为s1[i])，那么接下来只有s1[i+1]与s2[j]才有可能会有交集。
   5)s1的下界介于s2的下界与上界之间，如下图所示：
   
   在这种情况下，s1[i]和s2[j]有交集(交集为s1[i]的下界和s2[j]的上界)，那么接下来只有s1[i]与s2[j+1]才有可能会有交集。
   6)s2的上界小于s1的下界，如下图所示：
   
   在这种情况下，s1[i]和s2[j]显然没有交集，那么接下来只有s1[i]与s2[j+1]才有可能会有交集。
   根据以上分析给出实现代码如下：
   class MySet:
   def __init__(self,mins,maxs):
   self.mins=mins
   self.maxs=maxs
   def getMin(self):
   return self.mins
   def setMin(self,mins):
   self.mins=mins
   def getMax(self):
   return self.maxs
   def setMax(self,maxs):
   self.maxs=maxs
   

   def getlntersection(11,12):
   result=[]
   i=0
   j=0
   while i＜len(11)and j＜len(12):
   s1=11[i]
   s2=12[j]
   if s1.getMin()＜s2.getMin():
   if s1.getMax()＜s2.getMin():
   i+=1
   elif s1.getMax()＜=s2.getMax():
   result.append(MySet(s2.getMin(),s1.getMax(()))
   i+=1
   else:
   result.append(MySet(s2.getMin(),s2.getMax()))
   j+=1
   elif s1.getMin()＜=s2.getMax():
   if s1.getMax()＜=s2.getMax():
   result.append(MySet(s1.getMin(),s1.getMax()))
   i+=1
   else:
   result.append(MySet(s1.getMin(),s2.getMax()))
   j+=1
   else:
   j+=1
   return result
   

   if __name__="__main__":
   11=[]
   12=[]
   11.append(MySet(4,8))
   11.append(MySet(9,13))
   12.append(MySet(6,12))
   result=getIntersection(11,12)
   i=0
   while i＜len(result):
   print "["+str(result[i].getMin())+","+str(result[i].getMax())+"]"
   i+=1
   算法性能分析：
   这种方法的时间复杂度为O(N1+N2)，其中N1、N2分别为两个集合的大小。

[考点] 如何求两个有序集合的交集

如果使用常规的排序方法，虽然最好的排序算法的时间复杂度为O(NlOg₂^N)，但是使用常规排序算法显然没有用到数组中有大量重复数字这个特性。如何能使用这个特性呢?下面介绍两种更加高效的算法。
   方法一：AVL树
   这种方法的主要思路为：根据数组中的数构建一个AVL树，这里需要对AVL树做适当的扩展，在结点中增加一个额外的数据域来记录这个数字出现的次数，在AVL树构建完成后，可以对AVL树进行中序遍历，根据每个结点对应数字出现的次数，把遍历结果放回到数组中就完成了排序，实现代码如下：
   # AVL树的结点
   class Node:
   def __init__(self,data):
   self.data=data
   self.left=self.right=None
   self.height=self.count=1
   

   class Sort:
   #中序遍历AVL树, 把遍历结果放入到数组中
   def inorder(self,arr,root,index):
   if root!=None:
   #中序遍历左子树
   index=self.inorder(arr,root.left,index)
   #把root结点对应的数字根据出现的次数放入到数组中
   i=0
   while i＜root.count:
   arr[index]=root.data
   index+=1
   i+=1
   #中序遍历右子树
   index=self.inorder(arr,root.right,index)
   return index
   #得到树的高度
   def getHeight(self,node):
   if node==None:
   return 0
   else:
   return node.height
   #把以y为根的子树向右旋转
   def rightRotate(self,y):
   x=y.left
   T2=x.right
   #旋转
   x.right=y
   y.left=T2
   y.height=max(self.getHeight(y.left),self.getHeight(y.right))+1
   x.height=max(self.getHeight(x.left),self.getHeight(x.right))+1
   #返回新的根结点
   return x
   #把以x为根的子树向右旋转
   def leftRotate(self,x):
   y=x.right
   T2=y.left
   y.left=x
   x.right=T2
   x.height=max(self.getHeight(x.left),self.getHeight(x.right))+1
   y.height=max(self.getHeight(y.left),self.getHeight(y.right))+1
   # Return new root
   return y
   #获取树的平衡因子
   def getBalance(self,N):
   if (N==None):
   return 0
   return self.getHeight(N.left)-self.getHeight(N.right)
   """
   如果data在AVL树中不存在, 则把data插入到AVL树中, 否则把这个结点对应的count加1即可
   """
   def insert(self,root,data):
   if root==None:
   return (Node(data))
   #data在树中存在,把对应的结点的count加1
   if data==root.data:
   root.count+=1
   return root
   #在左子树中继续查找data是否存在
   if data＜root.data:
   root.left=self.insert(root.left, data)
   #在右子树中继续查找data是否存在
   else:
   root.right=self.insert(root.right,data)
   #插入新的结点后更新root结点的高度
   root.height=max(self.getHeight(root.left),self.getHeight(root.right))+1
   #获取树的平衡因子
   balance=self.getBalance(root)
   #如果树不平衡, 根据数据结构中学过的四种情况进行调整
   #LL型
   if balance＞1 and data＜root.left.data:
   return self.rightRotate(root)
   # RR型
   elif balance＜-1 and data>root.right.data:
   return self.leftRotate(root)
   # LR型
   elif balance＞1 and data>root.left.data:
   root.left=self.leftRotate(root.left)
   return self.rightRotate(root)
   # RL型
   elif balance＜-1 and data＜root.right.data:
   root.right=self.rightRotate(root.right)
   return self.leftRotate(root)
   return root
   #使用AVL树实现排序
   def sort(self,arr):
   root=None #根结点
   n=len(arr)
   i=0
   while i＜n:
   root=self.insert(root,arr[i])
   i+=1
   index=0
   self.inorder(arr,root,index)
   

   if __name__="__main__":
   arr=[15,12,15,2,2,12,2,3,12,100,3,3]
   s=Sort()
   s.sort(arr)
   while i＜len(arr):
   print arr[i],
   i+=1
   代码运行结果为：
   2 22 3 3 3 12 12 12 15 15 100
   算法性能分析：
   这种方法的时间复杂度为O(NLog₂^M)，其中，N为数组的大小，M为数组中不同数字的个数，空间复杂度为O(N)。
   方法二：哈希法
   这种方法的主要思路为创建一个哈希表，然后遍历数组，把数组中的数字放入哈希表中，在遍历的过程中，如果这个数在哈希表中存在，则直接把哈希表中这个key对应的value加1；如果这个数在哈希表中不存在，则直接把这个数添加到哈希表中，并且初始化这个key对应的value为1。实现代码如下：
   def sort(arr):
   data_count=dict()
   n=len(arr)
   #把数组中的数放入 map中
   i=0
   while i＜n:
   if str(arr[i]) in data_count:
   data_count[str(arr[i])]=data_count.get(str(arr[i]))+1
   else:
   data_count[str(arr[i])]=1
   i+=1
   index=0
   for key,value in data_count.items():
   i=value
   while i>0:
   arr[index]=key
   index+=1
   i-=1
   

   if __name__="__main__":
   arr=[15,12,15,2,2,12,2,3,12,100,3,3]
   sort(arr)
   i=0
   while i＜len(arr):
   print arr[i],
   i+=1
   算法性能分析：
   这种方法的时间复杂度为O(N+MLog₂^M)，空间复杂度为O(M)。

[考点] 如何对有大量重复的数字的数组排序

本题可以采用贪心法来解决，具体实现思路如下：
   申请一个数组来记录每台机器的执行时间，初始化为0，在调度任务的时候，对于每个任务，在选取机器的时候采用如下的贪心策略：对于每台机器，计算机器已经分配任务的执行时间+这个任务需要的时间，选用最短时间的机器进行处理。实现代码如下：
   """
   param t 每个服务器处理的时间
   param n 任务的个数
   return 各个服务器执行完任务所需的时间
   """
   def calculate_rocess_time(t,n):
   if t==None or n＜=0:
   return None
   m=len(t)
   proTime=[0]*m
   i=0
   while i＜n:
   minTime=proTime[0]+t[0] #把任务给第j个机器上后这个机器的执行时间
   minIndex=0 #把任务给第minIndex个机器上
   j=1
   while j＜m:
   # 分配到第j台机器上后执行时间更短
   if minTime＞proTime[j]+t[j]:
   minTime=proTime[j]+t[j]
   minIndex=j
   j+=1
   proTime[minIndex]+=t[minIndex]
   i+=1
   return proTime
   

   if __name__=="__main__":
   t=[7,10]
   n=6
   proTime=calculate_process_time(t,n)
   if proTime==None:
   print "分配失败"
   else:
   totalTime=proTime[0]
   i=0
   while i＜len(proTime):
   print "第"+str((i+1))+"台服务器有"+str(proTime[i]/t[i])+"个任务,执行总时间为:"+str(proTime[i])
   if proTime[i]＞totalTime:
   totalTime=proTime[i]
   i+=1
   print "执行完所有任务所需的时间为"+str(totalTime)
   程序的运行结果为：
   第1台服务器有4个任务，执行总时间为：28
   第2台服务器有2个任务，执行总时间为：20
   执行完所有任务所需的时间为28
   算法性能分析：
   这种方法使用了双重循环，因此，时间复杂度为O(mn)。

[考点] 如何对任务进行调度

本题的主要思路如下：对所有的分区进行遍历，同时用一个变量dIndex记录上次分配磁盘的下标，初始化为0；对于每个分区，从上次分配的磁盘开始继续分配，如果没有足够的空间，则顺序找其他的磁盘，直到找到合适的磁盘为止，进行分配；如果找不到合适的磁盘，则分配失败，实现代码如下：
   def is_allocable(d,p):
   dIndex=0 #磁盘分区下标
   i=0
   while i＜len(p):
   #找到符合条件的磁盘
   while dIndex＜len(d) andp[i]＞d[dIndex]:
   dIndex+=1
   #没有可用的磁盘
   if dIndex＞=len(d):
   return False
   #给分区分配磁盘
   d[dIndex]-=p[i]
   i+=1
   return True
   

   if __name__=="__main__":
   d=[120,120,120] #磁盘
   p=[60,60,80,20,80] #分区
   if is_allocable(d,p):
   print "分配成功"
   else:
   print "分配失败"
   程序的运行结果为：
   分配成功
   算法性能分析：
   这种方法使用了双重循环，因此，时间复杂度为O(MN)。

[考点] 如何对磁盘分区