华为机试原题8.18

题目1:喜爱值最大
第一行:输入总金钱money,商品数量n
此后的n行:(每行代表一个商品,数值分别代表,商品价格、商品可买数量、商品喜爱值)
商品价格 商品数量 商品喜爱值
p1          n1       like1
p2          n2      like2
...
问:如何购买能让喜爱值最大
题目2:商品综合
第一行:手中金钱为money,商品数量为n
第二行:商品的价格表例如[3, 7, 5, 10, 5]
问: 选择某些商品,使得价格正好为money(商品不可重复选择,价格相同的算不同商品)
题目3;连连看
给定一个矩阵,例如
mat = [[1, 0, 2, 0, 3],
[0, 2, 0, 1, 1],
[0, 3, 0, 0, 0]]
给定两点例如:a点位(0,2)b点为(1,1)

问:两点间的路径,最短由几条直线组成(连线只能通过mat中为0的点,其余点为障碍)

第一题参考答案
total, kind_num = [int(x) for x in input().split()]
price = [0] * kind_num
num = [0] * kind_num
like = [0] * kind_num
for i in range(kind_num):
    price[i], num[i], like[i] = [int(x) for x in input().split()]

# 把商品按照数量展平放入 weight val数组 变成背包问题
commodity_num = sum(num)
weight = [0] * commodity_num
val = [0] * commodity_num

# price -> weight  like -> val
cnt = 0
for i in range(kind_num):
    p1, n1, l1 = price[i], num[i], like[i]
    while n1 > 0:
        n1 -= 1
        weight[cnt] = p1
        val[cnt] = l1
        cnt += 1
        
#dp shape为 (commodity_num+1)*(total+1)
dp = [[0] * (total + 1) for _ in range(commodity_num+1)]

for i in range(1, commodity_num + 1):
    weight_one, val_one = weight[i - 1], val[i - 1]
    for j in range(1, total + 1):
        if j >= weight_one:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight_one] + val_one)
        else:
            dp[i][j] = dp[i - 1][j]

print(dp[commodity_num][total])


第二题参考答案
# total为目标商品总价 kind_num为商品数量  price为价目表
total, kind_num = [int(x) for x in input().split()]
price = [int(x) for x in input().split()]

min_pri = min(price)
if total < min_pri:
    print(-1)
else:
    # dp shape为 (kind_num+1)*(total+1)
    # dp[i][j] 意思为 可选商品为 1~i 时候 总价为j 的可组合数量
    dp = [[0] * (total + 1) for _ in range(kind_num + 1)]

    # 把第一列置为 1
    for i in range(kind_num + 1):
        dp[i][0] = 1

    for i in range(1, kind_num + 1):
        val = price[i - 1]
        for j in range(1, total + 1):
            if j >= val:
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - val]
            else:
                dp[i][j] = dp[i - 1][j]
    print(dp[kind_num][total])


第三题参考答案:
#3333333333
def search(ans, one_path, mat, vis, x_end, y_end, x_cur, y_cur, m, n):
    # 如果到了这个点 无需进行下方的一系列判断 直接认为成功到达 记录结果
    if x_cur == x_end and y_cur == y_end:
        one_path.append([x_cur, y_cur])
        ans.append(one_path.copy())  # 这里一定用copy 否则 one_path.pop的时候 ans里的也被修改了
        one_path.pop(-1)  # x_end y2点仅仅使用一次 记录完答案立即pop出去
        return

    # 若不是目的地 检查 边界 是否可走 mat==0  是否已经visit 过
    if x_cur < 0&nbs***bsp;x_cur >= m&nbs***bsp;y_cur < 0&nbs***bsp;y_cur >= n&nbs***bsp;mat[x_cur][y_cur] != 0&nbs***bsp;vis[x_cur][y_cur] == True:
        return

    # 不越界 可走 未visi 进行下一步
    vis[x_cur][y_cur] = True
    one_path.append([x_cur, y_cur])

    search(ans, one_path, mat, vis, y1, x_end, y_end, x_cur - 1, y_cur, m, n)  # 上
    search(ans, one_path, mat, vis, y1, x_end, y_end, x_cur + 1, y_cur, m, n)  # 下
    search(ans, one_path, mat, vis, y1, x_end, y_end, x_cur, y_cur - 1, m, n)  # 左
    search(ans, one_path, mat, vis, y1, x_end, y_end, x_cur, y_cur + 1, m, n)  # 右

    one_path.pop(-1)
    vis[x_cur][y_cur] = False
    return


