2021-7-5【虾皮笔试】：机器人
2021-7-5【虾皮笔试】：
机器人题目：
我的思路：用dfs找出所有能到达终点的路径，再用前缀和数组求出每条路径的触底体力值minH（也就是从路径头走到路径尾会出现的最低体力值），最后求出所有路径触底体力值的最大值，如果最大值大于0，直接返回1；否则返回触底体力值-minH+1.
# 虾皮笔试-机器人
class Solution:
def minimumInitHealth(self, rooms, startPoint, endPoint):
col_total = len(rooms[0])
row_total = len(rooms)
rooms_total = col_total * row_total
# 记录访问过的
visited = [[False for _ in range(col_total)] for _ in range(row_total)]
# res记录路径
res = []
def dfs(rooms, row, col, path, visited, res):
# stop condition
if (row == endPoint[0] and col == endPoint[1])&nbs***bsp;len(path) == rooms_total:
if row == endPoint[0] and col == endPoint[1]:
temp = path[:]
temp.append(rooms[row][col])
res.append(temp)
return
# bound
if row >= row_total&nbs***bsp;row < 0&nbs***bsp;col >= col_total&nbs***bsp;col < 0&nbs***bsp;visited[row][col]:
return
# 回溯
visited[row][col] = True
path.append(rooms[row][col])
dfs(rooms, row + 1, col, path, visited, res)
dfs(rooms, row - 1, col, path, visited, res)
dfs(rooms, row, col + 1, path, visited, res)
dfs(rooms, row, col - 1, path, visited, res)
path.pop()
visited[row][col] = False
dfs(rooms, startPoint[0], startPoint[1], [], visited, res)
print('所有路径：', res)
minH = []
# 求出所有路径体力的前缀和
for path in res:
sum_ = [0]
for value in path:
sum_.append(sum_[-1]+value)
minH.append(min(sum_))
# 找出最大的触底体力
if max(minH) < 0:
return -max(minH)+1
else:
return 1
if __name__ == '__main__':
s = Solution()
# 测试用例
rooms1 = [[-2, -3, 3], [-5, -10, 1], [10, 30, -5]]
rooms3 = [[-2, -1, 1], [-5, 1, -10], [3, 1, -1]]
rooms2 = [[2, 3, 3], [5, 10, 1], [10, 30, 5]]
start = [0, 0]
end = [2, 2]
res = s.minimumInitHealth(rooms3, start, end)
print(res)
程序还有很多可以优化的地方，欢迎批评指正。
楼主因为忘记考虑路径和大于0的情况才过了60。。发现的时候已经晚了。。。。
#Shopee##笔试题目#
华为HUAWEI工作强度 1372人发布
