数据结构与算法之二叉树: LeetCode 654. 最大二叉树 (Ts版)
最大二叉树
- https://leetcode.cn/problems/maximum-binary-tree/
描述
- 给定一个不重复的整数数组 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 的节点。
- 空数组,无子节点。
- [3,2,1] 中的最大值是 3 ,左边部分是 [] ,右边部分是 [2,1] 。
示例 2
输入:nums = [3,2,1]
输出:[3,null,2,null,1]
提示
- 1 <= nums.length <= 1000
- 0 <= nums[i] <= 1000
- nums 中的所有整数 互不相同
Typescript 版算法实现
1 ) 方案1:递归
/*** Definition for a binary tree node.* class TreeNode {* val: number* left: TreeNode | null* right: TreeNode | null* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {* this.val = (val===undefined ? 0 : val)* this.left = (left===undefined ? null : left)* this.right = (right===undefined ? null : right)* }* }*/function constructMaximumBinaryTree(nums: number[]): TreeNode | null {const construct = (nums, left, right) => {if (left > right) return null;let best = left;for (let i = left + 1; i <= right; ++i) {if (nums[i] > nums[best]) {best = i;}}const node = new TreeNode(nums[best]);node.left = construct(nums, left, best - 1);node.right = construct(nums, best + 1, right);return node;}return construct(nums, 0, nums.length - 1);
};
2 ) 方案2:单调栈
/*** Definition for a binary tree node.* class TreeNode {* val: number* left: TreeNode | null* right: TreeNode | null* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {* this.val = (val===undefined ? 0 : val)* this.left = (left===undefined ? null : left)* this.right = (right===undefined ? null : right)* }* }*/function constructMaximumBinaryTree(nums: number[]): TreeNode | null {const n = nums.length;const stack = [];const left = new Array(n).fill(-1);const right = new Array(n).fill(-1);const tree = new Array(n).fill(-1);for (let i = 0; i < n; ++i) {tree[i] = new TreeNode(nums[i]);while (stack.length && nums[i] > nums[stack[stack.length - 1]]) {right[stack.pop()] = i;}if (stack.length) {left[i] = stack[stack.length - 1];}stack.push(i);}let root = null;for (let i = 0; i < n; ++i) {if (left[i] === -1 && right[i] === -1) {root = tree[i];} else if (right[i] === -1 || (left[i] !== -1 && nums[left[i]] < nums[right[i]])) {tree[left[i]].right = tree[i];} else {tree[right[i]].left = tree[i];}}return root;
};
3 ) 方案3:单调栈优化
/*** Definition for a binary tree node.* class TreeNode {* val: number* left: TreeNode | null* right: TreeNode | null* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {* this.val = (val===undefined ? 0 : val)* this.left = (left===undefined ? null : left)* this.right = (right===undefined ? null : right)* }* }*/function constructMaximumBinaryTree(nums: number[]): TreeNode | null {const n = nums.length;const stack = [];const tree = new Array(n).fill(0);for (let i = 0; i < n; ++i) {tree[i] = new TreeNode(nums[i]);while (stack.length && nums[i] > nums[stack[stack.length - 1]]) {tree[i].left = tree[stack[stack.length - 1]];stack.pop();}if (stack.length) {tree[stack[stack.length - 1]].right = tree[i];}stack.push(i);}return tree[stack[0]];
};
相关文章:
数据结构与算法之二叉树: LeetCode 654. 最大二叉树 (Ts版)
最大二叉树 https://leetcode.cn/problems/maximum-binary-tree/ 描述 给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建: 创建一个根节点,其值为 nums 中的最大值递归地在最大值 左边 的 子数组前缀上 构建左子树递归地在最大值…...
Linux 容器漏洞
定义:Linux 容器漏洞是指在容器技术(如 Docker、LXC 等)运行环境中存在的安全弱点。这些漏洞可能存在于容器镜像本身、容器运行时(如 runc)、容器编排工具(如 Kubernetes)或者容器与主机之间的交…...
file与io流(1)
-1- java.io.File类的使用 (1) 概述 File类及本章下的各种流,都定义在java.io包下。一个File对象代表硬盘或网络中可能存在的一个文件或者文件目录(俗称文件夹),与平台无关。(体会万事万物皆…...
忘记了PDF文件的密码,怎么办?
PDF文件可以加密,大家都不陌生,并且大家应该也都知道PDF文件有两种密码,一个打开密码、一个限制编辑密码,因为PDF文件设置了密码,那么打开、编辑PDF文件就会受到限制。忘记了PDF密码该如何解密? PDF和offi…...
Linux权限管理(用户和权限之间的关系)
Linux系列 文章目录 Linux系列一、Linux下用户类型二、普通权限的基本概念2.1、Linux中权限的类别2.2、Linux中权限对应的三种身份2.3、文件权限的标识 三、文件权限设置四、修改文件属主和属组4.1、chown修改文件的属主4.2、修改所属组 五、文件掩码六、目录权限 一、Linux下用…...
Python Selenium库入门使用,图文详细。附网页爬虫、web自动化操作等实战操作。
文章目录 前言1 创建conda环境安装Selenium库2 浏览器驱动下载(以Chrome和Edge为例)3 基础使用(以Chrome为例演示)3.1 与浏览器相关的操作3.1.1 打开/关闭浏览器3.1.2 访问指定域名的网页3.1.3 控制浏览器的窗口大小3.1.4 前进/后…...
【Uniapp-Vue3】使用defineExpose暴露子组件的属性及方法
如果我们想要让父组件访问到子组件中的变量和方法,就需要使用defineExpose暴露: defineExpose({ 变量 }) 子组件配置 父组件配置 父组件要通过onMounted获取到子组件的DOM 传递多个属性和方法 子组件 父组件...
【多模态LLM】英伟达NVLM多模态大模型训练细节和数据集
前期笔者介绍了OCR-free的多模态大模型,可以参考:【多模态&文档智能】OCR-free感知多模态大模型技术链路及训练数据细节,其更偏向于训练模型对于密集文本的感知能力。本文看一看英伟达出品的多模态大模型NVLM-1.0系列,虽然暂未…...
HTTP详解——HTTP基础
HTTP 基本概念 HTTP 是超文本传输协议 (HyperText Transfer Protocol) 超文本传输协议(HyperText Transfer Protocol) HTTP 是一个在计算机世界里专门在 两点 之间 传输 文字、图片、音视频等 超文本 数据的 约定和规范 1. 协议 约定和规范 2. 传输 两点之间传输…...
MySQL教程之:输入查询
如上一节所述,确保您已连接到服务器。这样做本身不会选择任何要使用的数据库,但没关系。在这一点上,了解一下如何发出查询比直接创建表、加载数据和从中检索数据更重要。本节介绍输入查询的基本原则,使用几个查询,您可…...
docker+ffmpeg+nginx+rtmp 拉取摄像机视频
1、构造程序容器镜像 app.py import subprocess import json import time import multiprocessing import socketdef check_rtmp_server(host, port, timeout5):try:with socket.create_connection((host, port), timeout):print(f"RTMP server at {host}:{port} is avai…...
不同音频振幅dBFS计算方法
1. 振幅的基本概念 振幅是描述音频信号强度的一个重要参数。它通常表示为信号的幅度值,幅度越大,声音听起来就越响。为了更好地理解和处理音频信号,通常会将振幅转换为分贝(dB)单位。分贝是一个对数单位,能…...
【17. 电话号码的字母组合 中等】
题目: 给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。 示例 1: 输入:digits “23”…...
数据结构初阶---排序
一、排序相关概念与运用 1.排序相关概念 排序:所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。 稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的…...
【从0-1实现一个前端脚手架】
目录 介绍为什么需要脚手架?一个脚手架应该具备哪些功能? 脚手架实现初始化项目相关依赖实现脚手架 发布 介绍 为什么需要脚手架? 脚手架本质就是一个工具,作用是能够让使用者专注于写代码,它可以让我们只用一个命令…...
AI文章管理系统(自动生成图文分发到分站)
最近帮一个网上的朋友做了一套AI文章生成系统。他的需求是这样: 1、做一个服务端转接百度文心一言的生成文章的API接口。 2、服务端能注册用户,用户在服务端注册充值后可以获取一个令牌,这个令牌填写到客户端,客户端就可以根据客…...
【Leetcode 每日一题】3270. 求出数字答案
问题背景 给你三个 正 整数 n u m 1 num_1 num1, n u m 2 num_2 num2 和 n u m 3 num_3 num3。 数字 n u m 1 num_1 num1, n u m 2 num_2 num2 和 n u m 3 num_3 num3 的数字答案 k e y key key 是一个四位数,定义如下&…...
基于单片机的无线气象仪系统设计(论文+源码)
1系统方案设计 如图2.1所示为无线气象仪系统设计框架。系统设计采用STM32单片机作为主控制器,结合DHT11温湿度传感器、光敏传感器、BMP180气压传感器、PR-3000-FS-N01风速传感器实现气象环境的温度、湿度、光照、气压、风速等环境数据的检测,并通过OLED1…...
【数据库】Mysql精简回顾复习
一、概念 数据库(DB):数据存储的仓库数据库管理系统(DBMS):操纵和管理数据库的大型软件SQL:操作关系型数据库的编程语言,是一套标准关系型数据库(RDBMS)&…...
深入理解 HTTP 的 GET、POST 方法与 Request 和 Response
HTTP 协议是构建 Web 应用的基石,GET 和 POST 是其中最常用的请求方法。无论是前端开发、后端开发,还是接口测试,对它们的深入理解都显得尤为重要。在本文中,我们将介绍 GET 和 POST 方法,以及 Request 和 Response 的…...
HTML 语义化
目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案: 语义化标签: <header>:页头<nav>:导航<main>:主要内容<article>&#x…...
【Python】 -- 趣味代码 - 小恐龙游戏
文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...
Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)
概述 在 Swift 开发语言中,各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过,在涉及到多个子类派生于基类进行多态模拟的场景下,…...
无法与IP建立连接,未能下载VSCode服务器
如题,在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈,发现是VSCode版本自动更新惹的祸!!! 在VSCode的帮助->关于这里发现前几天VSCode自动更新了,我的版本号变成了1.100.3 才导致了远程连接出…...
转转集团旗下首家二手多品类循环仓店“超级转转”开业
6月9日,国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解,“超级…...
数据链路层的主要功能是什么
数据链路层(OSI模型第2层)的核心功能是在相邻网络节点(如交换机、主机)间提供可靠的数据帧传输服务,主要职责包括: 🔑 核心功能详解: 帧封装与解封装 封装: 将网络层下发…...
Element Plus 表单(el-form)中关于正整数输入的校验规则
目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入(联动)2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...
短视频矩阵系统文案创作功能开发实践,定制化开发
在短视频行业迅猛发展的当下,企业和个人创作者为了扩大影响力、提升传播效果,纷纷采用短视频矩阵运营策略,同时管理多个平台、多个账号的内容发布。然而,频繁的文案创作需求让运营者疲于应对,如何高效产出高质量文案成…...
基于Springboot+Vue的办公管理系统
角色: 管理员、员工 技术: 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能: 该办公管理系统是一个综合性的企业内部管理平台,旨在提升企业运营效率和员工管理水…...
Linux nano命令的基本使用
参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时,显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...
