java数据结构与算法刷题-----LeetCode96. 不同的二叉搜索树

java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完):https://blog.csdn.net/grd_java/article/details/123063846

很多人觉得动态规划很难,但它就是固定套路而已。其实动态规划只不过是将多余的步骤,提前放到dp数组中(就是一个数组,只不过大家都叫它dp),达到空间换时间的效果。它仅仅只是一种优化思路,因此它目前的境地和线性代数一样----虚假的难。

  1. 想想线性代数,在国外留学的学生大多数不觉得线性代数难理解。但是中国的学生学习线性代数时,完全摸不着头脑,一上来就是行列式和矩阵,根本不知道这玩意是干嘛的。
  2. 线性代数从根本上是在空间上研究向量,抽象上研究线性关系的学科。人家国外的教科书都是第一讲就帮助大家理解研究向量和线性关系。
  3. 反观国内的教材,直接把行列式搞到第一章。搞的国内的学生在学习线性代数的时候,只会觉得一知半解,觉得麻烦,完全不知道这玩意学来干什么。当苦尽甘来终于理解线性代数时干什么的时候,发现人家国外的教材第一节就把这玩意讲清楚了。你只会大骂我们国内这些教材,什么狗东西(以上是自己学完线性代数后的吐槽,我们同学无一例外都这么觉得)。

而我想告诉你,动态规划和线性代数一样,我学完了才知道,它不过就是研究空间换时间,提前将固定的重复操作规划到dp数组中,而不用暴力求解,从而让效率极大提升。

  1. 但是网上教动态规划的兄弟们,你直接给一个动态方程是怎么回事?和线性代数,一上来就教行列式和矩阵一样,纯属恶心人。我差不多做了30多道动态规划题目,才理解,动态方程只是一个步骤而已,而这已经浪费我很长时间了,我每道题都一知半解不理解,过程及其痛苦。最后只能重新做。
  2. 动态规划,一定是优先考虑重复操作与dp数组之间的关系,搞清楚后,再提出动态方程。而你们前面步骤省略了不讲,一上来给个方程,不是纯属扯淡吗?
  3. 我推荐研究动态规划题目,按5个步骤,从上到下依次来分析
  1. DP数组及下标含义
  2. 递推公式
  3. dp数组初始化
  4. 数组遍历顺序(双重循环及以上时,才考虑)
  5. dp数组打印,分析思路是否正确(相当于做完题,检查一下)

在这里插入图片描述

先理解题目细节

在这里插入图片描述

  1. 二叉搜索树,左子树都比根结点小,右子树都比根结点大,左右子树又各是一个二叉搜索树。而如果给我们一个数3.那么也就是让我们用①、②、③这3个结点构成二叉搜索树。
  1. 如果我们用①作根结点,那么②和③都大于①,只能在它右边,用②作根结点,那么①小于②只能放在左边,③大于②只能放在右边。
  2. 那么左右分多少个结点呢?我们发现,当我们截取②作为根,①、②、③这个序列,它左边的都小于它所有最终都会在它左边,同理右边的都在它右边。
  3. 令j = ②表示以②为根,共有i = 3个结点,那么②左边的,也就是j-1个 = 2-1 = 1个元素会被放在左子树。②右边的,也就是i - j= 3-2 = 1个元素会被放在右边
  1. dp数组存储:给你i个结点,有几种摆放方式可以构成二叉搜索树。下标i表示当前给我们多少结点可以用于构成二叉搜索树。
  2. i = 0时,只有一种方法组成二叉搜索树,就是什么都不摆,故,dp[0] = 1
  3. i = 1时,只有一个结点①组成二叉搜索树,只有一个结点,只有一种摆放方式,故,dp[1] = 1.
  4. i = 2时,有两个结点①和②可以组成二叉搜索树,所以我们有两种思路
  1. ①作为根结点,记为j,左边有j-1个元素比它小,右边有i - j个元素比它大
  2. ②作为根结点同理。
    在这里插入图片描述
  3. 而它的左右子树,有几个元素呢,你会发现一定比当前的i值小。都不大于2. 那么它们各有几种摆放方式呢?前面的dp数组构造时,已经考虑过了i = 0时,dp[0]=1, i=1时,dp[1]=1.两个相乘,就是以j为根的i个元素可以构造的二叉搜索树数量。最后将所有不同根结点情况相加即可。
