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

LeetCode-96. 不同的二叉搜索树

题目来源
96. 不同的二叉搜索树

递归

1.我们要知道二叉搜索树的性质,对于一个二叉搜索树,其 【左边的节点值 < 中间的节点值 < 右边的节点值】,也就是说,对于一个二叉搜索树,其中序遍历之后形成的数组应该是一个递增的序列,如下图:
在这里插入图片描述
2.我们不妨就假设我们拿到了一个中序遍历的数组nums = [1,2,3,4,5,6,7],来思考一个这样的数组能延伸出多少种二叉搜索树。
首先,对于数组中的每一个元素,都有可能成为二叉树最顶部的root节点,例如上图中,是nums[4]这个值,即5,充当了root节点。
3.还拿5这个节点为例,即上图,其左边有四个节点,右边有两个节点。对于左边的四个节点,假设能延伸出 n 种二叉搜索树子树,对于右边的两个节点,假设能延伸出 m 种二叉搜索树子树。则以5为root节点时的二叉搜索树总数为 m*n
4.这样我们遍历刚刚的nums数组,以值i(注意不是下标)当做根节点,其左边有i-1个节点,右边有n-i个节点,计算出可能的二叉搜索树数量,添加到总结果里即可,我们初步写出的代码如下

class Solution {public int numTrees(int n) {if(n == 0 || n == 1){return 1;}int count = 0;for(int i = 1;i<=n;i++){count+=numTrees(i-1)*numTrees(n-i);}return count;}
}

在这里插入图片描述

递归优化

其实是出现了很多次重复计算过程,举例[1,2,3]
大量的重复计算造成我们时间过长,因此我们可以用一个HashMap存储n和子树数量的映射,如果已经计算过了当前n的子树数量,直接取出用即可
在这里插入图片描述

class Solution {private HashMap<Integer,Integer> map = new HashMap();public int numTrees(int n) {if(n == 0 || n == 1){return 1;}if(map.containsKey(n)){return map.get(n);}int count = 0;for(int i = 1;i<=n;i++){count+=numTrees(i-1) * numTrees(n-i);map.put(n,count);}return count;}
}

在这里插入图片描述

动态规划

动规五部曲

  • 1.确定dp数组(dp table)以及下标的含义

dp[i] : 1到i为节点组成的二叉搜索树的个数为dp[i]。
也可以理解是i个不同元素节点组成的二叉搜索树的个数为dp[i] ,都是一样的。

  • 2.确定递推公式

在上面的分析中,其实已经看出其递推关系, dp[i] += dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量]
j相当于是头结点的元素,从1遍历到i为止。
所以递推公式:dp[i] += dp[j - 1] * dp[i - j]; ,j-1 为j为头结点左子树节点数量,i-j 为以j为头结点右子树节点数量

  • 3.dp数组如何初始化

初始化,只需要初始化dp[0]就可以了,推导的基础,都是dp[0]。
那么dp[0]应该是多少呢?
从定义上来讲,空节点也是一棵二叉树,也是一棵二叉搜索树,这是可以说得通的。
从递归公式上来讲,dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量] 中以j为头结点左子树节点数量为0,也需要dp[以j为头结点左子树节点数量] = 1, 否则乘法的结果就都变成0了。
所以初始化dp[0] = 1

  • 4.确定遍历顺序
    首先一定是遍历节点数,从递归公式:dp[i] += dp[j - 1] * dp[i - j]可以看出,节点数为i的状态是依靠 i之前节点数的状态。
    那么遍历i里面每一个数作为头结点的状态,用j来遍历。
        for(int i = 1;i <= n;i++){for(int j = 1;j<=i;j++){dp[i] += dp[j-1]*dp[i-j];}}
  • 5.举例推导dp数组

n为5时候的dp数组状态如图:
在这里插入图片描述
整体代码

class Solution {public int numTrees(int n) {int[] dp = new int[n+1];dp[0] = 1;for(int i = 1;i <= n;i++){for(int j = 1;j<=i;j++){dp[i] += dp[j-1]*dp[i-j];}}return dp[n];}
}

在这里插入图片描述

相关文章:

LeetCode-96. 不同的二叉搜索树

题目来源 96. 不同的二叉搜索树 递归 1.我们要知道二叉搜索树的性质&#xff0c;对于一个二叉搜索树&#xff0c;其 【左边的节点值 < 中间的节点值 < 右边的节点值】&#xff0c;也就是说&#xff0c;对于一个二叉搜索树&#xff0c;其中序遍历之后形成的数组应该是一…...

