PeterQwQ
0%

发表于

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵
平衡 二叉搜索树。

平衡 二叉搜索树：任意节点的两棵子树的高度差不超过 1 而且左子树中所有节点的值 < 根节点的值；右子树中所有节点的值 > 根节点的值；其左、右子树也分别为二叉搜索树。

既然题目里面已经给出了升序排列的数组，那么我们可以直接取中间的元素作为根节点，然后递归的构建左右子树即可。这样能够保证高度差不超过1。同时，由于数组是升序的，所以左子树的元素一定比根节点小，右子树的元素一定比根节点大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        def construct_tree(left, right):
            if left > right:
                return None
            mid = (left + right) // 2
            root = TreeNode(nums[mid])
            root.left = construct_tree(left, mid-1)
            root.right = construct_tree(mid+1, right)
            return root
        return construct_tree(0, len(nums)-1)

发表于

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

就是BFS，用队列存储每一层的节点，然后遍历队列，每次遍历一层，然后将下一层的节点加入队列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        queue, cur_level_ans,ans = [root], [], []
        while queue:
            tmp = []
            for node in queue:                
                if node.left:
                    tmp.append(node.left)
                if node.right:
                    tmp.append(node.right)           
                cur_level_ans.append(node.val)
            queue = tmp
            ans.append(cur_level_ans)
            cur_level_ans = []
        return ans

发表于

给你一棵二叉树的根节点，返回该树的 直径 。

二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。两节点之间路径的 长度 由它们之间边数表示。

对于一个节点而言，它的直径等于左子树的深度加上右子树的深度。因此，我们可以递归地求出每个节点的直径，取最大值即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.ans = 0
        def depth(node):
            if not node:
                return 0
            left_depth = depth(node.left)
            right_depth = depth(node.right)
            self.ans =  max(left_depth+right_depth+1, self.ans) 
            return max(left_depth, right_depth) + 1

        depth(root)
        return self.ans - 1

发表于

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。 回文字符串 是正着读和倒过来读一样的字符串。 子字符串 是字符串中的由连续字符组成的一个序列。

对于一个字符串的每个位置，都可以是一个回文串的中心点。因此我们可以遍历每一个位置，以这个位置为中心，向两边扩展，直到不是回文串为止。这样就可以求出以当前位置为中心的回文串的个数。

需要注意的就是，中心点可能是一个字符，也可能是两个字符。因此我们需要分别处理这两种情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def countSubstrings(self, s: str) -> int:
        n, ans = len(s), 0
        for i in range(n):
            ans += self.check(i, i, s)
            ans += self.check(i, i+1, s)
        return ans
           
    def check(self, left, right, s):
        ans = 0
        while left >= 0 and right <= len(s)-1 and s[left] == s[right]:
            ans += 1
            left -= 1
            right += 1
        return ans

发表于

给你一个整数数组 colors 和一个整数 k ， colors 表示一个由红色和蓝色瓷砖组成的环，第 i 块瓷砖的颜色为 colors[i] ：

  • colors[i] == 0 表示第 i 块瓷砖的颜色是 红色 。
  • colors[i] == 1 表示第 i 块瓷砖的颜色是 蓝色 。

环中连续 k 块瓷砖的颜色如果是 交替 颜色（也就是说除了第一块和最后一块瓷砖以外，中间瓷砖的颜色与它 左边 和 右边 的颜色都不同），那么它被称为一个 交替 组。

请你返回 交替 组的数目。注意 ，由于 colors 表示一个 环 ， 第一块 瓷砖和 最后一块 瓷砖是相邻的。

由于整体上是一个环，所以需要拓展到 n+k-2 的长度，然后遍历，如果当前颜色与下一个颜色不同，那么计数器加一，如果计数器等于 k，那么结果加一，然后计数器减一，继续遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def numberOfAlternatingGroups(self, colors: List[int], k: int) -> int:
        n = len(colors)
        cnt, res = 1, 0
        for i in range(n+k-2):
            if colors[i%n] != colors[(i+1)%n]:
                cnt += 1
                if cnt == k:
                    res += 1
                    cnt -= 1
                    continue
            else:
                cnt = 1
        return res

