阿里3.23笔试 python版本
1、从n个人中选择任意数量的人员组成一支队伍，然后从一支队伍中选出一位队长，不同的队长算不同的组合，问这样的组合的数量对10^9+7取模 。
def quick_power_mod(x, n, mod): res = 1 while n: if n & 1: res = res * x % mod n = n >> 1 x = (x ** 2) % mod return res n = 2 mod = 10 ** 9 + 7 mod1 = quick_power_mod(2, n-1, mod) mod2 = n % mod result = (mod1 * mod2) % mod print(result)快速幂算法，递推公式为S=n*(2^n-1)
笔试时递推公式没进一步优化，先去做第二题了，导致时间不太够，递推公式没推好的话会超时。
2、 一个地图n*m，包含1个起点，1个终点，其他点包括可达点和不可达点。 每一次可以：上下左右移动，或使用1点能量从（i,j)瞬间移动到（n-1-i, m-1-j)，最多可以使用5点能量。
def dfs(pos_x, pos_y, road, fly_time, time, min_time):
if time >= min_time:
return min_time
if sum([road[i][j] == 0 for i in range(n) for j in range(m)]) == 0:
return min_time
# down
if (0 <= pos_x + 1 < n) and road[pos_x+1][pos_y] != 1:
if road[pos_x+1][pos_y] == 2:
return time+1
else:
road[pos_x+1][pos_y] = 1
min_time = min(dfs(pos_x+1, pos_y, road, fly_time, time+1, min_time), min_time)
road[pos_x+1][pos_y] = 0
# up
if (0 <= pos_x - 1 < n) and road[pos_x-1][pos_y] != 1:
# print('up')
if road[pos_x-1][pos_y] == 2:
return time+1
else:
road[pos_x-1][pos_y] = 1
min_time = min(dfs(pos_x-1, pos_y, road, fly_time, time+1, min_time), min_time)
road[pos_x-1][pos_y] = 0
# left
if (0 <= pos_y - 1 < m) and road[pos_x][pos_y-1] != 1:
road[pos_x][pos_y-1] = 1
min_time = min(dfs(pos_x, pos_y-1, road, fly_time, time+1, min_time), min_time)
road[pos_x][pos_y-1] = 0
# right
if (0 <= pos_y + 1 < m) and road[pos_x][pos_y+1] != 1:
# print('right')
if road[pos_x][pos_y+1] == 2:
return time+1
else:
road[pos_x][pos_y+1] = 1
min_time = min(dfs(pos_x, pos_y+1, road, fly_time, time+1, min_time), min_time)
road[pos_x][pos_y+1] = 0
# fly machine
if (0 <= n - 1 - pos_x < n) and (0 <= m - 1 - pos_y < m) and road[n-1-pos_x][m-1-pos_y] != 1 and fly_time > 0:
# print('fly')
if road[n-1-pos_x][m-1-pos_y] == 2:
return time+1
else:
road[n-1-pos_x][m-1-pos_y] = 1
min_time = min(dfs(n-1-pos_x, m-1-pos_y, road, fly_time-1, time+1, min_time), min_time)
road[n-1-pos_x][m-1-pos_y] = 0
return min_time
n, m = [4, 4]
road = [[1, 1, 0, 0], [2, 1, 0, 0], [1, 0, 0, 0], [0, 0, 0, 0]]
born_x = 0
born_y = 1
fly_time = 5
min_time = 1000000000000000000000
time = dfs(born_x, born_y, road, fly_time, 0, min_time)
if time == 1000000000000000000000:
time = -1
print(time) 用了dp来做，笔试时也没做出来orz 后来发现问题在于每一次搜索的时候设置了步进的点为1，导致初始设定2为终点的判定始终未找到，以及时间不太够，摔 用惯了台式机再用笔记本写感觉屏幕和键盘用着好难受😂
难受，希望面试时能顺利些，预祝大家都能有好结果♥
#阿里笔试2020##阿里巴巴##笔试题目##Python#
