首页 > 网易笔试 9.12 AK
头像
milestian
编辑于 2020-09-12 20:56
+ 关注

网易笔试 9.12 AK

比较简单吧, 还以为平均AK, 想了很久问答题
1,二叉树, 求节点的两个子节点为叶子节点
m, n  = list(map(int, input().split()))
nodes = [None]*(m+1)
class Node:
    def __init__(self, id):
        self.left = None
        self.right = None
        self.id = id

for x in range(n):
    line = input().split()
    id = int(line[0])
    direction = line[1]
    child = int(line[2])
    if not nodes[id]:
        idNode = Node(id)
        nodes[id] = idNode
    if not nodes[child]:
        nodes[child] = Node(child)
    idNode = nodes[id]
    childNode = nodes[child]
    if direction=="left":
        idNode.left = childNode
    else:
        idNode.right = childNode
heights = [-1]*(m+1)
def dfs(node):
    global heights
    if node==None:
        return 0
    elif heights[node.id]>=0:
        return heights[node.id]
    else:
        height = max(dfs(node.left), dfs(node.right))+1
        heights[node.id] = height
        return height
result = 0
for x in range(1, m+1):
    if heights[x]<0:
        dfs(nodes[x])

for x in range(1,m+1):
    node = nodes[x]
    if node and node.left and node.right and heights[node.left.id]==1 and heights[node.right.id]==1:
        result += 1
print(result)

2, 回文子串数目
看到字符串长度为100000当场崩溃,以为manacher
结果暴力成功了。。。。。。🤣🤣🤣
string = input()
length = len(string)
dp = [[False]*length for x in range(length)]
result = 0
for x in range(length-1,-1,-1):
    for y in range(length):
        if x>y:
            dp[x][y] = True
        elif x==y:
            dp[x][y] = True
        else:
            if string[x]==string[y]:
                dp[x][y] = dp[x+1][y-1]
                if dp[x][y]:
                    result += 1
            else:
                dp[x][y] = False
print(result)
3, 满足字符为偶数,还是暴力,关键在于用6个bit存储状态,1表示是偶数,所以用前缀和,然后o(n^2)暴力所有连续子串就Ok
preSum = [2**6-1]
mem = {'a':0, 'b':1, 'c':2, 'x':3, 'y':4, 'z':5}
s = input()
for ch in s:
    if ch not in mem:
        preSum.append(preSum[-1])
        continue
    prev = preSum[-1]
    prev = prev ^ (1<<mem[ch])
    preSum.append(prev)
result = 0
for x in range(len(s)+1):
    for y in range(len(s),x-1,-1):
        if preSum[y]==63:
            result = max(result, y)
        else:
            if preSum[x]==preSum[y]:
                result = max(result, y-x)
print(result)
4, 还是暴力, 就0,1背包思路。
nums = list(map(int, input().split()))

maxVal = 0

def dfs(curVal, leftVal, leftIndex):
    global maxVal
    if maxVal >= (curVal + leftVal):
        return
    else:
        if curVal%7==0:
            maxVal = max(curVal, maxVal)
        if leftIndex<len(nums):
            popOne = nums[leftIndex]
            leftVal -= popOne
            dfs(curVal+popOne, leftVal, leftIndex+1)
            dfs(curVal, leftVal, leftIndex+1)
dfs(0, sum(nums), 0)
if maxVal:
    print(maxVal)
else:
    print(-1)

全部评论

(1) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