当前位置: 首页 > 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…...

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

css实现圆环展示百分比,根据值动态展示所占比例

代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序

一、开发准备 ​​环境搭建​​&#xff1a; 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 ​​项目创建​​&#xff1a; File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...

最新SpringBoot+SpringCloud+Nacos微服务框架分享

文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的&#xff0c;根据Excel列的需求预估的工时直接打骨折&#xff0c;不要问我为什么&#xff0c;主要…...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

LRU 缓存机制详解与实现(Java版) + 力扣解决

&#x1f4cc; LRU 缓存机制详解与实现&#xff08;Java版&#xff09; 一、&#x1f4d6; 问题背景 在日常开发中&#xff0c;我们经常会使用 缓存&#xff08;Cache&#xff09; 来提升性能。但由于内存有限&#xff0c;缓存不可能无限增长&#xff0c;于是需要策略决定&am…...

省略号和可变参数模板

本文主要介绍如何展开可变参数的参数包 1.C语言的va_list展开可变参数 #include <iostream> #include <cstdarg>void printNumbers(int count, ...) {// 声明va_list类型的变量va_list args;// 使用va_start将可变参数写入变量argsva_start(args, count);for (in…...

C语言中提供的第三方库之哈希表实现

一. 简介 前面一篇文章简单学习了C语言中第三方库&#xff08;uthash库&#xff09;提供对哈希表的操作&#xff0c;文章如下&#xff1a; C语言中提供的第三方库uthash常用接口-CSDN博客 本文简单学习一下第三方库 uthash库对哈希表的操作。 二. uthash库哈希表操作示例 u…...