阿里0323笔试 嗯。。
阿里笔试感觉思路都挺对的，但是就是ac不了，全是0。。难道是因为read没有读好么，代码贴上了求大家帮忙瞅瞅+指正
再次声明 -- 不是正确答案 不是正确答案 不是正确答案
以防误人子弟
第一题 感觉更像数学题，求排列组合。在n个人中可以取任意数目的人数组成一队，并且可以在其中选队长，问一共有多少种组合方式，最后的结果模10^9+7.
def comb(m,n): child = 1 mom = 1 for i in range(n, n-m, -1): child *= i for j in range(1, m): mom *= j return child / mom def calculateCombination(n): result = 0 for i in range(1, n+1): result += comb(i,n) return result %(10**9 + 7) n = int(input()) result = calculateCombination(n) print(int(result))
第二题 求走的最短路径，一个matrix，S表示start，E表示目的地，剩下的“#“ 表示障碍，”.“表示可以通过，求可以从S到E的最短路径，没有就输出-1.
用了DFS+visited set的方法，不过在本地IDE也没跑出来，有bug。。。刚刚又调试半天没调出来。。。先发出来吧
补充：服气了，应该对角的时候（n-1-x, m-1-y）跑了几个test case都过了
class Solution:
def getSandE(self, matrix, n, m):
for i in range(n):
for j in range(m):
if matrix[i][j] == "S":
S = [i,j]
if matrix[i][j] == "E":
E = [i,j]
return (S, E)
def getSteps(self, S, E, matrix, n, m):
self.result = float("inf")
visited = set()
visited.add((S[0], S[1]))
self.helper(S, E, matrix, n, m, 0, 5, visited)
print("here")
print(self.result)
return self.result
def helper(self, S, E, matrix, n, m, current, flightLeft, visited):
if S == E:
print("find!!!")
print(current, self.result)
self.result = min(self.result, current)
return
print(visited)
print("*********")
position = [[1,0], [-1,0], [0,-1], [0,1]]
for [delta_x, delta_y] in position:
newX = S[0] + delta_x
newY = S[1] + delta_y
if self.isValid(newX, newY, matrix, n, m, visited):
current += 1
visited.add((newX, newY))
self.helper([newX, newY], E, matrix, n, m, current, flightLeft, visited)
visited.remove((newX, newY))
current -= 1
if flightLeft > 0:
newX = n-1-S[0]
newY = m-1-S[1]
if self.isValid(newX, newY, matrix, n, m, visited):
current += 1
flightLeft -= 1
visited.add((newX, newY))
self.helper([newX, newY], E, matrix, n, m, current, flightLeft, visited)
visited.remove((newX, newY))
flightLeft += 1
current -= 1
def isValid(self, x, y, matrix, n, m, visited):
if x<0 or x>=n or y<0 or y>=m or matrix[x][y] == "#" or (x,y) in visited:
return False
return True
matrix = [["#", "S", ".", "."], ["E", "#", ".", "."], ["#", ".", ".", "."], [".", ".", ".", "."]]
s = Solution()
(S, E) = s.getSandE(matrix, 4, 4)
result = s.getSteps(S, E, matrix, 4, 4)
if result == float("inf")":
print(-1)
else:
print(result)
