Leetcode第 124 场周赛

周赛链接

993. 二叉树的堂兄弟节点

题目链接
可以通过深度优先遍历给定二叉树,如果某节点的孩子节点的值与所给值相同,则返回当前高度以及该父节点。最后判断给定的x和y对应的节点是否深度相同且父节点不同即可。
Python代码:

class Solution:
    def isCousins(self, root: 'TreeNode', x: 'int', y: 'int') -> 'bool':
        def helper(node, depth, val):
            if node is None:
                return
            if node.left and node.left.val == val:
                return [node, depth + 1]
            if node.right and node.right.val == val:
                return [node, depth + 1]
            left = helper(node.left, depth+1,val)
            if left:
                return left
            right = helper(node.right, depth+1,val)
            if right:
                return right
        l = helper(root,0,x)
        r = helper(root,0,y)
        if l and r and l[0] != r[0] and l[1] == r[1]:
            return True
        return False

994. 腐烂的橘子

题目链接
这是一道典型的bfs的问题,记录下一开始新鲜橘子的数量,然后对网格进行宽度优先遍历,每一轮把腐烂橘子四周的新鲜橘子改为腐烂并将其加入队列即可。最后通过比较从新鲜修改为腐烂橘子的数量与最初新鲜橘子的数量即可判断是否还剩有新鲜橘子。
Python代码:

class Solution:
    def orangesRotting(self, grid: 'List[List[int]]') -> 'int':
        m = len(grid)
        n = len(grid[0])
        queue = []
        count = 0
        res = 0
        directions = ((-1,0),(0,-1),(1,0),(0,1))
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    count += 1
                elif grid[i][j] == 2:
                    queue.append((i,j))
        while len(queue) > 0 and count > 0:
            res += 1
            size = len(queue)
            for i in range(size):
                element = queue.pop(0)
                row = element[0]
                col = element[1]
                for direction in directions:   
                    temp_row = row + direction[0]
                    temp_col = col + direction[1]
                    if m > temp_row and temp_row >= 0 and n > temp_col and temp_col >= 0  and grid[temp_row][temp_col] == 1:
                        grid[temp_row][temp_col] = 2
                        count -= 1
                        queue.append((temp_row,temp_col))
        return res if count == 0 else -1

995. K 连续位的最小翻转次数

题目链接
这是一道翻转问题(开关问题),问题分析可见https://blog.csdn.net/ac_hell/article/details/51077320。我们遍历数组A,并通过一个变量pre保存当前遍历到的数前面K-1个数的翻转情况,通过pre我们就可以知道该位置现在的值。当遍历到末尾的K-1个数时,如果还包含0,则返回-1,否则返回翻转次数。
Python代码:

class Solution:
    def minKBitFlips(self, A: 'List[int]', K: 'int') -> 'int':
        l = len(A)
        cur = 0
        res = 0
        f = [0] * l
        pre = 0
        while cur < l:
            if (A[cur] + pre) & 1 == 0:
                if cur > l - K:
                    return -1
                pre += 1
                f[cur] = 1
                res += 1
            if cur - K + 1 >= 0:
                pre -= f[cur - K + 1]
            cur += 1
        return res

996. 正方形数组的数目

题目链接
由于提示数组A并不长,所以我们可以先遍历数组A,统计每一个数出现的次数,并且建立一个无向图,如果数组中的两个数之和是完全平方数,则在两点间连一条边。然后我们可以通过回溯算法来构造正方形数组并得到正方形数组的数量。由于构造数组时数组的第一个数不重复,也就避免了出现重复数组的情况。
Python代码:

class Solution:
    def numSquarefulPerms(self, A: 'List[int]') -> 'int':
        def helper(pre, subl):
            nonlocal l,res,counter,d
            if subl == l:
                res += 1
                return
            for a in d.get(pre,[]):
                if counter[a] > 0:
                    counter[a] -= 1
                    helper(a, subl+1)
                    counter[a] += 1
        l = len(A)
        res = 0
        d = {}
        counter = collections.Counter(A)
        for i in range(l):
            for j in range(i+1,l):
                temp = A[i] + A[j]
                st = int(math.sqrt(temp))
                if st ** 2 == temp:
                    if d.get(A[i]) is None:
                        d[A[i]] = set()
                    d.get(A[i]).add(A[j])
                    if d.get(A[j]) is None:
                        d[A[j]] = set()
                    d.get(A[j]).add(A[i])
        for k in counter.keys():
            counter[k] -= 1
            helper(k, 1)
            counter[k] += 1
        return res