当前位置: 首页 > news >正文

力扣96. 不同的二叉搜索树

Problem: 96. 不同的二叉搜索树

文章目录

  • 题目描述
  • 思路
  • 复杂度
  • Code

题目描述

在这里插入图片描述

思路

一个数字做根节点的话可能的结果为:其左边数字做子树的组合数字乘以其右边数字做子树的个数之积

1.创建备忘录memo;
2.递归分别求取当前数字左边和右边数字做子树的数量(注意下面代码当左边界值大于有边界值时应当反回1)

复杂度

时间复杂度:

O ( n ) O(n) O(n);其中 n n n是二叉树节点的个数

空间复杂度:

O ( h e i g h t ) O(height) O(height);其中 h e i g h t height height是二叉树的高度

Code

class Solution {int[][] memo;/*** Unique Binary Search Trees** @param n Given number* @return int*/public int numTrees(int n) {memo = new int[n + 1][n + 1];return count(1, n);}/*** Unique Binary Search Trees(Implementation function)** @param low  Left boundary* @param high Right boundary* @return int*/private int count(int low, int high) {if (low > high) {return 1;}//Check the memeif (memo[low][high] != 0) {return memo[low][high];}int res = 0;for (int mid = low; mid <= high; ++mid) {int left = count(low, mid - 1);int right = count(mid + 1, high);res += left * right;}memo[low][high] = res;return res;}
}

相关文章:

力扣96. 不同的二叉搜索树

Problem: 96. 不同的二叉搜索树 文章目录 题目描述思路复杂度Code 题目描述 思路 一个数字做根节点的话可能的结果为&#xff1a;其左边数字做子树的组合数字乘以其右边数字做子树的个数之积 1.创建备忘录memo&#xff1b; 2.递归分别求取当前数字左边和右边数字做子树的数量&…...

哈希表的用途

...

k8s笔记 | 高度调度

CronJob计划任务 简介&#xff1a;在k8s中周期性运行计划任务&#xff0c;与linux中的crontab相同&#xff1b;注意点 CornJob执行的时间是controller-manager的时间&#xff0c;所以一定要确保controller-manager的时间是准确的&#xff0c;另外cornjob cron表达式 文章参…...

Rom应用开发遇到得一些小bug

记录一些细碎得bug ROM时间类问题 问题描述&#xff1a; 设备拔电重启&#xff0c;ROM时间为默认时间如1970年1月1日&#xff0c;与某些业务场景互斥 问题原因&#xff1a; 后台接口校验https证书校验失败&#xff0c;要求是2年内得请求头校验了时间戳&#xff0c;时间戳过期…...

Python简介

Python简介 1. Python定义 Python 是一种简单易学并且结合了解释性、编译性、互动性和面向对象的脚本语言。Python提供了高级数据结构&#xff0c;它的语法和动态类型以及解释性使它成为广大开发者的首选编程语言。 Python 是解释型语言&#xff1a; 开发过程中没有了编译这个环…...

C++完成特色旅游管理信息系统

背景&#xff1a; 继C完成淄博烧烤节管理系统后&#xff0c;我们来到了特色旅游管理信息系统的代码编写&#xff0c;历史链接点下方。 C完成淄博烧烤节管理系统_淄博烧烤总账管理系统的-CSDN博客 问题描述&#xff1a; 为了更好的管理各个服务小组&#xff0c;开发相应的管…...

贵州大学24计算机考研数据速览,国家重点实验室22408复试线285分!贵州大学计算机考研考情分析!

贵州大学计算机科学与技术学院坐落在贵州大学北校区&#xff08;贵阳花溪&#xff09;。 学院现有教职工139人&#xff0c;其中专职教师126人&#xff0c;教授17人&#xff0c;副教授37人&#xff0c;讲师46人&#xff0c;高级实验师4人&#xff0c;实验师17人。具有博士学位的…...

分区4K对齐那些事,你想知道的都在这里

在对磁盘进行分区时,有一个很重要的注意事项,就是要将分区对齐,不对齐可能会造成磁盘性能的下降。尤其是固态硬盘SSD,基本上都要求4K对齐。磁盘读写速度慢还找不到原因?可能就是4K对齐的锅。那么分区对齐究竟是怎么回事?为什么要对齐?如何才能对齐?如何检测是否对齐呢?…...

达梦数据库学习笔记

架构、特点和基本概念 达梦数据库&#xff08;DM Database&#xff09;是中国达梦数据库有限公司自主研发的关系型数据库管理系统。它广泛应用于政府、金融、电信、能源等行业&#xff0c;具备高性能、高可靠性和高安全性的特点。 架构 达梦数据库的架构设计注重高性能和高可…...

安卓绕过限制直接使用Android/data无需授权,支持安卓14(部分)

大家都知道&#xff0c;安卓每次更新都会给权限划分的更细、收的更紧。   早在安卓11的时候还可以直接通过授权Android/data来实现操作其他软件的目录&#xff0c;没有之前安卓11授权的图了&#xff0c;反正都长一个样&#xff0c;就直接贴新图了。   后面到了安卓12~13的…...

【知识蒸馏】多任务模型 logit-based 知识蒸馏实战

一、什么是逻辑&#xff08;logit&#xff09;知识蒸馏 Feature-based蒸馏原理是知识蒸馏中的一种重要方法&#xff0c;其关键在于利用教师模型的隐藏层特征来指导学生模型的学习过程。这种蒸馏方式旨在使学生模型能够学习到教师模型在特征提取和表示方面的能力&#xff0c;从…...

C:技术面试总结

1 变量的声明和定义: 定义:为变量分配地址和存储空间 声明:不分配地址。一个变量可以在多个地方声明,但只能在一个地方定义。extern修饰的变量声明,说明此变量将在文件以外或文件后面部分定义。 2 局部变量是否能与全局变量重名: 可以,局部变量会屏蔽全局变量 局部…...

OpenHarmony 实战开发——一文总结ACE代码框架

一、前言 ACE_Engine框架是OpenAtom OpenHarmony&#xff08;简称“OpenHarmony”&#xff09;的UI开发框架&#xff0c;为开发者提供在进行应用UI开发时所必需的各种组件&#xff0c;以及定义这些组件的属性、样式、事件及方法&#xff0c;通过这些组件可以方便进行OpenHarmo…...

【数据结构与算法】之堆的应用——堆排序及Top_K问题!

目录 1、堆排序 2、Top_K问题 3、完结散花 个人主页&#xff1a;秋风起&#xff0c;再归来~ 数据结构与算法 个人格言&#xff1a;悟已往之不谏&#xff0c;知来者犹可追 克心守己&#xff0c;律己则安&#xff01; 1、堆排序 对一个无序的数组…...

啊哈!算法-第2章-栈、队列、链表

啊哈!算法-第2章-栈、队列、链表 第1节 解密qq号——队列第2节 解密回文——栈第3节 纸牌游戏——小猫钓鱼第4节 链表第5节 模拟链表 第1节 解密qq号——队列 新学期开始了&#xff0c;小哈是小哼的新同桌(小哈是个大帅哥哦~)&#xff0c;小哼向小哈询问 QQ 号&#xff0c; 小…...

简述 v-if 和 v-show 的区别

v-if 和 v-show 都是 Vue.js 中用于控制元素显示与隐藏的指令&#xff0c;但它们的工作方式有显著的差异。以下是它们之间的主要区别&#xff1a; 渲染方式&#xff1a; v-if&#xff1a;v-if 是“真正”的条件渲染&#xff0c;因为它会确保在切换过程中条件块内的事件监听器和…...

Linux驱动学习之模块化,参数传递,符号导出

1.模块化 1.1.模块化的基本概念&#xff1a; 模块化是指将特定的功能或组件独立出来&#xff0c;以便于开发、测试和维护。在Linux设备驱动中&#xff0c;模块化允许将驱动程序作为内核模块动态加载到系统中&#xff0c;从而提高了系统的灵活性和可扩展性。 1.2.Linux内核模…...

RabbitMQ02-RebbitMQ简介及交换器

一. AMQP协议 什么是AMQP协议 AMQP(Advanced Message Queuing Protocol,高级消息队列协议):它是进程之间传递异步消息的网络协议 AMQP工作过程 发布者通过发布消息&#xff0c;通过交换机&#xff0c;交换机根据路由规则将收到的消息分发交换机绑定的下消息队列&#xff0c;最…...

Matlab自学笔记三十:元胞数组的修改、添加、删除和连接

1.说明 元胞数组的子数组或元素也是元胞型的&#xff0c;其元素内容&#xff08;值&#xff09;是本身类型&#xff0c;因此&#xff0c;在添、删、改和连接处理时&#xff0c;必须明确每个元素的值的类型和大小&#xff0c;否则&#xff0c;编程报错是不可避免的了。看本文前…...

【LeetCode】数组——双指针法

1 双指针法 1.1 介绍 双指针法是一种常用的算法技巧&#xff0c;通常用于处理数组或链表中的问题。它使用两个指针&#xff0c;通常一个从数组的开始位置遍历&#xff0c;另一个从数组的末尾位置开始遍历&#xff0c;根据问题的不同&#xff0c;这两个指针可以同时移动&#…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

CMake控制VS2022项目文件分组

我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表

##鸿蒙核心技术##运动开发##Sensor Service Kit&#xff08;传感器服务&#xff09;# 前言 在运动类应用中&#xff0c;运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据&#xff0c;如配速、距离、卡路里消耗等&#xff0c;用户可以更清晰…...

智能AI电话机器人系统的识别能力现状与发展水平

一、引言 随着人工智能技术的飞速发展&#xff0c;AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术&#xff0c;在客户服务、营销推广、信息查询等领域发挥着越来越重要…...

[ACTF2020 新生赛]Include 1(php://filter伪协议)

题目 做法 启动靶机&#xff0c;点进去 点进去 查看URL&#xff0c;有 ?fileflag.php说明存在文件包含&#xff0c;原理是php://filter 协议 当它与包含函数结合时&#xff0c;php://filter流会被当作php文件执行。 用php://filter加编码&#xff0c;能让PHP把文件内容…...

MacOS下Homebrew国内镜像加速指南(2025最新国内镜像加速)

macos brew国内镜像加速方法 brew install 加速formula.jws.json下载慢加速 &#x1f37a; 最新版brew安装慢到怀疑人生&#xff1f;别怕&#xff0c;教你轻松起飞&#xff01; 最近Homebrew更新至最新版&#xff0c;每次执行 brew 命令时都会自动从官方地址 https://formulae.…...