JavaWeb基础

Servlet 是在服务器上运行的小程序。这个词是在 Java applet的环境中创造的&#xff0c;Java applet 是一种当作单独文件跟网页一起发送的小程序&#xff0c;它通常用于在客户端运行&#xff0c;结果得到为用户进行运算或者根据用户互作用定位图形等服务。服务器上需要一些程序…...

C++基础了解-03-C++变量类型

C变量类型 一、变量类型 变量其实只不过是程序可操作的存储区的名称。C 中每个变量都有指定的类型&#xff0c;类型决定了变量存储的大小和布局&#xff0c;该范围内的值都可以存储在内存中&#xff0c;运算符可应用于变量上。 变量的名称可以由字母、数字和下划线字符组成。…...

树莓派4b——通过mjpg-streamer使用摄像头

参考博文&#xff1a;(51条消息) 树莓派4b如何打开摄像头_树莓派打开摄像头_会飞的小东的博客-CSDN博客(51条消息) 树莓派4B &#xff08;系统版本11&#xff0c;bullseye&#xff09;更换清华源_树莓派更换清华源_ASSSSHION的博客-CSDN博客这个坑踩了我一星期&#xff0c;找各…...

MySQL运维篇之读写分离

04、读写分离 4.1、介绍 读写分离&#xff0c;简单地说是把对数据库的读和写操作分开&#xff0c;以对应不同的数据库服务器。主数据库提供写操作&#xff0c;从数据库提供读操作&#xff0c;这样能有效地减轻单台数据库的压力。 通过Mycat即可轻易实现上述功能&#xff0c;…...

windows程序最小化到托盘并显示提示信息

windows程序最小化到托盘并显示提示信息背景干货直接上代码解析控制窗口显示初始化托盘添加第一条消息更新界面结束啦背景 有些时候需要程序在最小化的时候可以看到程序进度&#xff0c;甚至需要完全关闭界面&#xff0c;只留下托盘显示&#xff0c;这篇文章就是在这个背景下诞…...

使字符串平衡的最少删除次数(简单动态规划)

给你一个字符串 s &#xff0c;它仅包含字符 a 和 b​​​​ 。 你可以删除 s 中任意数目的字符&#xff0c;使得 s 平衡 。当不存在下标对 (i,j) 满足 i < j &#xff0c;且 s[i] b 的同时 s[j] a&#xff0c;此时认为 s 是 平衡 的。 请你返回使 s 平衡 的 最少 删除次…...

linux网络广播使用

广播使用的特殊的IP地址: 最后一位是255时的IP地址是给广播预留的IP地址, 如:192.168.1.255 UDP服务器在广播数据时,数据报使用的地址不是UDP服务器地址,而是广播地址 如:UDP服务器地址是:192.168.1.110 UDP服务器广播数据时使用地址是:192.168.1.255 UDP数据包发送给交换机…...

Kubernetes源码学习

kubernetes源码剖析 1.下载和编译源码 go 1.18.3 kubernetes 1.24.2 centos 7.9 进入目录$GOPATH/src/k8s.io/kubernetes&#xff0c;执行以下命令即可全量构建&#xff0c;并且构建结果只包含linux平台的&#xff1a; KUBE_BUILD_PLATFORMSlinux/amd64 make all GOFLAGS…...

筑基九层 —— 指针详解

目录 前言&#xff1a; 指针详解 前言&#xff1a; 1.CSDN由于我的排版不怎么好看&#xff0c;我的有道云笔记比较美观&#xff0c;请移步有道云笔记 2.修炼必备 1&#xff09;入门必备&#xff1a;VS2019社区版&#xff0c;下载地址&#xff1a;Visual Studio 较旧的下载 -…...

内存清理、动画制作、CPU检测等五款实用软件推荐

人类与99%的动物之间最大差别在于是否会运用工具&#xff0c;借助好的工具&#xff0c;能提升几倍的工作效率。 1.内存清理软件——MemReduct MemReduct是一款内存清理软件&#xff0c;现在越来越多的软件由于硬件的普遍发展&#xff0c;对内存的使用都开始肆无忌惮起来&…...

RocketMQ 5.0 学习笔记

1. 需求 背景&#xff1a;业务需要&#xff0c;平台将使用rocketMQ来实现消息的发送与消费&#xff0c;替代redis的消息功能。 需要在搭建好rocketMQ平台后&#xff0c;进行研究和验证。 技术&#xff1a;Springboot RocketMQ5.0 使用场景&#xff1a;签到活动&#xff0c…...

