网易互联网笔试统计和题目讨论
2022.3.27
第一题
两个怪物，一个a血，一个b血。
两个技能，一个单体x血，一个群体y血。
求最少需要放几次技能才能干掉怪物。
a,b,x,y 均小于20，大于0
直接暴力搜索+记忆化 a了
a,b,x,y = map(int,input().split(" "))
# print(a,b,type(x))
data= dict()
def dfs(a,b):
if a<=0 and b<=0:
return 0
if (a,b) in data:
return data[(a,b)]
# 火杀a
one,two = 1000,1000
if a>0:
one = dfs(a-x,b)+1
if b>0:
two = dfs(a,b-x)+1
three = dfs(a-y,b-y)+1
data[(a,b)]= min(one,two,three)
return min(one,two,three)
print(dfs(a,b)) 样例：
5 2 3 1
3
3
第二题
给一个字符串，里面都是小写字母，如果一个字母可以被标记（标记条件为隔壁字母和它相邻，相邻的意思就是b和a是相邻的，b和c是相邻的），那么就可以标记它和它隔壁的字母，获取它和隔壁的分数（a为1分，b为2分，以此类推），一个字母只能被标记一次。求最高分数。
输入：abb
输出：4
只A了一半，在评论区蹲大佬解答def fen(a,b):
if a==b:
return (ord(a)-ord("a")+1)*2
elif abs(ord(a)-ord(b))==1:
return ord(a)-ord("a")+2+ord(b)-ord("a")
else:
return 0
def solve():
# print(fen("y","z"))
s = input()
n = len(s)
if n<2:
print("0")
return
data = [[0 for i in range(3)] for j in range(n+1)]
ans = 0
for i in range(2,n+1):
j = i-1
if s[j]==s[j-1]:
jia = fen(s[j],s[j-1])
data[i][0] = max(data[i-2][0],data[i-2][1],data[i-2][2])+jia
elif abs(ord(s[j])-ord(s[j-1]))==1:
jia = fen(s[j],s[j-1])
data[i][1] = max(data[i-2][0],data[i-2][1],data[i-2][2])+jia
else:
# 无法标注
data[i][2] = max(data[i-1][0],data[i-1][1],data[i-1][2],data[i-2][0],data[i-2][1],data[i-2][2])
ans = max(ans,data[i][0],data[i][1],data[i][2])
print(ans)
solve() 每一个位置分3中情况：相同、或者相邻、或者无法标注
第三题
生成一个二叉树，输出其层序遍历，要求：
-
一共n个节点，包含1~n。
-
除了根节点，每个节点和其父节点的乘积为偶数。
输入：4
输出：2 4 1 3
答案不唯一，输出一种即可
因为是完全二叉树，考虑数组存储，则数组下标1~n顺序输出就是层次遍历
能过90%+的样例，显示超时
n = int(input()) tree = [0]*(n+1) flag = [False]*(n+1) def pan(cur,i): if cur==1: return True fu = cur//2 while fu>0: val = i*tree[fu] if val %2==1: return False fu = fu//2 return True def dfs(cur): if cur>n: ans = "" for i in range(1,n+1): ans +=str(tree[i])+" " print(ans) return True for i in range(1,n+1): if flag[i]: continue if pan(cur,i)==False: continue tree[cur] = i flag[i] = True if dfs(cur+1): return flag[i] = False tree[cur] = 0 return False dfs(1)
第四题
在沼泽地中移动，1代表沼泽，0代表平地。
在相同的地方里移动消耗1，否则消耗2。
求从0，0处到n-1,m-1处最少消耗多少。
输入：3 3
1 0 0
1 1 1
0 0 1
输出：4
只考虑向右向下的情况可以过90%+的样例
# 444444
n,m = map(int,input().split(" "))
data = []
for i in range(n):
data.append(list(map(int,input().split(" "))))
# print(data)
val = [[0 for j in range(m) ] for i in range(n)]
for i in range(1,n):
tmp = abs(data[i][0]-data[i-1][0])
if tmp==0:
val[i][0] = val[i-1][0]+1
elif tmp==1:
val[i][0] = val[i-1][0]+2
for j in range(1,m):
tmp = abs(data[0][j]-data[0][j-1])
if tmp==0:
val[0][j] = val[0][j-1]+1
elif tmp==1:
val[0][j] = val[0][j-1]+2
for i in range(1,n):
for j in range(1,m):
# 向右
you =abs( data[i][j-1]- data[i][j])+1
# 向下
xia = abs(data[i-1][j]-data[i][j])+1
# # 向左
# zuo = float("inf")
# if j+1<m:
# zuo = abs(data[i][j]-data[i][j+1])
# zuo+=val[i][j+1]
val[i][j] = min(val[i][j-1]+you, val[i-1][j]+xia)
print(val[n-1][m-1])
投递达能等公司7个岗位 >