• LeetCode 1470. 重新排列数组 / 654. 最大二叉树 / 998. 最大二叉树 II


    1470. 重新排列数组

    2022.8.29 每日一题

    题目描述

    给你一个数组 nums ,数组中有 2n 个元素,按 [x1,x2,…,xn,y1,y2,…,yn] 的格式排列。

    请你将数组按 [x1,y1,x2,y2,…,xn,yn] 格式重新排列,返回重排后的数组。

    示例 1:

    输入:nums = [2,5,1,3,4,7], n = 3
    输出:[2,3,5,4,1,7]
    解释:由于 x1=2, x2=5, x3=1, y1=3, y2=4, y3=7 ,所以答案为 [2,3,5,4,1,7]

    示例 2:

    输入:nums = [1,2,3,4,4,3,2,1], n = 4
    输出:[1,4,2,3,3,2,4,1]

    示例 3:

    输入:nums = [1,1,2,2], n = 2
    输出:[1,2,1,2]

    提示:

    1 <= n <= 500
    nums.length == 2n
    1 <= nums[i] <= 10^3

    来源:力扣(LeetCode)
    链接:https://leetcode.cn/problems/shuffle-the-array
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

    思路

    我自己写的,平平无奇(没看到n)

    class Solution:
        def shuffle(self, nums: List[int], n: int) -> List[int]:
            res = []
            for i in range(len(nums) // 2):
                res.append(nums[i])
                res.append(nums[i + len(nums) // 2])
            return res
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    大佬写的

    class Solution:
        def shuffle(self, nums: List[int], n: int) -> List[int]:
            nums[::2], nums[1::2] = nums[:n], nums[n:]
            return nums
    
    • 1
    • 2
    • 3
    • 4

    654. 最大二叉树

    8.30每日一题的前置

    题目描述

    给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

    • 创建一个根节点,其值为 nums 中的最大值。
    • 递归地在最大值 左边 的 子数组前缀上 构建左子树。
    • 递归地在最大值 右边 的 子数组后缀上 构建右子树。

    返回 nums 构建的 最大二叉树 。

    示例 1:

    在这里插入图片描述

    输入:nums = [3,2,1,6,0,5]
    输出:[6,3,5,null,2,0,null,null,1]
    解释:递归调用如下所示:

    • [3,2,1,6,0,5] 中的最大值是 6 ,左边部分是 [3,2,1] ,右边部分是 [0,5] 。
      • [3,2,1] 中的最大值是 3 ,左边部分是 [] ,右边部分是 [2,1] 。
        • 空数组,无子节点。
        • [2,1] 中的最大值是 2 ,左边部分是 [] ,右边部分是 [1] 。
          • 空数组,无子节点。
          • 只有一个元素,所以子节点是一个值为 1 的节点。
      • [0,5] 中的最大值是 5 ,左边部分是 [0] ,右边部分是 [] 。
        • 只有一个元素,所以子节点是一个值为 0 的节点。
        • 空数组,无子节点。

    示例 2:
    在这里插入图片描述

    输入:nums = [3,2,1]
    输出:[3,null,2,null,1]

    提示:

    1 <= nums.length <= 1000
    0 <= nums[i] <= 1000
    nums 中的所有整数 互不相同

    来源:力扣(LeetCode)
    链接:https://leetcode.cn/problems/maximum-binary-tree
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

    思路

    按照给的步骤写代码就行了

    # 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 constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
            # 就是按照这个步骤,先找最大值,然后递归处理左右部分
            if not nums:
                return None
            maxnum = max(nums)
            idx = nums.index(maxnum)
            node = TreeNode(maxnum)
            node.left = self.constructMaximumBinaryTree(nums[:idx])
            node.right = self.constructMaximumBinaryTree(nums[idx + 1:])
            return node
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    单调栈,如果小于栈顶就弹出,大于就放进去
    然后放进去的元素因为要小于栈顶,而且在右边,所以要将加入元素放在栈顶的右子树
    弹出的元素因为小于要加入的元素,而且在左边,所以要放在加入元素的左子树
    这样处理以后,当前栈底的元素就是最大值,输出这个节点就可以了

    class Solution:
        def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
            # 想想单调栈该怎么写
            # 放数据,存下标,然后遍历,发现新的,如果比当前小,入栈
            # 如果比当前大,出栈,此时是最小的,创建该节点,并挂在已有节点的右边
            # 然后再出栈,因为比上一个大,将上一个挂在该节点的右边
            node = TreeNode(nums[0])
            stack = [node]
            for num in nums[1:]:
                node = TreeNode(num)
                # 如果大于栈顶元素,将栈顶元素挂在当前元素左边
                while stack and num > stack[-1].val:
                    temp = stack.pop()
                    node.left = temp
                
                if stack:
                    stack[-1].right = node
                stack.append(node)
    
            return stack[0]
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    998. 最大二叉树 II

    2022.8.30 每日一题

    题目描述

    最大树 定义:一棵树,并满足:其中每个节点的值都大于其子树中的任何其他值。

    给你最大树的根节点 root 和一个整数 val 。

    就像 之前的问题 那样,给定的树是利用 Construct(a) 例程从列表 a(root = Construct(a))递归地构建的:

    如果 a 为空,返回 null 。
    否则,令 a[i] 作为 a 的最大元素。创建一个值为 a[i] 的根节点 root 。
    root 的左子树将被构建为 Construct([a[0], a[1], …, a[i - 1]]) 。
    root 的右子树将被构建为 Construct([a[i + 1], a[i + 2], …, a[a.length - 1]]) 。
    返回 root 。
    请注意,题目没有直接给出 a ,只是给出一个根节点 root = Construct(a) 。

    假设 b 是 a 的副本,并在末尾附加值 val。题目数据保证 b 中的值互不相同。

    返回 Construct(b) 。

    示例 1:

    在这里插入图片描述
    输入:root = [4,1,3,null,null,2], val = 5
    输出:[5,4,null,1,3,null,null,2]
    解释:a = [1,4,2,3], b = [1,4,2,3,5]

    示例 2:

    在这里插入图片描述
    输入:root = [5,2,4,null,1], val = 3
    输出:[5,2,4,null,1,null,3]
    解释:a = [2,1,5,4], b = [2,1,5,4,3]

    示例 3:

    在这里插入图片描述
    输入:root = [5,2,3,null,1], val = 4
    输出:[5,2,4,null,1,3]
    解释:a = [2,1,5,3], b = [2,1,5,3,4]

    提示:

    树中节点数目在范围 [1, 100] 内
    1 <= Node.val <= 100
    树中的所有值 互不相同
    1 <= val <= 100

    来源:力扣(LeetCode)
    链接:https://leetcode.cn/problems/maximum-binary-tree-ii
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

    思路

    主要难点在于理解题目让干什么

    # 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 insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
            # 看了半天,把那个题做了才看懂意思
            # 就是说在原来的树的基础上,在数组最后面加了一个数字,然后让输出新的树
            # 所以现在的问题就是,这个数字该插入到哪里
            # 首先,从根部开始找,如果大于根部,那么直接将根部接在左子树
            # 一直找右子树,直到找到比节点大的点
            node = TreeNode(val)
            if root.val < val:
                node.left = root
                return node
    
            temp = root
            while temp.right:
                if temp.right.val < val:
                    node.left = temp.right
                    temp.right = node
                    break
                temp = temp.right
            if not node.right:
                temp.right = node
            return 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
  • 相关阅读:
    中金所Java面试题整合
    各位帮我看看为啥冒红啊
    3款自己电脑就可以运行AI LLM的项目
    Elasticsearch核心技术与实战-05-elasticsearch的安装与简单配置-Windows
    孤网双机并联逆变器下垂控制策略MATLAB仿真模型
    中国程序员做独立开发者的怎么这么少呢?
    Maven的安装与配置与使用
    在项目中使用flex布局的justify-content:space-around;遇到的问题,(数量为单数)
    python使用matplotlib可视化subplots子图、subplots绘制子图并为可视化的多个子图设置共享的X轴
    SoundTouch对音频处理(Android)
  • 原文地址:https://blog.csdn.net/windyjcy/article/details/126577765