def check_onepath(one_path):
    if len(one_path) < 2:
        return 0
    # 至少有两个点 先确定开始的方向
    x_direction = one_path[1][0] - one_path[0][0]
    y_direction = one_path[1][1] - one_path[0][1]
    num_of_lines = 1  # 初值为1 至少有一个方向

    for i in range(2, len(one_path)):
        # 判断当前方向
        delta_x = one_path[i][0] - one_path[i - 1][0]
        delta_y = one_path[i][1] - one_path[i - 1][1]

        if delta_x == x_direction and delta_y == y_direction:
            continue
        else:
            # 如果方向不一致 更改方向
            x_direction = delta_x
            y_direction = delta_y
            num_of_lines += 1
    return num_of_lines


def check_ans(paths):
    result = []
    for one_path in paths:
        num_of_lines = check_onepath(one_path)
        result.append(num_of_lines)
    return min(result)


m, n = [int(x) for x in input().split()]

mat = [[0] * n for _ in range(m)]
vis = [[False] * n for _ in range(m)]
ans = []

for i in range(m):
    mat[i] = [int(x) for x in input().split()]

x1, y1, x2, y2 = [int(x) for x in input().split()]

# 初始化部分量 x1 y1点开始 所以这个点设为True 否则有问题
vis[x1][y1] = True
one_path = [[x1, y1]]

# 手动尝试从四个点开始搜索 要不然都放在search里判断就麻烦了
search(ans, one_path, mat, vis, x_end=x2, y_end=y2, x_cur=x1 - 1, y_cur=y1, m=m, n=n)
search(ans, one_path, mat, vis, x_end=x2, y_end=y2, x_cur=x1 + 1, y_cur=y1, m=m, n=n)
search(ans, one_path, mat, vis, x_end=x2, y_end=y2, x_cur=x1, y_cur=y1 - 1, m=m, n=n)
search(ans, one_path, mat, vis, x_end=x2, y_end=y2, x_cur=x1, y_cur=y1 + 1, m=m, n=n)

result = check_ans(ans)
print(result)




#华为机试##实习##笔试题目##面经##秋招##华为#
全部评论
我感觉难度在降低,我还没参加机试,太菜了,一直在观望,不过每次他们机试完,我都会看那些题,你们的题基本可以在华为机试题库中找到相仿的题,他们很多都是新题,我咋就没参加这场机试呢。。。:https://www.nowcoder.com/ta/huawei 第一题:HJ16 购物单 第二题:HJ41 称砝码 第三题:HJ43 迷宫问题
2 回复
分享
发布于 2021-08-19 11:16
第一题 通过了90% 不知道哪里错 了
1 回复
分享
发布于 2021-08-18 22:21
乐元素
校招火热招聘中
官网直投
大家有收到性格测试吗
1 回复
分享
发布于 2021-08-20 09:41
第二题 动态规划 本来都写出来了结果 没有考虑 j<val 的时候  修改后如下,应该对了,大家帮忙看下 输入   25 5 3 5 10 7 5 的dp矩阵如下图  数数最后一列多少个True即可
点赞 回复
分享
发布于 2021-08-19 09:18
第二题昨晚脑子瓦特回溯了有超时的用例,dp应该是这样....
点赞 回复
分享
发布于 2021-08-19 10:28
请问一下,第二题是个多重背包问题吗,需要二进制优化还是单调队列优化
点赞 回复
分享
发布于 2021-08-20 08:10
第二题的要求是啥?输出有多少组组合吗
点赞 回复
分享
发布于 2021-08-21 15:31
我吐了,,请问大哥,第二题的输入用c++怎么写啊??就是[1,2,3,4]怎么变成矩阵?
点赞 回复
分享
发布于 2021-08-22 10:31
第二题还可以写短点
点赞 回复
分享
发布于 2021-08-23 00:51

相关推荐

4 120 评论
分享
牛客网
牛客企业服务