网易笔试

第一题

题目我直接照搬leetcode原题了（因为我真不记得笔试的题目了）

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = “()”

输出：true

示例 2：

输入：s = “()[]{}”

输出：true

示例 3：

输入：s = “(]”

输出：false

示例 4：

输入：s = “([])”

输出：true

提示：

• 1 <= s.length <= 104
• s 仅由括号 '()[]{}' 组成

思路

本质上这题是需要检查括号的匹配和顺序，由于括号符合“后进后出“原则，所以我们直接用“栈”去解决。

代码逻辑

1.初始化一个栈和括号映射，用空栈来存储左括号，定义字典将左括号与右括号进行映射。

2.遍历字符串，对输入字符串的每个字符进行处理，如果是左括号直接入栈，右括号查看栈顶的左括号是否与之匹配。

3.匹配检查，遇到右括号如果栈顶为空直接返回 False，如果不为空且匹配错误直接返回 False ，如果栈顶不为空且有匹配到直接返回 True。

4.最终验证，如果栈为空，返回 True 。如果栈不为空，则返回 False。

代码

def isValide(s):
    stack = []
    brackets = {'(':')', '[':']', '{':'}'}
    for char in s:
        if char in brackets.keys():
            stack.append(char)
        elif char in brackets.values():
            if not stack or brackets[stack.pop()]!= char:
                return False
    return not stack

def main():
    try:
        s = input().strip()
        result = isValide(s)
        print('true' if result else 'false')
    except EXception as e:
        print('false')
if __name__ == '__main__':
    main()

第二题

这题貌似没有原题，我大概描述一下。这题我只做出来83.33%，思路对的中间有什么我没考虑到的地方。

有一个游戏，通过两个按钮来控制东西在旗杆上的位置。从离起点高一米的位置开始，到达顶端则游戏完成。用 height 来表示高度，按钮1可以控制向上1米，按钮2可以控制当前高度翻倍。且按钮2至多只有x次使用机会。需要计算如果最少次数到达顶端完成游戏。

输入描述：

旗杆高度h，按钮2使用次数x。

样例1

输入：5 0

输出 4

说明：1 -> 2 -> 3 -> 4 -> 5 到达顶端

样例2

输入：10 2

输出：4

说明：1 -> 2 -> 4 -> 5 -> 10 到达顶端

思路

本质上是一个动态规划问题，需要在有限的操作内找到最优解。

首先定义一个二维的DP数组$dp[pos][used]$，pos表示当前高度，used表示已使用按钮2的次数。

我们将初始高度定义为1，且操作次数为0。

然后走两步：

按钮1：如果 pos + 1 <= h ，则可以进行改变状态，使用次数不变。

按钮2：如果 used < x 且 pos * 2 <= h，则可以改变状态。

且我们在每次改变状态时需要计算当前的状态和新状态的最小值。

代码逻辑

创建二维数组，初始化为无穷大以表示未到达。数组大小两个都需要 +1 以表示从 dp[1][0] 开始。

双重循环遍历以找到所有可能性，且pos需要从1开始到 h + 1。

如果当前状态为未被访问即无法从初始状态到达，则可以跳过后续步骤。

按钮1操作和按钮2操作分开计算。

最终如果不是无穷大返回结果否则返回 -1 。

代码

def solve(h, x):
    dp = [[float('inf')] * (x + 1) for _ in range(h + 1)]
    dp[1][0] = 0
    for pos in range(1, h + 1):
        for used in range(x + 1):
            if dp[pos][used] == float('inf'):
                continue
            if pos + 1 <= h:
                dp[pos + 1][used] = min(dp[pos + 1][used], dp[pos][used] + 1)
            if used < x and pos * 2 <= h:
                dp[pos * 2][used + 1] = min(dp[pos * 2][used + 1], dp[pos][used] + 1)
    result = min(dp[h])
    return result if result != float('inf') else -1
while True:
    try:
        h, x = map(int, input().split())
        print(solve(h, x))
    except:
        break

第三题

leetcode原题，二叉树中的最大路径和。

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给定一个二叉树的根节点 root ，返回其 最大路径和，即所有路径上节点值之和的最大值。

示例 1：

输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

示例 2：

输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

提示：

• 树中节点数目范围是 [1, 3 * 104]
• -1000 <= Node.val <= 1000

