PeterQwQ
0%

发表于 更新于

给你二叉树的根结点 root ，请你将它展开为一个单链表：

  • 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。

  • 展开后的单链表应该与二叉树 先序遍历 顺序相同。

题目要求和先序遍历的顺序相同，直接使用一个列表存储先序遍历的结果，然后将每个节点的左子树置空，右子树指向下一个节点即可。

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
# 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 flatten(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        if not root: return
        tmp = []
        def preorder_traversal(root):
            if not root:
                return 
            tmp.append(root)
            preorder_traversal(root.left)
            preorder_traversal(root.right)
        preorder_traversal(root)
        for i in range(1, len(tmp)):
            node = tmp[i]
            root.left = None
            root.right = node
            root = root.right

发表于 更新于

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找二叉搜索树中第 k 个最小元素（从 1 开始计数）。

我对于二叉搜索树的遍历还是不够熟练，这里采用了层序遍历的方法，将所有节点的值存入一个列表中，然后对列表进行排序，返回第k个元素即可。

实际上，对于一颗二叉搜索树，中序遍历的结果就是一个有序的列表，所以可以直接对二叉搜索树进行中序遍历，同时记录遍历的节点数，当遍历到第k个节点时，返回该节点的值即可。

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 kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        queue, ans = [root], []
        while queue:
            tmp =[]
            for node in queue:
                if node.left: tmp.append(node.left)
                if node.right: tmp.append(node.right)
                ans.append(node.val)
            queue = tmp
        ans = sorted(ans)
        return ans[k-1]

发表于 更新于

给你一个二叉树的根节点 root ，判断其是否是一个有效的 二叉搜索树。

有效 二叉搜索树定义如下：

  • 节点的左子树只包含 小于 当前节点的数。

  • 节点的右子树只包含 大于 当前节点的数。

  • 所有左子树和右子树自身必须也是二叉搜索树。

这题目主要是要理解到底什么样才是有效的二叉搜索树。对于一个节点而言，不仅仅是它的左节点要小于它，右节点要大于它，而且它的左节点的左节点也要小于它，右节点的右节点也要大于它。

所以我们需要传递一个上下界，来判断当前节点是否在这个范围内。对于一个节点的左节点，它的上界就是当前节点的值，下界是负无穷。对于一个节点的右节点，它的下界就是当前节点的值，上界是正无穷。那么我们就可以递归的判断每个节点是否在这个范围内。

根节点没有上下界，所以我们可以传入负无穷和正无穷。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def check_valid(node, lower, upper):
            if not node:
                return True
            if node.val <= lower or node.val >= upper:
                return False
            return check_valid(node.left, lower, node.val) and check_valid(node.right, node.val, upper)
        return check_valid(root, float('-inf'), float('inf'))

发表于 更新于

给你一个整数数组 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