796.子矩阵的和

输入一个 n行 m列的整数矩阵&#xff0c;再输入 q个询问&#xff0c;每个询问包含四个整数 x1,y1,x2,y2&#xff0c;表示一个子矩阵的左上角坐标和右下角坐标。 对于每个询问输出子矩阵中所有数的和。 输入格式 第一行包含三个整数 n&#xff0c;m&#xff0c;q。 接下来 n…...

【PySide6】信号(signal)和槽函数(slot),以及事件过滤器

说明 在PYQT中&#xff0c;父控件可以通过两种方式响应子控件的事件&#xff1a; 通过信号(signal)和槽函数(slot)机制连接子控件和父控件父控件可以通过设置eventFilter()方法来监听响应子控件的事件 一、信号(signal)和槽函数(slot) 示例 在PYQT中&#xff0c;每个组件都…...

canal admin管理端配置(二)

下载安装 下载地址&#xff1a; 下载解压即可 配置 修改canal.admin-1.1.5\conf\application.yml server:port: 8089 #端口根据是否冲突修改 spring:jackson:date-format: yyyy-MM-dd HH:mm:sstime-zone: GMT8spring.datasource:address: 192.0.16.12:3306#数据库ip和端口…...

Servlet 生命周期

Servlet的生命周期有四个阶段&#xff1a;加载并实例化、初始化、请求处理、销毁。主要涉及到的方法有init、service、doGet、doPost、destory等 加载并实例化 Servlet容器负责加载和实例化Servelt。当Servlet容器启动时&#xff0c;或者在容器检测到需要这个Servlet来响应第一…...

redis集群模式登陆

总结redis单机模式时&#xff0c;登陆redis的命令格式&#xff1a; ./redis-cli -h 地址 -p 端口redis集群模式时&#xff0c;登陆redis的命令格式&#xff1a; ./redis-cli -h 地址 -p 端口 -c举例1&#xff1a;redis单机模式下登陆rootubuntu:/usr/local/redis/redis-7.0.0/b…...

04-useMemo 、React.memo、useCallback

useMemo 、React.memo、useCallback 一、useMemo 基本用法 缓存数据&#xff0c;模拟 Vue 中的计算属性。 同样useMemo跟vue中component一样&#xff0c;也是有缓存的&#xff0c;会将结果缓存下来 import React, { useMemo, useState } from react;export default functio…...

windows下安装emqx Unable to load emulator DLL@if ===/ SET data_dir=“

1.报错内容 I:\0-software\02-emqx\emqx-5.0.19-windows-amd64\bin>emqx start Unable to load emulator DLL (I:\0-software\02-emqx\emqx-5.0.19-windows-amd64\erts-12.3.2.9\bin\beam.smp.dll) 此时不应有 SET。 I:\0-software\02-emqx\emqx-5.0.19-windows-amd64\bin&…...

Redis常见问题(未完待续)

Redis常见问题Redis为什么快 &#xff1f;Redis为什么快 &#xff1f; 根据官方数据&#xff0c;Redis 的 QPS 可以达到约 100000&#xff08;每秒请求数&#xff09;&#xff1b; 基于内存 对于磁盘数据库来说&#xff0c;首先要将数据通过 IO 操作读取到内存里再读取&#x…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

Unity3D中Gfx.WaitForPresent优化方案

前言 在Unity中&#xff0c;Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染&#xff08;即CPU被阻塞&#xff09;&#xff0c;这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案&#xff1a; 对惹&#xff0c;这里有一个游戏开发交流小组&…...

ssc377d修改flash分区大小

1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序

一、开发环境准备 ​​工具安装​​&#xff1a; 下载安装DevEco Studio 4.0&#xff08;支持HarmonyOS 5&#xff09;配置HarmonyOS SDK 5.0确保Node.js版本≥14 ​​项目初始化​​&#xff1a; ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

Matlab | matlab常用命令总结

常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...

蓝桥杯 冶炼金属

原题目链接 &#x1f527; 冶炼金属转换率推测题解 &#x1f4dc; 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V&#xff0c;是一个正整数&#xff0c;表示每 V V V 个普通金属 O O O 可以冶炼出 …...

QT3D学习笔记——圆台、圆锥

类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体&#xff08;对象或容器&#xff09;QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质&#xff08;定义颜色、反光等&#xff09;QFirstPersonC…...

C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)

名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...

iview框架主题色的应用

1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题&#xff0c;无需引入&#xff0c;直接可…...