解题思路
  1. 暴力求解的思想,就是利用回溯算法,不撞南墙不回头。
  2. 但是如果我们预先将其存储到dp数组,就可以直接通过dp, 获取数据,而不用枚举。典型的动态规划题目
动态规划思考5步曲
  1. DP数组及下标含义
  1. 我们要求出的是给你i个结点,可以构造出多少种不同二叉搜索树。显然dp数组中存储的就是i个结点,可以构造出多少种不同二叉搜索树。要求出谁的?显然是求出,i个结点可构造二叉搜索树数量。那么下标就是代表用几个结点构造二叉搜索树,很显然,只需要一个下标,也就是一维数组。
  1. 递推公式
  1. 因为0个结点只有一种摆放方式,1个结点也只有一种摆放方式,所以:F(0) = F(1) = 1;
  2. 对于其它数i,我们可以通过指定不同根结点,构造多种不同二叉搜索树。我们用j来表示当前用哪个结点代表根结点。例如i = 3,有1,2,3这3个数可以构造,当我们选其中一个数,例如1.那么必须保证左边都小于它,右边都大于它。也就是2和3必须在它右边,而没有比1小的数,因此左子树为空
  3. 因此,当我们选中j作为根结点后,它左边有j-1个数,右边有i-j个数。左边j-1个数可以构造dp[j-1]个不同二叉搜索树。右边i-j个数可以构造dp[i-j]个二叉搜索树。
  4. 当我们j的右边固定不变时,左边每变一次,都是一课全新二叉搜索树。同理,左边不变,右边变,也一样。所以他俩是相乘的关系。也就是以j为根节点,有dp[j-1] * dp[i-j]种不同二叉搜索树。
  5. 而当i = 3,我们有①,②,③这3个结点,j可以选择任意一个作为根结点,所以每种情况都得考虑,因此j = ① 和 j = ② 和 j = ③这3种情况的和才是dp[i]的值。故:F[i] = F[1-1] * F[i-1] + F[2-1] * F[i-2] + F[3-1] * F[i-3] + … + F[i-1] * F[i-i]
  1. dp数组初始化

在这里插入图片描述

  1. 数组遍历顺序(单重循环,无需考虑遍历顺序,一共就一维,哪里来的谁先谁后)
  2. 打印dp数组(自己生成dp数组后,将dp数组输出看看,是否和自己预想的一样。)

在这里插入图片描述

代码:时间复杂度O(n).空间复杂度O(n)

在这里插入图片描述

