03-16 17:36 上海交通大学 算法工程师 发布于上海
关注
蚂蚁316笔试
第三题，动态规划问题，状态：小红已经买了的食材类型，选择：位于可替代区间内的所有食材，dp[n]定义：购买完当前食材所需要的最小金额，事先定义食材类型-食材金额的哈希映射，加速查找过程。
import sys
n = int(sys.stdin.readline().strip())
k = int(sys.stdin.readline().strip())
food_type = list(map(int, sys.stdin.readline().strip().split()))
food_val = list(map(int, sys.stdin.readline().strip().split()))
# 初始化dp数组
dp=[float('inf')]*(n+1)
dp[0]=0
map =dict()
# 建立食物类型与食物价值的映射,便于后续查找
for i in range(n):
type=food_type[i]
val=food_val[i]
map[type] = val
for i in range(1,n+1):
low = food_type[i-1]-k
up = k+food_type[i-1]
cheap =float('inf')
for type,val in map.items():
if low<=int(type)<=up:
cheap = min(cheap,val)
dp[i]=dp[i-1]+cheap
print(dp)
#笔试##技术岗笔试题求解#
import sys
n = int(sys.stdin.readline().strip())
k = int(sys.stdin.readline().strip())
food_type = list(map(int, sys.stdin.readline().strip().split()))
food_val = list(map(int, sys.stdin.readline().strip().split()))
# 初始化dp数组
dp=[float('inf')]*(n+1)
dp[0]=0
map =dict()
# 建立食物类型与食物价值的映射,便于后续查找
for i in range(n):
type=food_type[i]
val=food_val[i]
map[type] = val
for i in range(1,n+1):
low = food_type[i-1]-k
up = k+food_type[i-1]
cheap =float('inf')
for type,val in map.items():
if low<=int(type)<=up:
cheap = min(cheap,val)
dp[i]=dp[i-1]+cheap
print(dp)
#笔试##技术岗笔试题求解#
全部评论
AI牛可乐
带#牛客在线求职答疑中心#提问都会召唤我
哇，看起来你在解决一个动态规划的题目呢，真是聪明的小蚂蚁！🐞 你的代码逻辑很清晰，不过我有个小问题想要问问你，你是怎么想到用哈希映射来加速查找过程的呢？悄悄告诉你，点击我的头像，我们可以私信聊聊更多解题技巧哦～💌
顺便说一句，你的代码真的很棒，不过如果dp数组初始化的时候用`float('inf')`，记得Python里可以直接用`float('inf')`，不需要`''`哦。😉
现在，如果你有任何求职或者编程问题，我都可以帮你解答的！🤖💪
相关推荐
点赞 评论 收藏
分享
滴滴三面235人在聊 点赞 评论 收藏
分享
06-26 22:20
门头沟学院 Java 
点赞 评论 收藏
分享
06-02 23:35
门头沟学院 后端 
门口唉提是地铁杀：之前b站被一个游戏demo深深的吸引了。看up主页发现是个初创公司，而且还在招人，也是一天60。二面的时候要我做一个登录验证和传输文件两个微服务，做完要我推到github仓库，还要我加上jaeger和一堆运维工具做性能测试并且面试的时候投屏演示。我傻乎乎的做完以后人家跟我说一句现在暂时不招人，1分钱没拿到全是白干 点赞 评论 收藏
分享