【9.12】网易2021校招笔试-算法工程师 题解

class TreeNode:
    def __init__(self, x):
        self.id = x
        self.left = None
        self.right = None

    def is_leaf(self):
        return self.left is None and self.right is None

    def two_children_are_leaves(self):
        return (self.left is not None
                and self.left.is_leaf()) and (self.right is not None
                                              and self.right.is_leaf())


line = input()
m, n = list(map(int, line.strip().split()))

# m 点数
# n 边数

# 点 id从1开始
nodes = [None] * (m + 1)
for i in range(1, m + 1):
    nodes[i] = TreeNode(i)

for i in range(n):
    # n条边
    line = input()
    line_split = line.strip().split()
    parent = int(line_split[0])
    left_or_right = line_split[1]
    child = int(line_split[2])
    if left_or_right == 'left':
        nodes[parent].left = nodes[child]
    else:
        nodes[parent].right = nodes[child]

cnt = 0
for i in range(1, m + 1):
    if nodes[i].two_children_are_leaves():
        cnt += 1

print(cnt)

第二题

def expand(left, right):
    global s
    global len_s
    while left >= 0 and right < len_s and s[left] == s[right]:
        left -= 1
        right += 1
    return left + 1, right - 1  # 计算长度


def solve():
    global s
    global len_s
    global cnt

    if len_s == 1:
        return 0
    if len_s == 2:
        if s[0] == s[1]:
            return 1
        else:
            return 0

    # 长度3以上
    for i in range(len_s):
        # 奇数
        odd_left, odd_right = expand(i, i)
        odd_cnt = (odd_right - odd_left) // 2
        # 偶数
        if i < len_s - 1:
            even_left, even_right = expand(i, i + 1)
            even_cnt = (even_right - even_left + 1) // 2
        else:
            even_cnt = 0

        cnt[i] = odd_cnt + even_cnt

    all_cnt = 0
    for i in range(len_s):
        all_cnt += cnt[i]

    return all_cnt


s = input()
len_s = len(s)
cnt = [0] * len_s

res = solve()
print(res)

第三题

def dfs(boy_id):
    for girl_id in girl_ids:
        if girl_id in boy_to_girl[boy_id] and (not girl_vis[girl_id]):
            girl_vis[girl_id] = True
            if girl_res[girl_id] is None || dfs(girl_res[girl_id]):
                girl_res[girl_id] = boy_id
                return True

    return False


line = input()
boy_ids = [int(_) for _ in line.strip().split()]
line = input()
girl_ids = [int(_) for _ in line.strip().split()]

n = int(input())

boy_to_girl = {}
for boy_id in boy_ids:
    boy_to_girl[boy_id] = []

girl_res = {}  # 保存这个女孩匹配的boy
for girl_id in girl_ids:
    girl_res[girl_id] = None  # None表未匹配

girl_vis = {}  # 表示是否已经被占用
for girl_id in girl_ids:
    girl_vis[girl_id] = False

for i in range(n):
    line = input()
    line_int = [int(_) for _ in line.strip().split()]
    tmp_boy_id = line_int[0]
    tmp_girl_id = line_int[1]
    boy_to_girl[tmp_boy_id].append(tmp_girl_id)

cnt = 0
for boy_id in boy_ids:
    for girl_id in girl_ids:
        girl_vis[girl_id] = False
    if dfs(boy_id):
        cnt += 1

print(cnt)