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

面试热题(不同的二分搜索树)

给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。

 

       经典的面试题,这部分涉及了组合数学中的卡特兰数,如果对其不清楚的同学可以去看我以前的博客卡特兰数

今天用记忆化搜索以及动态规划进行讲解

  • 记忆化搜索
    //维护一个记忆化搜素int[][] memo;public int numTrees(int n) {memo=new int[n+1][n+1];return  count(1,n);}public int count(int left,int right){//单节点,直接返回1if(left>=right){return 1;}if(memo[left][right]!=0){return memo[left][right];}int res=0;//遍历区间内的每一个节点,都作为根节点的情况for(int mid=left;mid<=right;mid++){int l=count(left,mid-1);int r=count(mid+1,right);res+=l*r;}memo[left][right]=res;return res;}
  • 动态规划
   public int numTrees(int n) {//先创建一个存储的数组int[] dp=new int[n+1];dp[0]=1;//节点可能存储的位置for (int i =1; i <=n; i++) {//左边节点可能存储的个数for (int j = 0; j<i; j++) {//计算出总种类  dp[j]是左树的节点个数 dp[i-j-1]是右树的节点个数dp[i]+=dp[j]*dp[i-j-1];}}return dp[n];}

相关文章:

面试热题(不同的二分搜索树)

给你一个整数 n &#xff0c;求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种&#xff1f;返回满足题意的二叉搜索树的种数。 经典的面试题&#xff0c;这部分涉及了组合数学中的卡特兰数&#xff0c;如果对其不清楚的同学可以去看我以前的博客卡特兰数 …...

MybatisPlus整合p6spy组件SQL分析

目录 p6spy java为什么需要 如何使用 其他配置 p6spy p6spy是一个开源项目&#xff0c;通常使用它来跟踪数据库操作&#xff0c;查看程序运行过程中执行的sql语句。 p6spy将应用的数据源给劫持了&#xff0c;应用操作数据库其实在调用p6spy的数据源&#xff0c;p6spy劫持到…...

项目实战 — 博客系统③ {功能实现}

目录 一、编写注册功能 &#x1f345; 1、使用ajax构造请求&#xff08;前端&#xff09; &#x1f345; 2、统一处理 &#x1f384; 统一对象处理 &#x1f384; 保底统一返回处理 &#x1f384; 统一异常处理 &#x1f345; 3、处理请求 二、编写登录功能 &#x1f345; …...

卷积神经网络全解:(AlexNet/VGG/ GoogLeNet/LeNet/ResNet/卷积/激活/池化/全连接)、现代卷积神经网络、经典卷积神经网络

CNN&#xff0c;卷积神经网络&#xff0c;Convolution Neural Network 卷积计算公式&#xff1a;N &#xff08;W-F2p&#xff09;/s1 这个公式每次都得看看&#xff0c;不能忘 1 经典网络 按照时间顺序 1.1 LeNet LeNet是 Yann LeCun在1998年提出&#xff0c;用于解决手…...

WDM 模型(Windows Driver Model)简述

WDM 模型(Windows Driver Model) 是微软公司为 Windows98 和 Windows2000 的驱动程序设计的一种架构&#xff0c;在 WDM 驱动程序模型中&#xff0c;每个硬件设备 至少有两个驱动程序。其中一个为功能驱动程序&#xff0c;它了解硬件工作的所有细节&#xff0c;负 责初始化 …...

【算法刷题之数组篇(1)】

目录 1.leetcode-59. 螺旋矩阵 II&#xff08;题2.题3相当于二分变形&#xff09;2.leetcode-33. 搜索旋转排序数组3.leetcode-81. 搜索旋转排序数组 II(与题目2对比理解)&#xff08;题4和题5都是排序双指针&#xff09;4.leetcode-15. 三数之和5.leetcode-18. 四数之和6.leet…...

【数据挖掘】使用 Python 分析公共数据【01/10】

一、说明 本文讨论了如何使用 Python 使用 Pandas 库分析官方 COVID-19 病例数据。您将看到如何从实际数据集中收集见解&#xff0c;发现乍一看可能不那么明显的信息。特别是&#xff0c;本文中提供的示例说明了如何获取有关疾病在不同国家/地区传播速度的信息。 二、准备您的…...

html怎么插入视频?视频如何插入页面

html怎么插入视频&#xff1f;视频如何插入页面 HTML 的功能强大&#xff0c;基本所有的静态效果都可以在此轻松呈现&#xff0c;各种视频网站内有大量的视频内容&#xff0c;本篇文章教你如何在 html 中插入视频 代码如下&#xff1a; <!DOCTYPE html> <html> …...

游戏服务端性能测试

导语&#xff1a;近期经历了一系列的性能测试&#xff0c;涵盖了Web服务器和游戏服务器的领域。在这篇文章中&#xff0c;我将会对游戏服务端所做的测试进行详细整理和记录。需要注意的是&#xff0c;本文着重于记录&#xff0c;而并非深入的编程讨论。在这里&#xff0c;我将与…...

【使用Zookeeper当作注册中心】自己定制负载均衡常见策略

自己定制负载均衡常见策略 一、前言随机&#xff08;Random&#xff09;策略的实现轮询&#xff08;Round Robin&#xff09;策略的实现哈希&#xff08;Hash&#xff09;策略 一、前言 大伙肯定知道&#xff0c;在分布式开发中&#xff0c;目前使用较多的注册中心有以下几个&…...

设计模式十七:迭代器模式(Iterator Pattern)

迭代器模式&#xff08;Iterator Pattern&#xff09;是一种行为型设计模式&#xff0c;它提供了一种访问聚合对象&#xff08;例如列表、集合、数组等&#xff09;中各个元素的方法&#xff0c;而无需暴露其内部表示。迭代器模式将遍历元素和访问元素的责任分离开来&#xff0…...

Python制作爱心并打包成手机端可执行文件

前言 本文是想要将python代码打包成在手机上能执行的文件 尝试了几个库&#xff0c; 有这也那样的限制&#xff0c;最终还是选了BeeWare 环境&#xff1a;python3.7.x 开始 找到打包有相关工具os-android-apk-builder&#xff0c;buildozer&#xff0c;cx_Freeze&#xff…...

使用docker-compose.yml快速搭建开发、部署环境(nginx、tomcat、mysql、jar包、各种程序)以及多容器通信和统一配置

目录 docker-compose语法&#xff08;更多说明可查看下面代码&#xff09;imagehostnamecontainer_namevolumesnetworks yml文件的使用启动停止 开发环境&#xff08;这里以python为例&#xff09;部署环境nginxmysqltomcatjar包打包后的可执行程序 常见问题与解决方案多个容器…...

管理类联考——逻辑——真题篇——按知识分类——汇总篇——二、论证逻辑——支持加强——第三节——分类3——类比题干支持

文章目录 第三节 支持加强-分类3-类比题干支持真题(2017-28)-支持加强-正面支持-表达“确实如此”真题(2017-36)-支持加强-正面支持-表达“确实如此”真题(2017-39)-支持加强-正面支持-方法有效或方法可行,但多半不选择方法无恶果真题(2017-50)-支持加强真题(2018-2…...

搜索旋转排序数组

整数数组 nums 按升序排列&#xff0c;数组中的值 互不相同 。 在传递给函数之前&#xff0c;nums 在预先未知的某个下标 k&#xff08;0 < k < nums.length&#xff09;上进行了 旋转&#xff0c;使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nums[1], …, …...

Steam搬砖项目:最长久稳定的副业!

项目应该大家都有听说话&#xff0c;但是细节问题&#xff0c;如何操作可能有些不是很清楚&#xff0c;今天在这里简单分享一下。 这个Steam搬砖项目主要赚钱汇率差和价值差&#xff0c;是一个细分领取的小项目。 不用引流&#xff0c;时间也是比较自由的&#xff0c;你可以兼…...

最小化安装移动云大云操作系统--BCLinux-R8-U8-Server-x86_64-230802版

CentOS 结束技术支持&#xff0c;转为RHEL的前置stream版本后&#xff0c;国内开源Linux服务器OS生态转向了开源龙蜥和开源欧拉两大开源社区&#xff0c;对应衍生出了一系列商用Linux服务器系统。BC-Linux V8.8是中国移动基于龙蜥社区Anolis OS 8.8版本深度定制的企业级X86服务…...

神经网络基础-神经网络补充概念-05-导数

概念 导数是微积分中的一个概念&#xff0c;用于描述函数在某一点的变化率。在数学中&#xff0c;函数的导数表示函数值随着自变量的微小变化而产生的变化量&#xff0c;即斜率或变化率。 假设有一个函数 f(x)&#xff0c;其中 x 是自变量&#xff0c;y f(x) 是因变量。函数…...

kubernetes — 安装Ingress

1、 Ingress 1、安装-Nginx-Ingress kubectl apply -f https://raw.githubusercontent.com/kubernetes/ingress-nginx/controller-v1.8.1/deploy/static/provider/cloud/deploy.yaml 2、设为默认的Ingress [rootk8s01 ~]# vim default_ingress.yaml apiVersion: networking.…...

SSR使用HTTPS

1.安装 npm i browser-sync 2. 再angular.json里配置 "serve-ssr": {"builder": "nguniversal/builders:ssr-dev-server","options": {"ssl": true,"sslCert": "./node_modules/browser-sync/certs/server…...

python打卡day49

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

如何将联系人从 iPhone 转移到 Android

从 iPhone 换到 Android 手机时&#xff0c;你可能需要保留重要的数据&#xff0c;例如通讯录。好在&#xff0c;将通讯录从 iPhone 转移到 Android 手机非常简单&#xff0c;你可以从本文中学习 6 种可靠的方法&#xff0c;确保随时保持连接&#xff0c;不错过任何信息。 第 1…...

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

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

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)

要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况&#xff0c;可以通过以下几种方式模拟或触发&#xff1a; 1. 增加CPU负载 运行大量计算密集型任务&#xff0c;例如&#xff1a; 使用多线程循环执行复杂计算&#xff08;如数学运算、加密解密等&#xff09;。运行图…...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关&#xff0…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...