思路

需要找到二叉树中某条路径的最大和，由于不经过根节点可以选择是否包含子树，所以需要递归的方式处理每个节点同时追踪全局最大值。

递归定义需要走两步
当前路径和：当前节点值加上左右子树的单边路径和

单边路径和：当前节点加上左右子树中较大的单边路径和

边际条件：如果节点为空，返回0。如果根节点为空，返回0。

代码逻辑

TreeNode 类，定义二叉树节点（值、左右子节点）

build_tree：使用层次遍历将输入数组转换为二叉树，处理 null 为空节点，并转换字符串为整数，使用 try-expect 兼容不同输入格式保证健壮性。

maxPathSum(root) ：主函数，检查根节点是否为空，初始化 max_sum 为负无穷（最终输出）并调用递归函数 dfs 。

dfs(node) 递归计算按照前面的逻辑去计算，分别计算左右子树的单边路径和，为负置0。计算当前路径和并更新全局最大路径值，返回较大的子路径给上层节点。

最终，主程序需要加入 EOF 以保证代码的完整性。这里需要注意的是，如果最终输入我们直接用main函数来进行，代码的运行通过率为70%左右，具体原因可能是因为python的某些特性（具体原因我也不清楚，但是确实是加了这个就能过，能过就行！管那么多干啥！）

代码

class TreeNode:
    def __init(self, val = 0, left = None, right = None):
        self.val = val
        self.left = left
        self.right = right
def build_tree(values):
    if not values or values[0] == 'null':
        return None
    try:
        root = TreeNode(int(values[0]))
    except TypeError:
        root = TreeNode()
        root.val = int(values[0])
        root.left = None
        root.right = None
    queue = [root]
    i = 1
    while queue and i < len(values):
        node = queue.pop(0)
        if i < len(values) and values[i] != 'null':
            try:
                node.left = TreeNode(int(values[i]))
            except TypeError:
                node.left = TreeNode()
                node.left.val = int(values[i])
                node.left.left = None
                node.left.right = None
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] != 'null':
            try:
                node.right = TreeNode(int(values[i]))
            except TypeError:
                node.right = TreeNode()
                node.right.val = int(values[i])
                node.right.left = None
                node.right.right = None
            queue.append(node.right)
        i += 1
    return root
def maxPathSum(root):
    if not root:
        return 0
    max_sum = float('-inf')
    def dfs(node):
        nonlocal max_sum
        if not node:
            return 0
        left_gain = max(dfs(node.left), 0)
        right_gain = max(dfs(node.right), 0)
        current_path_sum = node.val + left_gain + right_gain
        max_sum = max(max_sum, current_path_sum)
        return node.val + max(left_gain, right_gain)
    dfs(root)
    return max_sum
while True:
    try:
        input_str = input().strip()
        values = input_str.split(',')
        root = build_tree(values)
        print(maxPathSum(root))
    except EOFError:
        break

第四题

题目依旧是leetcode原题，952按公因数计算最大组件大小

给定一个由不同正整数的组成的非空数组 nums ，考虑下面的图：

• 有 nums.length 个节点，按从 nums[0] 到 nums[nums.length - 1] 标记；
• 只有当 nums[i] 和 nums[j] 共用一个大于 1 的公因数时，nums[i] 和 nums[j]之间才有一条边。

返回 图中最大连通组件的大小 。

示例 1：

输入：nums = [4,6,15,35]
输出：4

示例 2：

输入：nums = [20,50,9,63]
输出：2

示例 3：

输入：nums = [2,3,6,7,4,12,21,39]
输出：8

提示：

• 1 <= nums.length <= 2 * 104
• 1 <= nums[i] <= 105
• nums 中所有值都 不同

思路

核心思路是识别数字之间的公共因子关系，并将它们分组为连通组件。由于数字可能通过因子简洁连接，使用并查集就好。

因子分解与连接：对数组中的每个数字，分解出它的因子。将数字与其因子在并查集中合并，以表示它们属于同一组件。

并查集实现：使用路径压缩的 find 函数查找每个元素的根节点。使用按秩合并的 merge 函数连接两个元素，优化并查集效率。

统计组件大小：遍历数组，将每个数字映射到其所在组件的根节点。使用 Counter 统计每个根节点代表的组件大小，取最大值。

