首页 > 华为机试原题8.18
头像
谁能给我个offer啊
编辑于 2021-08-19 15:54
+ 关注

华为机试原题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)




更多模拟面试

全部评论

(9) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