20220821字节跳动后端笔试题解
T1
双休在家的凯凯真的是太无聊了，他准备和他家的猫玩一个游戏。
凯凯随手写下一串01数列，定义这串数列的子串和为所有长度为2的子串的和。比如数列=010001，有如下长度为2的子串：
01 （前导0， =1）
10
00 （前导0，=0）
00 （前导0，=0）
01 （前导0，=1）
所以和为1+10+0+0+1 = 12
如果要只是算子串和的话，那对喵喵来说实在是太简单了，所以凯凯准备加大难度。
喵喵有k次机会可以交换数列里的相邻两个数（可以不用完这k次机会），使得交换完之后子串和最小。
这下喵喵不会做了，你可以帮帮它么？
输入为先输入一个t，代表t组。然后分别是n、k，字符串。 input: 3 4 0 1010 7 1 0010100 5 2 00110 output: 21 22 12
分析字符串中每一个1，只有3种情况：
- 出现在字符串首部，贡献为10
- 出现在字符串中央，贡献为11
- 出现在字符串末尾，贡献为01
那么只需要考虑能不能把1换到头尾就好了。
for _ in range(int(input())):
n,k=list(map(int,input().split()))
s=input()
n1=s.count('1')
if n1==0:
print(0)
continue
ans=n1*11
ri=s.rindex('1')
rneed=(n-1-ri)
if k>=rneed:
k-=rneed
ans-=10
# 后面交换成功了
if n1==1:
print(1)
continue
else:
lneed=s.index('1')
if k>=lneed:
ans-=1
print(ans)
else:
lneed=s.index('1')
if k>=lneed:
ans-=1
print(ans) T2
第一行输入两个整数n和m，表示迷宫的长和宽。
接下来n行，每行m 个字符， 用于描述迷宫构造，每个字符可能为以下几种：
.表示空地， 玩家在空地时可以选择往 [上，下，左，右] 中的某个方向移动一格
U，D，L，R 分别表示朝向[上，下，左，右] 的传送带，站在传送带上的人会被强制移动到其指向的下一个位置
如果下一个位置还是传送带，会被继续传下去
如果传送带指向迷宫外，玩家会撞在墙上，昏过去，游戏结束，无法再到达出口
O表示迷宫出口
请你找到有多少点按照规则行走不能到达终点。
n<1e5，m<1e5，n*m<1e5 input: 5 5 ..... .RRD. .U.DR .ULL. ....O output: 10
思路来自于一个银牌佬，反向思考，把传送带视为一个单向板。从终点反向遍历，假设你处于一个空地上，你左侧的点只有为R的时候才可以从你这个位置到达R那个位置，然后查找地图上所有O的数量。n*m-count(O)即可。
之前写的深搜思路有问题，已删除。
from collections import deque
n,m=list(map(int,input().split()))
g=[list(input()) for _ in range(n)]
ex,ey=-1,-1
for i in range(n):
for j in range(m):
if g[i][j]=='O':
ex,ey=i,j
break
if ex!=-1:break
q=deque([(ex,ey)])
while q:
x,y=q.popleft()
# up
if x-1>=0 and g[x-1][y] in 'D.':
q.append((x-1,y))
g[x-1][y]='O'
# down
if x+1<n and g[x+1][y] in 'U.':
q.append((x+1,y))
g[x+1][y]='O'
# left
if y-1>=0 and g[x][y-1] in 'R.':
q.append((x,y-1))
g[x][y-1]='O'
# right
if y+1<m and g[x][y+1] in 'L.':
q.append((x,y+1))
g[x][y+1]='O'
onum=sum(line.count('O') for line in g)
print(n*m-onum)
T3
在广告平台中，为了给广告主一定的自由性和效率，允许广告主在创造标题的时候以通配符的方式进行创意提交。线上服务的时候，会根据用户的搜索词触发的bidword对创意中的通配符（通配符是用成对{}括起来的字符串）进行替换（用0个或者多个字符替换通配符），用来提升广告投放体验。例如：{末日血战}，上线送SSR英雄，三天集鲚无敌阵容！”，会被替换成“帝国时代下载上线送SSR英雄，三天集齐无敌阵容！”。给定一个含有通配符的创意和一句标题，判断这句标题是否从该创意替换生成的。
输入一个n，有n个标题。第一行是带有通配符的创意，下面n行是所有标题。对于每一行标题，如果可以用通配符匹配，输出True否则输出False。
input:
4
ad{XYZ}cdc{Y}f{x}e
adcdcefdfeffe
adcdcefdfeff
dcdcefdfeffe
adcdcfe
output:
True
False
False
True普通回溯，注意记录每一个通配符的对应字符串。不是自己的场，没时间写了。
T4
小明和小红在玩摇骰子游戏，每个骰子有固定的面数k（2<=k<=8）,每一面对应的点数分别为1,2,.…,k。
小明有n（1<=n<=20）个骰子，对于骰子i（1<=i<=n），它的面数为a_i(2<=a_i<=8),摇到每一面的概率都是1/a_i。
小红有m（1<=m<=20）个骰子，对于骰子j（1<=j<=m），它的面数为bj(2<=bj<=8),摇到每一面的概率都是1/bj。
小明和小红分别摇各自拥有的全部骰子，然后把骰子朝上那一面的点数相加，最后比较谁的点数和最大，大的获胜，相同平手，小的获败。小明和小红只摇一把，平手不会继续重摇，小明想知道他获胜的概率，你能帮帮他吗？
输入n、m。然后输入n个骰子和m个骰子
输出获胜概率，保留小数点后3位
input: 1 3 8 2 3 4 output: 0.255
对于小明，维护一个数组A：A[i]代表小明获得i点的方案数。小红同理。那么假设小明获到i点，需要小红获取到1~i-1点才可以让小明获胜，利用维护的上面这个数组来计算获胜的方案数和总方案数。
如何计算这个数组？考虑还没有扔骰子的情况，那么只有一种方案，那就是什么都不扔，只能得到数字0，且方案数为1。那么开始扔第一个骰子，假设这个骰子有k个面，根据第一种方案，使用这个骰子可以获得1~k点，且每一种都是1种方案。
在扔第二个骰子的时候，假设这个骰子点数有k个面，在扔一个骰子的方案数的基础上。假设扔一个骰子可以获得i分，那么可以通过这个i分获取到：i+1、i+2、...、i+k分。以此类推。具体可以在代码中看。
本题代码没有过100%，只过了85%，如果大佬看出问题希望在评论区留言指正，感激不尽
n,m=list(map(int,input().split()))
a=list(map(int,input().split()))
b=list(map(int,input().split()))
ac=sum(a)
fa=[0]*(ac+1)
fa[0]=1
for i in a:
ga=[0]*(ac+1)
for j in range(ac+1):
if not fa[j]:continue
for k in range(1,i+1):
ga[j+k]+=fa[j]
fa=ga
bc=sum(b)
fb=[0]*(bc+1)
fb[0]=1
for i in b:
gb=[0]*(bc+1)
for j in range(bc+1):
if not fb[j]:continue
for k in range(1,i+1):
gb[j+k]+=fb[j]
fb=gb
can=0
j=0
cj=0
for i in range(ac+1):
while j<i and j<=bc:
cj+=fb[j]
j+=1
can+=fa[i]*cj
tot=sum(fa)*sum(fb)
print(round(can/tot,3))#字节跳动##字节笔试##字节##笔试##字节23秋招笔试太难了吧##原来字节劝退的只是我，罢了罢了#
投递美团等公司10个岗位 >
腾讯三面176人在聊