字节笔试，彻底拿下！（0908秋招笔试真题解析）

大家好，我是吴师兄。

继续每天陪大家练习一场大厂算法题，拿下秋招！

今天练习的是 字节跳动秋招笔试题 。很有难度的一场笔试。

2024 年的大厂真题可以在我的网站上进行练习。

网站地址： https://oj.algomooc.com/

关注吴师兄，算法学习好轻松

1、小U的购物策略

小U有 个钱包，每个钱包中装有不同数量的现金，表示为 元。小U计划每天使用一个钱包的全部金额购买单价为 元的商品。在开始购物之前，小U可以选择性地向一些钱包中加入更多的钱，但总额不能超过 元。小U希望制定一个最优策略，使得他能够购买最多数量的商品。现在他想知道，在最优策略下，他最多能购买多少件该商品。

输入

首先输入一行包含三个整数 ，分别代表钱包的数量，商品的单价，以及小U最多可以加入钱包中的钱的总额。

接下来的一行输入 个正整数 ，分别代表每个钱包中的初始金额。

输出

输出一个整数，表示小U在最优策略下最多能购买的商品数量。

样例

输入：
5 3 2
4 4 3 1 2

输出：
4

提示：
开始时，小U有5个钱包，单价为3元的商品。钱包金额分别为4, 4, 3, 1, 2元。他可以在第4个钱包中加2元，使得第4个钱包的金额变为3元，从而购买1件商品。总共能购买4件商品。

解答

首先计算出所有钱包买出来的物品个数总数并计入，然后对a中的每个元素x，-x % k就是所需要补充的差额。如果-x % k为0，那么已经补完差额，不需要再计入。

接下来基于贪心的思想对差额进行排序，每次选择最小差额的进行补充。

如果补充完差额后还有剩余，那么直接使用剩余的额度进行购买。

代码

# 读取输入的三个整数，n为钱包数量，k为商品单价，m为总共可添加的最大金额
n, k, m = map(int, input().split())
# 读取每个钱包中的初始金额，并存储在列表a中
a = list(map(int, input().split()))

