20220828 字节研发第二场笔试题解（后端方向）
不是自己的场，补题记录下。有问题欢迎随时私戳。
T1 数字乘积
有n个元素的数组，元素由[0,1,2,4,8,16,32,64,128,256,512,1024]组成； 现在想从数组中选择一段连续的区间，得到尽可能大的乘积； 输入一个t，代表有t组样例。每个样例有2行： 第一行是n，代表数组长度。 第二行是n个整数，取值为[0,1,2,4,8,16,32,64,128,256,512,1024]。 每个样例输出一行，表示乘积最大的区间[x,y]。如果有多个答案，输出x尽量小的答案。如果仍然有多个答案，输出y尽量小。 input: 2 5 1 2 4 0 8 7 1 2 4 8 0 256 0 output: 1 3 6 6
思路：普通模拟，遇到0就重新开始模拟。模拟过程中更新结果即可。
for _ in range(int(input())):
n = int(input())
arr = list(map(int, input().split()))
x, y, v = 0, 0, arr[0]
l = 0
cnt = 1
for r in range(n):
if arr[r] == 0:
l = r + 1
cnt = 1
else:
cnt *= arr[r]
if cnt > v:
x, y, v = l, r, cnt
elif cnt == v:
if l < x:
x, y = l, r
elif l == x and r < y:
y = r
print(x + 1, y + 1)T2 特征加工计算
在特征加工过程中，我们经常会遇到特征加工依赖，如特征A的加工依赖特征B和特征C，特征C加工又依赖于特征D和特征E，为了保证特征能够正常加工出结果，要避免特征间出现循环依赖，如A依赖B，B又依赖A。现在给出一组待加工的特征，判断指定的特征能否计算出结果，为了简化理解，下面用数字表示特征。 1、输入包含多行数字，每行包含至少1列数字，每列之间用空格分开 2、第一行只有一列，表示输入数据行数 3、第二行是要判断的特征，会包含多列，需要判断这些特征是否能够被计算，特征数字范围（1-9） 4、从第三行开始，每行数字表示特征之间的依赖关系（第一列的特征依赖其他列的特征）。如：134，表示1依赖3和4。 输出多列数字，每列表示一个待判定特征的结果，1表示该特征能够计算出结果，0表示不能计算出结果。输出顺序和第二行待判断特征的顺序保持一致。 input: 3 1 1 2 2 3 1 output: 0 input: 3 1 2 1 2 3 2 4 output: 1 1 input: 3 1 2 1 2 3 2 4 1 output: 0 0
思路：经典拓扑排序，构造好图，然后直接排序即可。
from collections import deque, defaultdict, Counter
n = int(input())
targets = list(map(int, input().split()))
g = defaultdict(list)
ind = Counter()
for _ in range(n - 1):
arr = list(map(int, input().split()))
for i in arr[1:]:
ind[arr[0]] += 1
ind[i] = ind[i]
g[i].append(arr[0])
q = deque()
for i in ind:
if ind[i] == 0:
q.append(i)
while q:
cnt = q.popleft()
for nxt in g[cnt]:
ind[nxt] -= 1
if ind[nxt] == 0:
q.append(nxt)
print(*[0 if ind[i] else 1 for i in targets])T3 翻转后连续子数组的最大和
给定整数数组，其中连续的0个或多个整数构成一个子数组，求翻转任一子数组后，新数组中子数组的和的最大值。 第一行输入为N，代表数组长度。n<=1e6 第二行输入为N个整数，依次为数组的每个元素 输出一个整数K，代表所有可能的新数组中子数组的和的最大值 input: 5 1 2 3 -1 4 output: 10
首先考虑一个子问题：如果我们不能翻转数组，如何求最大子数组和？这个题目是leetcode 53。这个子问题有一个非常经典的dp算法，可以在时间复杂度为O(n)的情况下求最大子数组和，具体可以查询题目题解。
如果我们可以求整体的最大子数组和了，如何转化为我们目前面临的问题呢？
不难看出，对一个子数组进行翻转，实际上就是删除了一部分元素。比如我们要翻转的区间是[l,r]，假设我们有一个k，且l<=k<=r，这个k为[l,r]内部，sum(a[l..k])最大的下标，也就是说，我们要删除[k+1,r]这段元素。使得a[l..k]可以和a[r+1..]接上。
那我们本次翻转，可以得到的最大子数组和就是：以a[k]为结尾的最大子数组和+以a[r+1]开头的最大子数组和。
以更简单的方式说明一下上述过程：
原来数组：a[l], a[l+1], ..., a[k], a[k+1], ..., a[r] a[r+1] a[r+2] ... 经过翻转：a[r], r[r-1], ..., a[k], a[k-1]，..., a[l] a[r+1] a[r+2] ...
因为我们要删除的是[k+1,r]这段元素，删除之后会使得数组分为2段。那我们反向考虑，如果我们要将数组分成2段，如何得到最大子数组和呢？也就是左边段的最大子数组和+右边段的最大子数组和。
用变量形式考虑：我们先确定一个k，以a[k]为结尾的最大子数组和为基准，然后找k的右侧最大的子数组和。根据我们的规则，这两段数组和是一定可以粘在一起的。只要我们遍历k，用O(1)的方式求出来k右侧最大的子数组和，那么我们就可以以一个总体O(n)的复杂度求得答案。
可以把数字分2段求：
- 以a[k]为结尾的最大子数组和，这个很好求，不多说了。
- k右侧最大的子数组和，也就是以k右侧任意点为起点，可以得到的最大子数组和。那么我们可以反向考虑，可以考虑从右往左，以j(j>k)为结尾的最大子数组和，这样求得这部分的方式可以像第一步一样容易。
n = int(input())
a = list(map(int, input().split()))
r_maxv = [0] * n
r_maxv[-1] = a[-1]
rmv = a[-1]
for i in range(n - 2, -1, -1):
rmv = max(rmv + a[i], 0)
r_maxv[i] = max(r_maxv[i + 1], rmv)
ans = r_maxv[0]
lmv = 0
for i in range(n - 1):
lmv = max(lmv + a[i], 0)
ans = max(ans, lmv + r_maxv[i + 1])
print(ans)T4 删除一次得到子数组最大和
给定整数数组，我们称其中连续的0个或多个整数为一个子数组，求删除任一元素后，新数组中长度为k的子数组的和的最大值 第一行输入为N和K，N代表数组长度，K代表子数组长度。k<n<=1e6 第二行输入为N个整数，依次为数组的每个元素 输出一个S，代表所有可能新数组中长度为k的子数组和的最大值。 input: 5 3 2 1 3 -1 4 output: 8
思路：滑动窗口，考虑前k+1个元素的数组的和，然后删除这k+1个元素里面最小的元素，作为本轮贡献。然后这个数组向右滑动，每次增加一个新元素，删除一个旧元素，用堆维护一下历史元素，懒惰删除保证复杂度不会恶化就可以了。
from collections import Counter
from heapq import *
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
ans = 0
deld = Counter() # lazy del
h = []
for i in range(k):
heappush(h, a[i])
s = sum(h)
for i in range(k, n):
heappush(h, a[i])
s += a[i]
while deld[h[0]]:
deld[h[0]] -= 1
heappop(h)
ans = max(ans, s - h[0])
s -= a[i - k]
deld[a[i - k]] += 1
print(ans)#字节跳动##字节##字节笔试##笔试#
查看22道真题和解析