讨论/题目交流/🐱 第 14 场夜喵双周赛/
🐱 第 14 场夜喵双周赛

欢迎在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 十六进制魔术数字
5 分 - 删除区间
5 分 - 删除树节点
7 分 - 矩形内船只的数目

这次是用python打的比赛,python不怎么熟悉,大家将就着看下

第一题:

没啥难度,转成十六进制后该干嘛干嘛

class Solution:
    def toHexspeak(self, num: str) -> str:
        s = hex(int(num))[2:].upper()
        def change(c):
            if c == '0':
                return 'O'
            elif c == '1':
                return 'I'
            else:
                return c
        if len(list(filter(lambda c: c not in 'ABCDEF01', s))) != 0:
            return "ERROR"
        return "".join(list(map(lambda c: change(c), s)))

第二题:

主要难度在枚举两个区间的所有相交情况

  • A和B相离
  • A在B里
  • B在A里
  • A盖住了B的左边部分
  • A盖住了B的右边部分
class Solution:
    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:
        def cross(a, b):
            if a[0] >= b[1] or a[1] <= b[0]:
                return [a]
            elif a[0] >= b[0] and a[1] <= b[1]:
                return []
            elif a[0] >= b[0] and a[1] > b[1]:
                return [[b[1], a[1]]]
            elif a[0] < b[0] and a[1] <= b[1]:
                return [[a[0], b[0]]]
            else:
                return [[a[0], b[0]], [b[1], a[1]]]
            
        ret = []
        for x in intervals:
            ret += cross(x, toBeRemoved)
        return ret

第三题:

两遍dfs,
第一遍dfs,统计出每个结点为根的子树和
第二遍dfs,统计删除子树和为0的结点,子树和为0的结点就不进行dfs了

注意,需要提前建立邻接表,否则会超时

class Solution:
    def deleteTreeNodes(self, nodes: int, parent: List[int], value: List[int]) -> int:
        children = list(map(lambda c: [], range(0, nodes)))
        for i in range(1, nodes):
            children[parent[i]].append(i)
        num_sub = [0] * nodes
        def dfs1(node):
            num_sub[node] += value[node]
            for child in children[node]:
                num_sub[node] += dfs1(child)
            return num_sub[node]
        dfs1(0)
        def dfs2(node):
            if num_sub[node] == 0:
                return 0
            ret = 1
            for child in children[node]:
                ret += dfs2(child)
            return ret
        return dfs2(0)

第四题:

二分,矩阵的二分,划成了4个小矩阵,分别对这4个小矩阵进行探测,如果没有船,就不继续探测了,如果有船,那么递归探测

递归的终止条件是:矩阵只剩下一个点,那么这个点就有一艘船

class Solution(object):
    def countShips(self, sea: 'Sea', topRight: 'Point', bottomLeft: 'Point') -> int:
        def find(bottomLeft, topRight):
            if not sea.hasShips(topRight, bottomLeft):
                return 0
            
            if bottomLeft.x == topRight.x and bottomLeft.y == topRight.y:
                return 1
            
            sub = []
            mid_x = (bottomLeft.x + topRight.x) // 2
            mid_y = (bottomLeft.y + topRight.y) // 2
            if bottomLeft.x == topRight.x:
                sub = [[bottomLeft, Point(mid_x, mid_y)], [Point(mid_x, mid_y + 1), topRight]]
            elif bottomLeft.y == topRight.y:
                sub = [[bottomLeft, Point(mid_x, mid_y)], [Point(mid_x + 1, mid_y), topRight]]
            else:
                sub = [[bottomLeft, Point(mid_x, mid_y)], [Point(bottomLeft.x, mid_y + 1), Point(mid_x, topRight.y)], [Point(mid_x + 1, bottomLeft.y), Point(topRight.x, mid_y)], [Point(mid_x + 1, mid_y + 1), topRight]]
            
            ret = 0
            for x in sub:
                ret += find(x[0], x[1])
            return ret
            
        return find(bottomLeft, topRight)
11
展开全部 8 讨论