# 初始商品总数，通过遍历每个钱包计算每个钱包能买的商品数量，使用整除操作
ans = sum(x // k for x in a)

# 计算每个钱包需要补充到下一个整数倍的k的金额，并排序
# -x % k 计算当前钱包金额与最近的k的倍数之间的差额
rest = sorted([-x % k for x in a])

# 遍历每个钱包需要补充的金额，检查是否有足够的预算来补充这个差额
for x in rest:
    if 0 < x <= m:  # 确保补充金额是正数且不超过剩余的可用金额m
        ans += 1  # 如果可以补充，商品总数增加1
        m -= x    # 并从总预算中扣除这部分补充金额

# 如果处理完所有钱包后还有剩余金额，计算这部分剩余金额能购买的商品数量
ans += m // k

# 输出最终能购买的商品总数
print(ans)

2、小R的数组操作

小R有一个长度为 的数组。在任意时刻，她可以选择其中的 个数并对它们进行取反操作。小R希望知道，通过若干次这样的操作之后，所有数组元素之和能达到的最大值是多少。

输入

首先输入一个整数 ，表示数组的长度为 。

接下来一行输入 个整数，表示数组 的元素。

输出

输出一个整数，表示所有数组元素之和经过若干次取反操作后的最大值。

样例

输入：
3
1 2 3 -4 5

输出：
15

提示：
选择2, 3, -4进行取反操作，数组变为1, -2, -3, 4, 5。
选择-2, 4, 5进行取反操作，数组变为1, 2, -3, -4, -5。
选择-3, -4, -5进行取反操作，数组变为1, 2, 3, 4, 5，总和达到最大值15。

解答

假设原数组a不包含0。

假设原来数组中有c个负数，考虑每次操作中，选择k个负数, n - k个正数进行取反，其中k满足 0 <= k <= min(c, n), 0 <= n - k <= min(m - c, n) 。那么，进行一次操作后，负数个数减少了k个，增加了n - k个。这也意味着，负数从c个变成了 c + n - 2 * k 个。

如果n是偶数，那么负数个数c的奇偶性不会反转，因此无论如何操作，如果原本c为奇数，那么数组至少会保留一个负数。

如果n是奇数，那么负数个数c的奇偶性会反转，因此数组可以做到没有负数。

因此，如果n是偶数，c是奇数，那么最优解是最小值为负，其余值为正；否则所有数都可以为正。

如果数组a包含0，那么所有数都可以变为非负，因为0可以视为“负数”的那一部分，也可以不视为“负数”的那一部分。

代码

# 读取输入的整数n，表示数组的长度为2n-1
n = int(input())
# 读取数组a的元素，使用map函数将输入的字符串转换为整数列表
a = list(map(int, input().split()))

# 创建一个新列表b，其中的元素是数组a中每个元素的绝对值，这个列表还要进行排序
b = sorted(abs(x) for x in a)

# 初始化答案变量ans
# 如果原数组中包含0或者n是奇数（可以保证经过操作后所有数都为正）
if 0 in a or n & 1:
    ans = sum(b)  # 直接将b中所有元素求和，因为可以使所有元素为正
else:
    # 统计原数组中负数的个数
    neg_c = sum(1 for x in a if x < 0)
    # 如果负数个数为奇数，n为偶数时，无法通过取反操作消除所有负数
    if neg_c & 1:
        ans = sum(b[1:]) - b[0]  # 将最小的元素保持为负，其他元素取为正
    else:
        ans = sum(b)  # 负数个数为偶数，可以通过操作使所有元素为正

# 输出最终结果
print(ans)

3、小M的奇妙树

小M有一棵包含 个节点的树，其中编号为1的节点是根节点。每个节点都有一个权值 。如果树中任意节点的权值都大于或等于其所有子节点权值的总和，这棵树被认为是一棵奇妙树。小M可以通过对任意节点执行加一操作来增加其权值。请问，小M最少需要进行多少次操作才能使这棵树变成一棵奇妙树？

输入

首先输入一个整数 ，表示树的节点数。

接下来一行输入 个整数 ，表示每个节点的权值。

随后的 行，每行两个整数 和 ，表示节点 和 之间存在一条边。

输出

输出一个整数，表示小M为使树成为奇妙树所需进行的最小操作次数。

样例

输入：
3
1 2 3
1 2
1 3

输出：
4

解答

使用树形动态规划可以求解。假设当前阶段u的所有后代的权值和为s，如果原本a[u] >= s，那么就不需要对u进行操作。否则，对u需要进行s - a[u]次操作，并将s重新赋值给a[u]。此时，以u为根的子树权值之和为s + a[u]。

最终统计所有操作次数之和即可。

代码

import sys

# 增加递归限制，因为默认的Python递归深度较低，不足以处理可能的最大递归深度（10^5）
sys.setrecursionlimit(10 ** 5 + 4)

# 读取输入的整数n，表示树的节点数
n = int(input())
# 读取节点的权值，前面加一个0是为了使数组的索引与节点编号对应（节点从1开始编号）
a = [0] + list(map(int, input().split()))

# 创建图的邻接表表示，多出的一个用于从1开始索引
g = [[] for _ in range(n + 1)]

# 初始化变量ans，用来记录总的操作次数
ans = 0

# 读取n-1条边的信息，构建无向图
for _ in range(n - 1):
    x, y = map(int, input().split())
    g[x].append(y)
    g[y].append(x)


def dfs(u, fa):
    # 初始化子节点权值之和为0
    s = 0
    # 遍历节点u的所有邻接节点
    for v in g[u]:
        if v == fa:  # 跳过父节点，避免回溯
            continue
        # 递归计算子树v的权值和，累加到s上
        s += dfs(v, u)
    # 如果子节点权值之和大于当前节点权值，需要增加当前节点的权值
    if s > a[u]:
        global ans  # 使用全局变量ans
        ans += s - a[u]  # 增加的操作次数为子节点权值之和与当前节点权值的差
        a[u] = s  # 更新当前节点的权值
    return s + a[u]  # 返回以当前节点为根的子树的总权值


# 从根节点1开始递归
dfs(1, 0)
# 输出最少需要的操作次数
print(ans)

4、小F的矩阵染色方案

小F拿到了一个 行 列的矩阵，并打算使用最多四种颜色（分别用字符a, b, c, d表示）为该矩阵的每个格子染色。染色需要满足以下条件：每个同色连通块要么是 的正方形，要么是 的正方形。其中 的正方形恰好有 个， 的正方形恰好有 个。根据四色定理，四种颜色应该足够。请输出一种可能的染色方案。

输入

第1行输入四个整数