边界条件：当数组为空，返回0.

代码逻辑

find 函数：实现路径压缩的查找，递归找到根节点并将路径上的节点直接指向根。

merge 函数：按秩合并两个元素，先初始化为出现的元素，再根据秩决定合并方向。

largestComponentSize 函数：检查空数组，初始化 parent 和 rank 。对每个 num ，从2到√num枚举因子 i ，如果 num%i == 0，合并 num 与 i 和 num//i。用 Counter 计算每个根节点代表的组件大小，返回最大值。

考场代码

from collections import Counter
import sys
def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])
    return parent[x]
def merge(parent, rank, x, y):
    if x not in parent:
        parent[x] = x
        rank[x] = 0
    if y not in parent:
        parent[y] = y
        rank[y] = 0
    x = find(parent, x)
    y = find(parent, y)
    if x == y:
        return
    if rank[x] > rank[y]:
        parent[y] = x
    elif rank[x] < rank[y]:
        parent[x] = y
    else:
        parent[y] = x
        rank[x] += 1
def largestComponentSize(nums):
    if not nums:
        return 0
    parent = {}
    rank = {}
    for num in nums:
        if num not in parent:
            parent[num] = num
            rank[num] = 0
        i = 2
        while i * i <= num:
            if num % i == 0:
                factor = i
                if factor not in parent:
                    parent[factor] = factor
                    rank[factor] = 0
                merge(parent, rank, num, factor)
                factor = num // i
                if factor not in parent:
                    parent[factor] = factor
                    rank[factor] = 0
                merge(parent, rank, num, factor)
            i += 1
    counter = Counter(find(parent, num) for num in nums)
    return max(counter.values())
def main():
    input_data = sys.stdin.read().split()
    n = int(input_data[0])
    nums = list(map(int, input_data[1 : n + 1]))
    result = largestComponentSize(nums)
    print(result)
if __name__ == '__main__':
    main()

问题与正确代码

实际上当时考场上我这题通过率只有13.33%，也因为时间不够没办法进行修改，后续进行查找后发现是 因子分解不完整。当时漏掉了大于 √num 的因子（自身或最后一个商），导致某些情况下组件连接不全。

所以我们需要在因子分解后，显式检查 num 是否还有剩余因子 （即 num 本身可能是质数或大于 √num 的因子），并将其与自身初始化或合并。确保每个 num 至少与自己的一个因子（包括自身）连接。

修改后的代码如下：

from collections import Counter
import sys

def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])
    return parent[x]

def merge(parent, rank, x, y):
    if x not in parent:
        parent[x] = x
        rank[x] = 0
    if y not in parent:
        parent[y] = y
        rank[y] = 0
    x = find(parent, x)
    y = find(parent, y)
    if x == y:
        return
    if rank[x] > rank[y]:
        parent[y] = x
    elif rank[x] < rank[y]:
        parent[x] = y
    else:
        parent[y] = x
        rank[x] += 1

def largestComponentSize(nums):
    if not nums:
        return 0
    parent = {}
    rank = {}
    for num in nums:
        if num not in parent:
            parent[num] = num
            rank[num] = 0
        i = 2
        temp = num
        while i * i <= temp:  # 使用 temp 避免修改 num
            if temp % i == 0:
                factor = i
                merge(parent, rank, num, factor)
                while temp % i == 0:  # 除尽 i
                    temp //= i
            i += 1
        if temp > 1:  # 处理剩余因子（质数或大于 √num）
            merge(parent, rank, num, temp)
    counter = Counter(find(parent, num) for num in nums)
    return max(counter.values())

def main():
    input_data = sys.stdin.read().split()
    n = int(input_data[0])
    nums = list(map(int, input_data[1 : n + 1]))
    result = largestComponentSize(nums)
    print(result)

if __name__ == '__main__':
    main()

具体修改点：

​ 因子分解优化：

​ 使用 temp 代替 num，逐步除去因子 i，直到无法整除。

​ 循环结束后，若 temp > 1，说明剩余一个大于 √num 的因子或质数，合并 num 和 temp。

​ 移除冗余合并：

​ 原代码中每次找到因子 i 就合并 num 和 i 以及 num // i，可能重复合并。修改后只合并必要的因子。