class Solution {public int numTrees(int n) {int dp[] = new int[n+1];//需要0到n的下标范围,因此需要n+1个元素dp[0] = dp[1] = 1;//0个结点和1个结点,只有一种摆放方式for(int i = 2;i<=n;i++){//剩下的,需要将不同结点作为根结点的情况加起来for(int j = 1;j<=i;j++){//j表示当前用谁当根结点dp[i]+=dp[j-1]*dp[i-j];//j当根结点,左边有j-1个元素,右边有i-j个元素}}return dp[n];//返回n个结点可以构成多少种二叉搜索树}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/239381.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

OceanBase 4.2特性解读:Show Trace全链路跟踪,助力快速问题定位与精准诊断

在分布式数据库环境下&#xff0c;慢 SQL 诊断是运维人员面临的一大挑战。在无法及时发现问题根本原因的情况下&#xff0c;可能会严重影响用户体验&#xff0c;甚至会导致业务服务不可用。相对于单机数据库&#xff0c;分布式数据库系统涉及多个节点、多组件的协同工作&#x…

推荐VSCODE插件:为`package.json`添加注释信息

众所周知&#xff0c;JSON文件是不支持注释的&#xff0c;除了JSON5/JSONC之外&#xff0c;我们在开发项目特别是前端项目时&#xff0c;大量会用到JSON文件&#xff0c;特别是在编写package.json中的scripts时&#xff0c;由于缺少注释,当有大量的命令脚本时&#xff0c;就有了…

【Docker】在容器中管理数据数据卷挂载以及宿主机目录挂载

&#x1f389;&#x1f389;欢迎来到我的CSDN主页&#xff01;&#x1f389;&#x1f389; &#x1f3c5;我是平顶山大师&#xff0c;一个在CSDN分享笔记的博主。&#x1f4da;&#x1f4da; &#x1f31f;推荐给大家我的博客专栏《【Docker】在容器中管理数据》。&#x1f3af…

Halcon提取亚像素轮廓edges_sub_pix算子

Halcon提取亚像素轮廓edges_sub_pix算子 最常用的提取亚像素轮廓的算子是edges_sub_pix算子&#xff0c;该算子同样提供了大量的提取方法&#xff0c;只需要在Filter 参数中设置方法的名字&#xff0c;就可以完成边缘的提取。该算子的输入是灰度图像&#xff0c;输出是XLD轮廓…

1491. 去掉最低工资和最高工资后的工资平均值

1491. 去掉最低工资和最高工资后的工资平均值 class Solution {public double average(int[] salary) {Arrays.sort(salary);salary[0] 0;for(int i 1;i < salary.length - 1;i){salary[0] salary[i];}return salary[0] * 1.0 / (salary.length - 2);} }

【C++】vector的使用及模拟实现

目录 一、vector的介绍及使用1.1 介绍vector1.2 vector的使用1.2.1 构造1.2.2 遍历访问1.2.3 容量空间1.2.4 增删查改 二、vector的模拟实现2.1 成员变量2.2 迭代器相关函数2.3 构造-析构-赋值重载2.3.1 无参构造2.3.2 有参构造12.3.3 有参构造22.3.4 拷贝构造2.3.5 赋值重载2.…

Docker部署Jira、Confluence、Bitbucket、Bamboo、Crowd,Atlassian全家桶

文章目录 省流&#xff1a;注意&#xff1a;解决方案&#xff1a; 1.docker-compose文件2.其他服务都正常启动&#xff0c;唯独Bitbucket不行。日志错误刚启动时候重启后查询分析原因再针对第一点排查看样子是安装的bitbucket和系统环境有冲突问题&#xff1f; 结论&#xff1a…

Ovtio不同版本下载

关注 M r . m a t e r i a l , \color{Violet} \rm Mr.material\ , Mr.material , 更 \color{red}{更} 更 多 \color{blue}{多} 多 精 \color{orange}{精} 精 彩 \color{green}{彩} 彩&#xff01; 主要专栏内容包括&#xff1a; †《LAMMPS小技巧》&#xff1a; ‾ \textbf…

VTK开发调试环境下载(VTK开发环境一步到位直接开发,无需自己配置编译 VS2017+Qt5.12.10+VTK)

一、无与伦比的优势 直接下载代码就可以调试的VTK代码仓库。 二、资源制作原理 这个资源根据VTK源码 编译出动态库文件 pdb lib dll 文件&#xff08; x64 debug &#xff09; 并将这两者同时放在一个代码仓库里&#xff0c;下载就能用。 三、使用方法&#xff08;vtk-so…

武理多媒体信息共享平台的架构设计与实现

✍✍计算机编程指导师 ⭐⭐个人介绍&#xff1a;自己非常喜欢研究技术问题&#xff01;专业做Java、Python、微信小程序、安卓、大数据、爬虫、Golang、大屏等实战项目。 ⛽⛽实战项目&#xff1a;有源码或者技术上的问题欢迎在评论区一起讨论交流&#xff01; ⚡⚡ Java实战 |…

Mantle: A Programmable Metadata Load Balancer for the Ceph File System——论文泛读

SC 2015 Paper 元数据论文阅读汇总 问题 优化Ceph的元数据局部性和负载平衡。 现有方法 提高元数据服务性能的最常见技术是在专用的元数据服务器&#xff08;MDS&#xff09;节点之间平衡负载 [16, 25, 26, 21, 28]。常见的方法是鼓励独立增长并减少通信&#xff0c;使用诸…

使用 Picocli 开发 Java 命令行,5 分钟上手

大家好&#xff0c;我是鱼皮&#xff0c;对不会前端的同学来说&#xff0c;开发 命令行工具 是一种不错的展示系统功能的方式。在 Java 中开发命令行工具也很简单&#xff0c;使用框架&#xff0c;几分钟就能学会啦~ Picocli 入门 Picocli 是 Java 中个人认为功能最完善、最简单…

NAS入门(学习笔记)

文章目录 AutoMLNAS初期NAS当前NAS框架One-Shot NAS权重共享策略 Zero-Shot NASZen-NASNASWOTEPENAS 参考资料 AutoML 深度学习使特征学习自动化 AutoML 使深度学习自动化 自动化机器学习 (automated machine learning) 是一种自动化的数据驱动方法, 并做出一系列决策。 按…

【Docker】网络模式➕自定义网络

&#x1f973;&#x1f973;Welcome 的Huihuis Code World ! !&#x1f973;&#x1f973; 接下来看看由辉辉所写的关于Docker的相关操作吧 目录 &#x1f973;&#x1f973;Welcome 的Huihuis Code World ! !&#x1f973;&#x1f973; 一.Docker网络模式的介绍 二. 网桥模…

Server/PC 稳定性测试(Windows)

Server/PC 稳定性测试 1. CPU - 中央处理器1.1 CPU稳定性1.2 CPU温度 2. Memory - 内存2.1 内存性能 3. DISK - 硬盘3.1 HDD - 机械硬盘机械硬盘转速详解监测工具 3.2 SSD - 固态硬盘监测工具 4. 使用时长cpu能用多久&#xff1f;主板能用多久&#xff1f;内存能用多久&#xf…

博后期间各种计划

博后期间各种计划&#xff1a; &#xff08;1&#xff09;国家自然科学基金&#xff08;青年项目&#xff09;、&#xff08;2&#xff09;博士后创新人才支持计划&#xff08;23年新改革&#xff1a;28w*2生活补助经费8w科研启动经费&#xff1b;每年资助400多人&#xff1b;…

Ansible-剧本与变量

对于运维小伙伴来讲&#xff0c;Ansible并不陌生&#xff0c;配置简单&#xff0c;上手容易&#xff0c;只要掌握几个基本的模块就可以解决好多运维中重复的事&#xff0c;但是对于处理更为高级的功能和更大、更复杂的项目时&#xff0c;管理和维护Ansible Playbook或高效使用将…

解决MPICH的GPU初始化失败:一次深入探索

今天来分享“MPICH&#xff1a;MPII_Init_thread(222): gpu_init failed”这个问题的解决方式 文章目录 前言问题原因解决方案 前言 如果在安装MPICH的时候没有注意要一些选项&#xff0c;那么当使用mpicxx mpi_send.cpp -o send && mpirun -n 2 ./send进行编译输出的…

C++ 之LeetCode刷题记录(十一)

&#x1f604;&#x1f60a;&#x1f606;&#x1f603;&#x1f604;&#x1f60a;&#x1f606;&#x1f603; 开始cpp刷题之旅。 向耗时0s前进。 67. 二进制求和 给你两个二进制字符串 a 和 b &#xff0c;以二进制字符串的形式返回它们的和。 示例 1&#xff1a; 输入…

最新AI绘画Midjourney绘画提示词Prompt大全

一、Midjourney绘画工具 SparkAi创作系统是基于ChatGPT进行开发的Ai智能问答系统和Midjourney绘画系统&#xff0c;支持OpenAI-GPT全模型国内AI全模型。本期针对源码系统整体测试下来非常完美&#xff0c;可以说SparkAi是目前国内一款的ChatGPT对接OpenAI软件系统。那么如何搭…