做完字节秋招笔试题，难受了......

大家好，我是吴师兄。

最近给训练营的学员新增了几场大厂真题的直播，反响不错，所以在秋招结束之前，决定后续每周都讲解两到三场的校招真题，会按照考试场次进行讲解，明天晚上 8 点 30 邀请了一个 LeetCode 周赛前 10 的朋友来讲解 9 月 8 日字节跳动笔试的几道真题，感兴趣的小伙伴可以通过下面的直播链接进入观看。

直播链接：https://ntpkq.xetlk.com/sl/yPpSE

我们今天先来看看文字题解。

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

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

小U的购物策略

题目描述

解题思路

本题的目标是让小 U 通过最优策略，用有限的预算尽可能购买更多的商品。每个钱包中的金额是固定的，但小U可以向某些钱包中添加额外的钱，总额不能超过一个给定的最大值。商品的单价是固定的，所以问题转化为通过合理分配小U的预算，来让钱包中的钱尽可能购买更多的商品。

1. 直接购买 ：对于每个钱包，首先计算它能直接购买的商品数量，即用钱包中的金额整除商品的单价 k 。这样我们可以初步计算出一个能购买商品的总数。
2. 计算每个钱包的差额 ：对于每个钱包剩下的钱，计算它需要补充多少金额才能刚好多买一个商品。这个差额可以通过 -a_i % k 来计算。例如，如果某个钱包有4元，商品单价为3元，那么它需要补充 -4 % 3 = 2 元才能再买一个商品。
3. 贪心策略补充差额 ：我们将所有钱包的差额进行排序，从最小的差额开始，用小U的预算进行补充。每补充一次，小U就可以多购买一个商品。只要小U的预算允许，我们就不断进行这个操作。
4. 处理剩余预算 ：如果在处理完所有差额之后，仍然有剩余的预算，那么可以将剩余的钱全部用于购买商品。剩余的钱直接通过整除商品单价的方式再购买商品。

优化思路

由于题目数据范围较大（钱包数量可以达到10^5），我们需要在 O(n log n) 的时间复杂度内解决问题。计算每个钱包的差额是 O(n) 的操作，而排序这些差额的时间复杂度是 O(n log n) 。这是可行的复杂度。

参考代码

# 读取输入的三个整数，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 # 确保补充金额是正数且不超过剩余的可用金额m
        ans += 1  # 如果可以补充，商品总数增加1
        m -= x    # 并从总预算中扣除这部分补充金额

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

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

小 R 的数组操作

题目描述

解题思路

要最大化数组的和，目标是让更多的元素为正值。对于负数元素，我们希望通过选择 n 个数取反操作将它们变为正数，而对于正数则尽量避免让它们变为负数。

问题的关键在于：

1. 取反操作次数和 n 的奇偶性 ：

• 如果 n 是奇数，经过若干次操作，可以改变负数的奇偶性（即最终剩余的负数个数可以是0或1），因此可以消除所有的负数，甚至能把数组和变为正数的最大和。
• 如果 n 是偶数，并且原数组中的负数个数是奇数，那么不论如何操作，最终至少会剩下一个负数。

• 如果数组中存在0，那么它可以帮助解决负数的问题，因为我们可以选择0进行取反，而不会改变数组和。因此，如果数组中存在0，我们可以认为所有数都能变为非负数。

• 我们首先将所有元素取绝对值，并计算这些绝对值的总和。如果取反操作无法将所有负数消除，则保留一个最小的绝对值作为负数，这样损失会最小化。

具体操作步骤：

1. 绝对值排序 ：将数组中的每个数取绝对值，然后对这些绝对值进行排序。
2. 处理负数个数的奇偶性 ：如果负数个数为奇数，且 n 是偶数，则最终会剩下一个负数，我们通过保留一个最小的绝对值来让负数对结果的影响最小化。
3. 计算最大和 ：根据负数个数的奇偶性和数组中是否有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 % 2 == 1:
    ans = sum(b)  # 直接将b中所有元素求和，因为可以使所有元素为正




    

else:
    # 统计原数组中负数的个数
    neg_c = sum(1 for x in a if x 0)
    # 如果负数个数为奇数，n为偶数时，无法通过取反操作消除所有负数
    if neg_c % 2 == 1:
        ans = sum(b) - 2 * b[0]  # 将最小的元素保持为负，其他元素取为正
    else:
        ans = sum(b)  # 负数个数为偶数，可以通过操作使所有元素为正

# 输出最终结果
print(ans)

小M的奇妙树

题目描述

解题思路

这道题目本质上是一个树形 动态规划 问题，要求我们通过操作来使每个节点的权值满足其子节点权值总和不超过当前节点的权值。我们可以通过深度优先搜索（DFS）从下往上递归地处理每个节点，保证每个节点的权值满足奇妙树的条件。

1. DFS 递归 ：

• 从根节点出发，对于每个节点，我们递归处理其子节点，累加子节点的权值总和 S 。
• 如果当前节点的权值小于其子节点权值的总和 S ，则需要对当前节点增加 S - a[i] 次操作，使得当前节点的权值满足条件。
• 在递归返回时，将当前节点的权值更新为调整后的权值。

• 每个递归函数返回当前节点的子树权值之和，这样父节点可以利用子节点的返回值来计算子节点的权值总和。

• 使用一个全局变量 ans 来记录所有操作的次数。

详细步骤：

1. 初始化树的邻接表表示。
2. 从根节点开始递归，利用深度优先搜索（DFS）遍历整棵树。
3. 对于每个节点，累加其子节点的权值和，如果当前节点的权值小于其子节点权值和，则需要增加操作次数。
4. 返回以当前节点为根的子树的权值总和。
5. 最终输出最少的操作次数。

参考代码

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)

小F的矩阵染色方案

题目描述

解题思路

基本思路 ：我们需要通过贪心的方法在矩阵中先放置 x 个 2 x 2 正方形，并且在剩余的空位放置 y 个 1 x 1 正方形。由于最多可以使用四种颜色，并且需要避免同色相邻，所以我们可以通过交替使用 a , b , c , d 四种颜色来填充矩阵。

1. 放置 2 x 2 正方形 ：我们首先从矩阵的左上角开始，优先放置 x 个 2 x 2 的正方形。每次放置一个 2 x 2 的正方形时，可以根据当前行号和列号的奇偶性交替使用 a 和 b 两种颜色，或者其他颜色，确保颜色不会冲突。
2. 放置 1 x 1 正方形 ：在放置完 2 x 2 正方形后，剩下的未被染色的格子放置 y 个 1 x 1 的正方形。在放置每一个 1 x 1 正方形时，我们需要确保它的颜色与其左边和上边的颜色不同。
3. 无解判断 ：如果矩阵的大小无法容纳 x 个 2 x 2 的正方形（即可放置的 2 x 2 正方形的数量小于 x ），则返回 -1 表示无解。

算法流程