Unique Binary Search Trees -- LeetCode

2023-11-19

原题链接: http://oj.leetcode.com/problems/unique-binary-search-trees/
这道题要求可行的二叉查找树的数量,其实二叉查找树可以任意取根,只要满足中序遍历有序的要求就可以。从处理子问题的角度来看,选取一个结点为根,就把结点切成左右子树,以这个结点为根的可行二叉树数量就是左右子树可行二叉树数量的乘积,所以总的数量是将以所有结点为根的可行结果累加起来。写成表达式如下:
熟悉 卡特兰数的朋友可能已经发现了,这正是 卡特兰数的一种定义方式,是一个典型的动态规划的定义方式(根据其实条件和递推式求解结果)。所以思路也很明确了,维护量res[i]表示含有i个结点的二叉查找树的数量。根据上述递推式依次求出1到n的的结果即可。
时间上每次求解i个结点的二叉查找树数量的需要一个i步的循环,总体要求n次,所以总时间复杂度是O(1+2+...+n)=O(n^2)。空间上需要一个数组来维护,并且需要前i个的所有信息,所以是O(n)。代码如下:
public int numTrees(int n) {
    if(n<=0)
        return 0;
    int[] res = new int[n+1];
    res[0] = 1;
    res[1] = 1;
    for(int i=2;i<=n;i++)
    {
        for(int j=0;j<i;j++)
        {
            res[i] += res[j]*res[i-j-1];
        }
    }
    return res[n];
}
这种求数量的题目一般都容易想到用动态规划的解法,这道题的模型正好是 卡特兰数 的定义。当然这道题还可以用 卡特兰数 的通项公式来求解,这样时间复杂度就可以降低到O(n)。因为比较直接,这里就不列举代码了。
如果是求解所有满足要求的二叉树(而不仅仅是数量)那么时间复杂度是就取决于结果的数量了,不再是一个多项式的解法了,有兴趣的朋友可以看看 Unique Binary Search Trees II
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

