网易互联网笔试统计和题目讨论

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

第二题

给一个字符串，里面都是小写字母，如果一个字母可以被标记（标记条件为隔壁字母和它相邻，相邻的意思就是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])