原卷地址:
https://www.nowcoder.com/test/39959332/summary

T1:

比较基础的一题 只需要知道只有2的幂对应二进制肯定只有一个1即可

1
2
3
class Solution:
    def minCnt(self , s: str) -> int:
        return s.count("1") - 1

T2:

贪心+二分
先对数组进行排序
每次将最后一个数即最大的数减去x 然后再通过二分寻找该数减去x后的合适位置 并将其放入
排序是nlogn 二分 klogn
总复杂度 (n+k)logn

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from typing import List
from bisect import bisect_left


class Solution:
    def minMax(self, a: List[int], k: int, x: int) -> int:
        a.sort()
        r = len(a) - 1
        while k:
            k = k - 1
            a[r] = a[r] - x
            l = bisect_left(a, a[r])
            a.insert(l,a[r])
            a.pop()
        return a[r]

T3

这种求连续最大长度的题 可考虑使用dp
应该是全场最难的一题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
MOD = 10**6
class Solution:
    """
    dp[i][j] 表示长度为i 可分为j段的子串个数
    对当前加入字符串的字母
    如果当前字母与之前的字母可以构成连续串
        dp[i][j] = dp[i-1][j]
        因为根据定义尾部至少有两个字母相等了 再加上尾部的这个仍然还是相等
    如果当前字母不能与之前的字母构成连续串
        dp[i][j] = 25 * dp[i-2][j-1]
        还是因为定义 连续子串至少要有2个字母构成 不能与尾部的两个字符构成连续串 那就只能与i-2的字母构成 这样的选择除了尾部的字符种类还有25种
    """
    def numsOfStrings(self , n: int, k: int) -> int:
        dp = [[0 for i in range(k+10)] for _ in range(n + 10)]

        for i in range(2,n+1):
            # 长度为2 以上串 符合连续串的条件
            # 全部组成一段的方案数有26种
            dp[i][1] = 26
        
        # 第1段已经赋了初值
        # 第2段长度4开始 已经2 + 2才可能存在两段
        for i in range(4,n+1):
            for j in range(2,k+1):
                dp[i][j] = (dp[i-1][j] + 25 * dp[i-2][j-1])%MOD
        
        return dp[n][k]

T4

BFS层序遍历的基础上 判断根据上下两层是否需要删除的情况进行操作
因为是要根据上下两层进行操作所以对于第0层要进行一个特判 即将0层算入要删除的层 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
from collections import *
class Solution:
    """
    1.先将所有需要删除的层加入set中
    2.BFS:
        如果当前层上一层为要删除层 且当前层不需要删除 则将该节点加入答案
        将该节点的左右节点加入队列
        若当前节点的下一层需要删除 则断开当前节点与其左右节点的连接

    特判: 将第0层也加入队列视作要删除层 因为可能第一层也是要删除的
    """

    def deleteLevel(self, root: TreeNode, a: List[int]) -> List[TreeNode]:
        s = set()
        # 将所有要删除的层 加入set 便于后续的判断
        for d in a:
            s.add(d)
        # 特判 将0层作为删除层
        s.add(0)
        q = deque()
        q.append(root)
        d = 0
        ans = []
        while q:
            d = d + 1
            w = len(q)
            for _ in range(w):
                node = q.popleft()
                # 如果上一层为要删除的 而该层不需要删除 那么该层节点为新的独立子树 加入ans中
                if d - 1 in s and d not in s:
                    ans.append(node)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
                # 如果下一层是需要删除 则断开当前节点与其左右子节点的联系
                if d + 1 in s:
                    node.left =None
                    node.right = None

        return ans

T5

这题关键在于明白异或的运算结果与运算顺序无关
故可以先求父节点的运算结果然后再通过dfs向其子树进行传递

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 返回值的树节点中val表示节点权值
# @param root TreeNode类 给定的初始树节点中的val表示节点编号
# @param op int整型二维数组 op的组成为[[id,v],[id,v],[id,v],...]
# @return TreeNode类
#

from collections import *
class Solution:
    """
    异或运算的先后顺序不影响结果
    所以可以对某节点先执行完所有异或操作后 再通过dfs将结果传递给其所有子树
    """

    def xorTree(self, root: TreeNode, op: List[List[int]]) -> TreeNode:
        h = defaultdict(int)
        for id, v in op:
            h[id] ^= v

        def dfs(node: TreeNode, fa: int):
            if not node:
                return
            # 有进行过异或操作则直接赋值 否则默认为0
            node.val = h[node.val]
            node.val^=fa

            dfs(node.left, node.val)
            dfs(node.right, node.val)

        dfs(root, 0)

        return root

T6#

非常基础的一题 比第一题还简单不知道为啥放到最后

1
2
3
4
5
6
7
8
9
10

class Solution:
    def howMany(self , S: str, k: int) -> int:
        ans = 0
        for i in range(26):
            ch = chr(i+97)
            if S.count(ch) >= k:
                ans = ans + 1
        return ans
        # write code here

总结

由于这张卷只写了编程题合集所以我也不知道这些是笔试还是把面试都算进去了
但总的来说难度不算大 2345 大概是leetcode mid的程度
另外牛客上的提交与力扣有些不一样 defaultdict这些比较常用都需要手动导入 牛客是不会导入collections集合这点要注意一下 不过牛客没有频繁提交次数限制还是蛮不错的