Unique Binary Search Trees -- LeetCode 的相关文章

  • 算法:双指针

    双指针 双指针是一种思想或一种技巧并不是特别具体的算法 具体就是用两个变量动态存储两个结点 来方便我们进行一些操作 通常用在线性的数据结构中 特别是链表类的题目 经常需要用到两个或多个指针配合来记忆链表上的节点 完成某些操作 常见的双指针方
  • 白盒测试相关的一些知识

    在白盒测试中 可以使用各种测试方法进行测试 下面这篇文章 可能比较枯燥 如果不乐意读 可以先收藏 如果在你的工作中真遇到白盒测试的话 可以回过头再来看看 还是值得读一读 一般来说 白盒测试时要考虑以下5个问题 1 测试中尽量先用自动化工具来
  • 数据结构之链表与线性表

    数据结构之链表与线性表 线性表 顺序线性表 顺序表 顺序线性表 使用数组实现 一组地址连续的存储单元 数组大小有两种方式指定 一是静态分配 二是动态扩展 优点 随机访问特性 查找O 1 时间 存储密度高 逻辑上相邻的元素 物理上也相邻 缺点
  • 数据结构----链式栈

    目录 前言 链式栈 操作方式 1 存储结构 2 初始化 3 创建节点 4 判断是否满栈 5 判断是否空栈 6 入栈 7 出栈 8 获取栈顶元素 9 遍历栈 10 清空栈 完整代码 前言 前面我们学习过了数组栈的相关方法 链接 线性表 栈 栈
  • 亚利桑那州立大学周纵苇:研习 U-Net ——现有的分割网络创新

    雷锋网AI研习社按 经典的 Encoder Decoder 结构在目标分割问题中展现出了举足轻重的作用 然而这样一个相对固定的框架使得模型在感受野大小和边界分割精度两方面很难达到兼顾 本次公开课 讲者以 U Net 为案例分析 总结现有的分
  • 数据结构之图的两种遍历实现(C语言版)

    上一期文章分享完了图的两种遍历方式 也是两种很重要的算法 DFS和BFS 这两种算法的应用和重要性我就不多说了 内行的人懂的都懂 今天这文章重要就是来上机实现这两种算法 又由于这两种算法都可以由邻接矩阵和邻接表来表示 博主分享的代码都是上机
  • 以太坊系列之十五: 以太坊数据库

    以太坊数据库中都存了什么 以太坊使用的数据库是一个NOSQL数据库 是谷歌提供的开源数据leveldb 这里尝试通过分析以太坊数据库存储了什么来分析以太坊可能为我们提供哪些关于区块链的API 存储内容 NOSQL是一个key value数据
  • 数据结构——计算节点个数和二叉树高度(C语言版)

    摘自 数据结构 计算节点个数和二叉树高度 C语言版 作者 正弦定理 发布时间 2020 12 12 23 27 09 网址 https blog csdn net chinesekobe article details 111086664
  • 算法问题实战策略

    算法问题实战策略 基本信息作者 韩 具宗万 译者 崔盛一出版社 人民邮电出版社ISBN 9787115384621上架时间 2015 2 4出版日期 2015 年3月开本 16开页码 738版次 1 1 内容简介 算法问题实战策略 本书收录
  • 算法学习——贪心算法之币种统计

    算法描述 币种统计 单位给每一位员工发工资 精确到元 为了保证不临时换零钱 使得每个员工取款的张数最少 在取工资前统计所有员工所需要的各种票面的张数 约定票种为100 50 20 10 5 2 1元 并验证币种统计是否正确 算法思路 算法描
  • Linux 内核中的 Device Mapper 机制

    Linux 内核中的 Device Mapper 机制 尹 洋 在读博士生 尹洋 中科院计算所国家高性能计算机工程技术研究中心的在读博士生 主要从事服务部署和存储资源管理以及Linux块设备一级的开发和研究工作 简介 本文结合具体代码对 L
  • 时间复杂度+常见复杂度解释

    前言 算法的效率 虽然计算机能快速的完成运算处理 但实际上 它也需要根据输入数据的大小和算法效率来消耗一定的处理器资源 要想编写出能高效运行的程序 我们就需要考虑到算法的效率 算法的效率主要由以下两个复杂度来评估 时间复杂度 评估执行程序所
  • 机器学习算法GBDT的面试要点总结-上篇

    1 简介 gbdt全称梯度提升决策树 在传统机器学习算法里面是对真实分布拟合的最好的几种算法之一 在前几年深度学习还没有大行其道之前 gbdt在各种竞赛是大放异彩 原因大概有几个 一是效果确实挺不错 二是即可以用于分类也可以用于回归 三是可
  • 【试题】排列组合

    在写一个远程的代码 如果本地有M个显示器 远程有N个显示器 M lt N 依据分辨率 显示器刷新频率等要求 需要对远程的N个显示器进行最佳分辨率修改 之后 需要从N个远程显示器中选择M个 跟本地显示器进行一对一的匹配 即从 A N M N
  • 插入排序超详解释,一看就懂

    目录 一 插入排序的相关概念 1 基本思想 2 基本操作 有序插入 二 插入排序的种类 三 直接插入排序 1 直接插入排序的过程 顺序查找法查找插入位置 2 使用 哨兵 直接插入排序 四 直接插入排序算法描述 五 折半插入排序 1 查找插入
  • 索引优化之Explain 及慢查询日志

    索引 本质是数据结构 简单理解为 排好序的快速查找数据结构 以索引文件的形式存储在磁盘中 目的 提高数据查询的效率 优化查询性能 就像书的目录一样 优势 提高检索效率 降低IO成本 排好序的表 降低CPU的消耗劣势 索引实际也是一张表 该表
  • Leetcode2661. 找出叠涂元素

    Every day a Leetcode 题目来源 2661 找出叠涂元素 解法1 哈希 题目很绕 理解题意后就很简单 由于矩阵 mat 中每一个元素都不同 并且都在数组 arr 中 所以首先我们用一个哈希表 hash 来存储 mat 中每
  • Leetcode1094. 拼车

    Every day a Leetcode 题目来源 1094 拼车 解法1 差分数组 对于本题 设 a i 表示车行驶到位置 i 时车上的人数 我们需要判断是否所有 a i 都不超过 capacity trips i 相当于把 a 中下标从
  • 从源码角度来谈谈 HashMap

    HashMap的知识点可以说在面试中经常被问到 是Java中比较常见的一种数据结构 所以这一篇就通过源码来深入理解下HashMap 1 HashMap的底层是如何实现的 基于JDK8 1 1 HashMap的类结构和成员 HashMap继承
  • 高精度运算合集,加减乘除,快速幂,详细代码,OJ链接

    文章目录 零 前言 一 加法 高精度加法步骤 P1601 A B 二 减法 高精度减法步骤

