4.10字节跳动后端笔试
4.10笔试第四题
凑成卡组的最少购买次数
from itertools import combinations
n = int(input())
prod = []
for _ in range(n):
p = list(map(int,input().split()))
prod += [p]
dp = [[float('Inf') for _ in range(2**10)] for _ in range(n+1)]
dp[0][0] = 0
for i in range(1,n+1):
for j in range(2**10):
dp[i][j] = min(dp[i][j],dp[i-1][j])
k = []
if j & 1 << prod[i-1][0] != 0:
k += [prod[i-1][0]]
if j & 1 << prod[i-1][1] != 0:
k += [prod[i-1][1]]
if j & 1 << prod[i-1][2] != 0:
k += [prod[i-1][2]]
k = list(set(k))
if not k:
continue
for _ in k:
dp[i][j] = min(dp[i][j],dp[i][j ^ 1 << _]+1)
if len(k) >= 2:
for comb in combinations(k,2):
dp[i][j] = min(dp[i][j], dp[i][(j ^ 1 << comb[0]) ^ 1 << comb[1]]+ 1)
if len(k) == 3:
dp[i][j] = min(dp[i][j], dp[i][((j ^ 1 << k[0]) ^ 1 << k[1]) ^ 1 << k[2]]+ 1)
print(dp[-1][-1]) 刷字节笔试3.27
第一题
给定长度为n的数组的元素只有0或1，问该数组的每个1之间是否至少有k个0？
def have_k_0(k,arr,n):
n1 = sum(arr)
if n1 > (n // (k+1) + 1):
return False
stack,flag = [],0
for s in arr:
if s == 0 and flag == 1:
stack.append(s)
elif s == 1 and flag == 1:
flag == 1
if len(stack) >= k:
stack.clear()
else:
print('type II error')
return False
elif s == 1 and flag == 0:
flag = 1
return True 工作量为N，初始效率为1，效率每分钟加1，最大效率为M。最大效率可持续T分钟，之后会被强制休息10分钟，然后效率从1开始。允许主动休息5分钟，效率减半。问完成工作所需最少时间。
def MinTime(N,M,T): m,total_time,max_t = 1,0,0 while N > 0: if m < M: N -= m m += 1 total_time += 1 continue if max_t <= T - 2: N -= m total_time += 1 max_t += 1 else: if N - m <= 0: N -= m total_time += 1 else: total_time += 5 m = m // 2 return total_time
一根长度为x的魔法棒，选最长的偶数长度对半切割，从0秒到n秒，每秒切割一次，共n+1次。每根魔法棒每秒长度+1
def max_stick(x,n): #cut longest even stick def cut(odd_sticks,even_sticks,t): if t % 2: if odd_sticks: ## stick = odd_sticks.pop() else: return odd_sticks,even_sticks else: if even_sticks: stick = even_sticks.pop() else: return odd_sticks,even_sticks new_stick = (stick + t)//2 if (new_stick - t) % 2: odd_sticks += [new_stick - t] * 2 else: even_sticks += [new_stick - t] * 2 return sorted(odd_sticks),sorted(even_sticks) #separate even odd sticks odd_sticks, even_sticks = [],[] if x % 2: odd_sticks += [x] else: even_sticks += [x] #cut one each time, cut n+1 time for t in range(n+1): odd_sticks,even_sticks = cut(odd_sticks,even_sticks,t) #empty list if odd_sticks and even_sticks: return max(odd_sticks[-1],even_sticks[-1]) + n else: return (odd_sticks[-1] or even_sticks[-1]) + n第四题
给定N个人，部分人可以互相通信，比如 a -> b, 那么b->a；也可以间接通信，比如a->b 且 b ->c，那么a ->c。
每次通信耗时1秒，问把一条信息传递给所有人，最少耗时多少秒？
while True:
if True:
N = int(input('>> 输入人数:'))
dp = [[float('inf') for _ in range(N)] for _ in range(N)]
for i in range(N):
dp[i][i] = 0
i_list = list(map(int,input('第'+str(i+1)+'个人的路径:').split()))
for j in range(i_list[0]):
dp[i][i_list[j+1]-1] = min(1,dp[i][i_list[j+1]-1])
dp[i_list[j+1]-1][i] = dp[i][i_list[j+1]-1]
for k in range(N):
for i in range(N):
for j in range(N):
dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j])
paths = [max(start) for start in dp]
print(min(paths))
else:
break 
查看29道真题和解析
