自娱自乐的精神乐园

余凯迪的博客

0%

leetcode_124_contest

发表于 更新于 分类于 ， 阅读次数：

993. 二叉树的堂兄弟节点

思路

本题的思路较为简单。比较是否为堂兄弟节点，根据定义关键有两点

  1. 深度相同
  2. 父节点不同

因此分别得到两个节点的深度和父节点，此题就能解答。

代码

代码为Python版本，python的函数可以有多个返回值（实际上作为一个tuple返回），便于编程和理解。

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    """
    获取节点的深度和父节点，深度优先搜索
    """
    def dfs(self, root: 'TreeNode', x: 'int', depth: 'int'):
        if root is None:
            return None
        if root.left and root.left.val == x:
            return depth + 1, root
        if root.right and root.right.val == x:
            return depth + 1, root
        left_res = self.dfs(root.left, x, depth + 1)
        if left_res:
            return left_res
        right_res = self.dfs(root.right, x, depth + 1)
        if right_res:
            return right_res   
    
    def isCousins(self, root: 'TreeNode', x: 'int', y: 'int') -> 'bool':
        # 获取节点深度信息和其父节点
        x_info = self.dfs(root, x, 0)
        y_info = self.dfs(root, y, 0)
        if x_info is None or y_info is None:
            return False
        if x_info[0] == y_info[0] and x_info[1] != y_info[1]:
            return True
        return False

994. 腐烂的橘子

思路

本题模拟题目中描述的过程即可以作答。
连续两次数组信息没有发生改变，即可认为达到了最终状态。
使用两个变量分别记录本轮新鲜橘子的个数和上一轮新鲜橘子的个数，前后不发生变化，则过程模拟即可退出。

代码

prev_fresh记录上一轮新鲜橘子个数
fresh记录本轮新鲜橘子的个数
本轮腐烂的橘子到下一轮进行统计，导致最后的结果需要-1

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
class Solution:
    def orangesRotting(self, grid: 'List[List[int]]') -> 'int':
        prev_fresh = -1
        minute = 0
        # 该函数对坐标为(r,c)相邻位置的橘子进行腐烂操作
        def infect(r,c):
            if r-1 >= 0 and grid[r-1][c] == 1:
                grid[r-1][c] = 2
            if r+1 <len(grid) and grid[r+1][c] == 1:
                grid[r+1][c] = 2
            if c-1 >= 0 and grid[r][c-1] == 1:
                grid[r][c-1] = 2
            if c+1 <len(grid[0]) and grid[r][c+1] == 1:
                grid[r][c+1] = 2
        
        while(1):
            fresh = 0
            rot = 0
            rot_corr = []
            for row in range(len(grid)):
                for col in range(len(grid[0])):
                    if grid[row][col] == 1:
                        fresh += 1
                    if grid[row][col] == 2:
                        rot += 1
                        rot_corr.append([row,col])
            for x in rot_corr:
                infect(x[0],x[1])
            
            if (fresh == prev_fresh):
                break
            minute += 1
            prev_fresh = fresh
            prev_rot = rot
            
        if fresh == 0:
            return minute - 1
        return -1

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

思路

对于每一个位置，两次翻转即还原。x与0异或保持原值，x以1异或得到1-x
如果K=1，要将每一个位置都置1，最朴素的想法就是从前往后遍历0，遇到0则进行翻转。那么对于K>1，我们同样对出现的0进行翻转操作，但是需要记录下翻转的终点，便于我们恢复。
如果走到最后，对于前面length-K位都为1，但是由于前面的操作导致末尾的K位中包含1，这就表明了不可能实现。

代码

使用一个辅助List，记录翻转操作的终点。
ls变量记录是否处于翻转阶段，第i为0时，意味着A[i:i+k]需要翻转（注意python语法，index是i到i+k-1），rev在结束位置后记上标记。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def minKBitFlips(self, A: 'List[int]', K: 'int') -> 'int':
        rev = [0]*(len(A)+10)
        ls = 0
        ans = 0
        for i in range(len(A)):
            ls ^= rev[i]# 主要是用来判断该位置需不需要翻转
            A[i] ^= ls  #该位置之前多次操作最后的结果
            if A[i] == 0:
                ans += 1
                ls ^= 1 #flag翻转一下
                if i+K > len(A):
                    return -1
                rev[i+K] = 1 # 标记翻转的结束位置
        return ans

996. 正方形数组的数目

思路

通过递归实现深度优先搜索。
该过程类似每次挑选出一个数字，与已经是正方形数组的子数组最后一个数字，判断能否扩充子数组，直到成为原数组的一个排列。
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
import copy
import math
class Solution:
    def isSqr(self,num):
        return int(math.sqrt(num))**2 == num

    def dfs(self, A, b):
        if len(A) == 0:
            return 1
        ans = 0
        for i in range(len(A)):
            if i==0 or A[i] != A[i-1]:
                if not self.isSqr(A[i]+b):
                    continue
                B = copy.deepcopy(A)
                B.remove(B[i])
                ans += self.dfs(B, A[i])
        return ans

    def numSquarefulPerms(self, A: 'List[int]') -> 'int':
        ans = 0
        A.sort() # 排序的原因是为了在搜索时避免重复查找
        for i in range(len(A)):
            if i==0 or A[i] != A[i-1]:
                B = copy.deepcopy(A)
                B.remove(B[i])
                ans += self.dfs(B, A[i])
        return ans