2017阿里算法两道笔试试题解答

题目一，最短时间问题：
import queue
class Graph(object):
    def __init__(self,nNode,nEdge):
        self.Nodes = [0]*nNode
        self.nNode = nNode
        self.nEdge = nEdge
        self.arrArcs = [([float('inf')]*nNode) for _ in range(nNode)]
    def readGraphData(self,roads):
        for road in roads:
            self.arrArcs[road[0]][road[1]] = road[2]
            self.arrArcs[road[1]][road[0]] = road[2] 
    def readNodeData(self,Nodes):
        for node in Nodes:
            self.Nodes[node[0]] = node[1]
    def getAdjNode(self,node):
        adjnodes = []
        for j in range(self.nNode):
            if self.arrArcs[node][j] != float('inf'):
                adjnodes.append(j)
        return adjnodes
    def getPassTime(self,i,j,t):
        passtime = 0
        if ((t//self.Nodes[i]) % 2 != 0):
            passtime += t%self.Nodes[i]
        passtime += self.arrArcs[i][j]
        return passtime+t
def search(graph,s,d):
    nNode = graph.nNode
    a = [float('inf')] * nNode
    a[s] = 0
    L = queue.Queue()
    L.put(s)
    while(not L.empty()):
        u = L.get()
        for w in graph.getAdjNode(u):
            temp = graph.getPassTime(u,w,a[u])
            if a[w] > temp:
                a[w] = temp
                if w not in L.queue:
                    L.put(w)
            if (w ==d and len(set(graph.getAdjNode(w)).intersection(set(L.queue))) == 0):
                return a[d] 
题目二，仓库编号问题：
def find_max_i(A,num):
    n = len(A)
    out = []
    for i in range(n-num+1):
        sum_tmp = sum(A[i:i+num])
        out.append(sum_tmp)
    return out
def find_max_unsort(A):
    n = len(A)
    out = []
    for i in range(1,n+1):
        max_tmp = find_max_i(A, i)
        out.append(max_tmp)
    index_i,index_j = find_i_j(out)
    print(index_i,index_j)
    return out[index_i][index_j:index_j+index_i]
def find_i_j(out):
    max_temp = float('-inf')
    for i in range(len(out)):
        for j in range(len(out[i])):
            if out[i][j] > max_temp:
                max_temp = out[i][j]
                index_i = i
                index_j = j
    return index_i,index_j

欢迎大家讨论一下！