随机推荐

  • c++系列 —— 移动构造函数

    往期地址 c 系列一 c 的封装 c 系列二 c 的继承 c 系列三 继承和多态特性 c 系列四 运算符重载 c 系列五 静态成员和静态类 c 系列六 友元函数和友元类 c 系列七 STL编程之模板template c 系列八 STL编程之
  • 事件循环机制分享

    Event Loop 即事件循环 是JavaScript或Node为解决单线程代码执行不阻塞主进程一种机制 也就是我们所说的异步原理 要了解事件循环机制首先要了解进程 线程 宏任务 微任务 进程 Process 是计算机中的程序关于某数据集
  • 【STM32F0】Keil 查看局部变量显示

    现象 在进行STM32F0开发的时候出现了 调试代码 添加变量Watch时 显示not in scope 处理方式 因为代码开了优化的处理 把优化改到Level0 就可以解决问题
  • 【深度学习】ResNet残差网络 ResidualBlock残差块实现(pytorch)

    文章目录 前言 一 卷积的相关计算公式 复习 二 残差块ResidualBlock复现 pytorch 三 残差网络ResNet18复现 pytorch 四 直接调用方法 五 具体实践 ResNet进行猫狗分类 六 可能报错 6 1 Typ
  • C语言学习:用C语言实现简单的计算器

    用C语言编写一个简单的可以进行加减乘除运算混合运算的计算器的方法 include
  • 解决Chrome浏览器左键双击没反应,无法启动

    打开任务管理器Ctrl aLT DEL 或是在任务栏图标空白处右击 解决Chrome浏览器点击没反应 2 然后 在进程列中 点击表头排序 之后找到chrome exe进程 解决Chrome浏览器点击没反应 3 右击选择后 结束进程 解决Ch
  • rpm -ivh oracle-xe-11.2.0-1.0.x86_64.rpm

    update install the packages for libaio bc and flex view plaincopy to clipboardprint root localhost yum install libaio bc
  • ECharts社区里面的gallery在哪里?ECharts gallery新地址

    学习echarts map发现echarts 社区里面没有gallery了 找了好久 终于找到了 这是新地址 https www makeapie com explore html 赶紧收藏
  • 软件测试用例——三角形

    1 题目 输入三个数a b c分别作为三边的边长构成三角形 通过程序判定所构成的三角形是一般三角形 等腰三角形还是等边三角形时 请为该程序设计测试用例 用等价类划分方法 分析 得出测试用例 用判定表法 条件 1 2 3 4 5 6 7 8
  • 嵌入式数据库sqlite3【进阶篇】-如何用C语言操作sqlite3,一文搞懂

    sqlite3编程接口非常多 对于初学者来说 我们暂时只需要掌握常用的几个函数 其他函数自然就知道如何使用了 数据库 本篇假设数据库为my db 有数据表student no name score 4 一口Linux 89 0 创建表格语句
  • Keil MDK报错:Browse information of one or more files is not available----全面的解决方法。

    最近玩stm32遇到一个BUG 报错内容如图 图片来自网络 感谢网友提供图片 如有侵权 请私聊以便删除 本人的报错情况跟这个一模一样 不同的是我的报错文件要多一些 以下是解决方法 方法一 1 点击魔术棒 2 在Output界面中勾选Brow
  • Linux文件系统是怎么工作的?

    本文已收录GitHub 更有互联网大厂面试真题 面试攻略 高效学习资料等 磁盘为系统提供了最基本的持久化存储 文件系统则在磁盘的基础上 提供了一个用来管理文件的树状结构 那么 磁盘和文件系统是怎么工作的呢 又有哪些指标可以衡量它们的性能呢
  • Selenium+WebDriver 各浏览器驱动下载与使用

    Selenium python WebDriver驱动下载与使用 Firefox 火狐 浏览器驱动 Chrome google 浏览器驱动 IE浏览器驱动 Microsoft Edge EdgeHTML 浏览器驱动 Microsoft Ed
  • linux send recv函数详解

    2009 05 10 21 55 int send SOCKET s const char FAR buf int len int flags 不论是客户还是服务器应用程序都用send函数来向TCP连接的另一端发送数据 客户程序一般用sen
  • paddleseg人像分割windows下实现与证照自动生成实现

    paddleseg人像分割windows下实现与证照自动生成实现 近日研究了一下用人脸识别作自动证件照生成 刚开始以为很简单不就是识别出人脸 然后按比例切出 这一步当然很简单 结果看了各种证件照 原来要去除背景的 这样一来原来简单的事搞得复
  • 虚拟计算技术

    虚拟计算的本质是资源共享 P2P计算 云计算 网格计算 普适计算都属于虚拟计算 一 概述 虚拟计算 Virtual Computing 的本质是资源共享 虚拟计算技术不仅能使人们更有效地共享现有的资源 而且能通过重组等手段 为人们提供更多
  • 这一次,我顿悟了

    大家好 我是苍何 昨晚和编程导航 星球嘉宾也是我的引路人闫 y n 小林大佬 畅聊了 4 个 小时 至今内心还是久久不能平静 小林和我一样是跨界转行 他是医学院毕业 大二开始自学编程 并写博客记录 迄今有 30 万编程学习者关注 毕业后在某
  • OSI七层模型以及各层的作用

    OSI七层模型 OSI七层模型包括 应用层 表示层 会话层 传输层 网络层 数据链路层 物理层 具体作用 物理层 主要定义物理设备标准 如网线的接口类型 各种传输介质的传输速率等 主要作用是传输bit流 主要设备 集线器 数据链路层 主要将
  • HMI智能串口屏——在STM32开发板上的实战应用及其详解

    HMI智能串口屏 在STM32开发板上的实战应用及其详解 一 HMI智能串口屏使用步骤 二 附录 一 HMI智能串口屏使用步骤 安装USART HMI软件 一般买的串口屏里面 商家送的资料里面都有改该软件 打开软件 并点击左上角的 新建 选
  • Unique Binary Search Trees -- LeetCode

    原题链接 http oj leetcode com problems unique binary search trees 这道题要求可行的二叉查找树的数量 其实二叉查找树可以任意取根 只要满足中序遍历有序的要求就可以 从处理子问题的角度来