大疆软件类B卷编程题 过2.9
第一题
- 无向图中两点的最短距离
- 用的DFS，过了90
def first():
n, p = map(int, input().strip().split(' '))
cost = [[101] * n for _ in range(n)]
for _ in range(p):
x, y, t = map(int, input().strip().split(' '))
cost[x][y] = t
cost[y][x] = t
end = int(input())
def dfs(start, cur_t, min_t):
for i in range(len(cost[start])):
if cost[start][i] <= 100 and (i not in visit) and (cur_t + cost[start][i] <= min_t):
if i == end:
min_t = cur_t + cost[start][i]
continue
visit.add(i)
min_t = dfs(i, cur_t + cost[start][i], min_t)
visit.remove(i)
return min_t
min_time = 100 * n
visit = {0}
print(dfs(0, 0, min_time)) 第二题
- 01背包
- 通过
def second():
n, x = map(int, input().strip().split(' '))
cost = []
for _ in range(n):
cost.append(list(map(int, input().strip().split(' '))))
dp = [[0] * (x + 1) for _ in range(n)]
for i in range(cost[0][1], x + 1):
dp[0][i] = cost[0][0]
for i in range(1, n):
for j in range(x + 1):
if cost[i][1] <= j:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cost[i][1]] + cost[i][0])
else:
dp[i][j] = dp[i - 1][j]
print(dp[-1][-1]) 第三题
- 维护一个单增栈
- 弹出的就是要删的
- 力扣原题 https://leetcode-cn.com/problems/remove-k-digits/
- 通过
def third():
s = input()
k = int(input())
if k == 0:
print(s)
else:
s += '0'
res = []
for c in s:
while res and res[-1] > c:
if k == 0:
break
res.pop()
k -= 1
res.append(c)
for i in range(len(res)):
if res[i] != '0':
print(''.join(res[i:-1]))
break
else:
print('0')
投递快手等公司10个岗位