发表于

给你一个整数数组 colors ，它表示一个由红色和蓝色瓷砖组成的环，第 i 块瓷砖的颜色为 colors[i] ：

  • colors[i] == 0 表示第 i 块瓷砖的颜色是 红色 。
  • colors[i] == 1 表示第 i 块瓷砖的颜色是 蓝色 。

环中连续 3 块瓷砖的颜色如果是 交替 颜色（也就是说中间瓷砖的颜色与它 左边 和 右边 的颜色都不同），那么它被称为一个 交替 组。

请你返回 交替 组的数目。注意 ，由于 colors 表示一个 环 ，第一块 瓷砖和 最后一块 瓷砖是相邻的。

模拟即可，注意边界情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def numberOfAlternatingGroups(self, colors: List[int]) -> int:
        n = len(colors)
        cnt = 0
        for i in range(1, n-1):
            if colors[i-1] == colors[i+1] and colors[i] != colors[i-1]:
                cnt += 1
            else:
                continue
        if colors[n-2] == colors[0] and colors[n-1] != colors[0]:
            cnt += 1
        if colors[n-1] == colors[1] and colors[n-1] != colors[0]:
            cnt += 1
        return cnt

发表于

图像平滑器 是大小为 3 x 3 的过滤器，用于对图像的每个单元格平滑处理，平滑处理后单元格的值为该单元格的平均灰度。

每个单元格的 平均灰度 定义为：该单元格自身及其周围的 8 个单元格的平均值，结果需向下取整。（即，需要计算蓝色平滑器中 9 个单元格的平均值）。

题目意思就是写一个 3 * 3 的 Averge Pooling。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:
        m, n = len(img), len(img[0])
        ans  = [[0 for _ in range(n)] for _ in range(m)]
        directions = [-1, 0, 1]
        for i in range(m):
            for j in range(n):
                count = 0
                total = 0
                for row in directions:
                    for col in directions:
                        if 0 <= i+row <= m-1 and 0 <= j+col <= n-1:
                            total += img[i+row][j+col]
                            count += 1
                average = total // count
                ans[i][j] = average
        return ans

发表于

翻转一棵二叉树。

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
# 递归
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return 
        root.left, root.right = root.right, root.left
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root
    
# 迭代
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return
        stack = [root]
        while stack:
            cur = stack.pop()
            cur.left, cur.right = cur.right, cur.left
            if cur.left: stack.append(cur.left)
            if cur.right: stack.append(cur.right)
        return root

发表于

给你一个二叉树的根节点 root ， 检查它是否 轴对称 。

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

# 递归
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def helper(left_tree, right_tree):
            if not left_tree and not right_tree: return True
            if left_tree and right_tree:
                if left_tree.val == right_tree.val and helper(left_tree.right, right_tree.left) and helper(left_tree.left, right_tree.right):
                    return True
            return False
        return helper(root.left, root.right)
    
# 迭代
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        queue = [root, root]
        while queue:
            cur_left, cur_right = queue[0], queue[1]
            if not cur_left and not cur_right: 
                queue = queue[2:]
                continue
            if not cur_left or not cur_right or cur_left.val != cur_right.val:
                return False
            queue.append(cur_left.left)
            queue.append(cur_right.right)
            queue.append(cur_left.right)
            queue.append(cur_right.left)
            queue = queue[2:]
        return True

发表于

给定一个二叉树，找出其最大深度。

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

# DFS
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        def helper(root, depth):
            if not root:
                return depth
            else:
                return max(helper(root.left, depth+1), helper(root.right, depth+1))
        return helper(root, 0)

# BFS
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root: 
            return 0
        queue, res = [root], 0
        while queue:
            tmp = []
            for node in queue:
                if node.left:
                    tmp.append(node.left)
                if node.right:
                    tmp.append(node.right)
            queue = tmp
            res += 1
        return res