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

代码随想录算法训练营第四十天|LeetCode343 整数拆分、LeetCode96 不同的二叉搜索树

343.整数拆分

思路:确定dp数组以及下标的含义 dp[i]代表 i可以被拆分后的最大乘积。确定递推公式,假如拆成连个数,dp[i] = j*(i-j),拆成两个数以上,dp[i]=j*dp[i-j],j的范围为1到i-1.dp[i]找到所有情况的最大值。初始化dp[2]=1。dp[1]=0。

class Solution {
public:int integerBreak(int n) {//确定dp数组及其下标含义 dp[i]表示i拆分后的最大乘积//确定递推公式 dp[i] = max(i*(i-j),j*dp[i-j],dp[i]);//初始化dp数组 dp[0] = 0; dp[1] = 0;dp[2] = 1;//遍历顺序//打印dp数组,用于debugvector<int> dp(n+1);dp[2] = 1;for(int i=3;i<=n;i++){for(int j = 1;j<i;j++){dp[i] =  max(max(j*(i-j),j*dp[i-j]),dp[i]);}}return dp[n];}
};

96.不同的二叉搜索树

思路:确定dp数组及其下标的含义,dp[i]表示i个节点排列二叉搜索树的顺序数。递推公式,当前节点的排列二叉搜索树的顺序数为 节点1~i分别为头节点的二叉搜索树的和,头节点为j的二叉搜索树左子树有j-1个节点,右子树有i-j个节点,所以头节点为j时对应dp[j-1]*dp[i-j]中二叉搜索树的顺序。dp[i] += dp[j-1]*dp[i-j]; 1<=j<=i。初始化dp[0]=1。遍历顺序,第i个节点的顺序数需要他前面节点的顺序数信息,因此为从前往后遍历。打印dp数组,可以用于debug。

class Solution {
public:int numTrees(int n) {//确定dp数组及其下标的意义 dp[i]表示i个节点组成不同的二叉搜索树的个数//递推公式 dp[i]+=dp[j-1]*dp[i-j];j是头节点,1<=j<=i//初始化dp数组 dp[0] = 1; dp[1] = 1; dp[2]= 2 ;//遍历顺序,头节点从1到n遍历//打印dp数组用于debugvector<int> dp(n+2);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];}
};

收获:

重要的是如何写出递推公式以及初始化。

dp数组的含义也很重要。

相关文章:

代码随想录算法训练营第四十天|LeetCode343 整数拆分、LeetCode96 不同的二叉搜索树

343.整数拆分 思路&#xff1a;确定dp数组以及下标的含义 dp[i]代表 i可以被拆分后的最大乘积。确定递推公式&#xff0c;假如拆成连个数&#xff0c;dp[i] j*(i-j),拆成两个数以上&#xff0c;dp[i]j*dp[i-j]&#xff0c;j的范围为1到i-1.dp[i]找到所有情况的最大值。初始化…...

接口自动化测试用例如何设计

说到自动化测试&#xff0c;或者说接口自动化测试&#xff0c;多数人的第一反应是该用什么工具&#xff0c;比如&#xff1a;Python Requests、Java HttpClient、Apifox、MeterSphere、自研的自动化平台等。大家似乎更关注的是哪个工具更优秀&#xff0c;甚至出现“ 做平台的 &…...

弱电综合布线:连接现代生活的纽带

在当今信息化快速发展的时代&#xff0c;弱电网络布线作为信息传输的重要基础设施&#xff0c;其作用日益凸显。它不仅保障了数据的高效流通&#xff0c;还确保了通信的稳定性。从商业大厦到教育机构&#xff0c;从政府机关到医院急救中心&#xff0c;再到我们居住的社区&#…...

Java零基础 - 数组的定义和声明

哈喽&#xff0c;各位小伙伴们&#xff0c;你们好呀&#xff0c;我是喵手。 今天我要给大家分享一些自己日常学习到的一些知识点&#xff0c;并以文字的形式跟大家一起交流&#xff0c;互相学习&#xff0c;一个人虽可以走的更快&#xff0c;但一群人可以走的更远。 我是一名后…...

CSS补充(下),弹性布局(上)

高级选择器 1.兄弟选择器 2.同时满足 div.bg{background-color: red;}p.bg{background-color: green;}spam.bg{background-color: blue;}注&#xff1a;选择器中间没有空格&#xff0c;有明确标识的选择器写在后面 3.各种伪类的应用 3.1作为第几个子元素 选择器:nth-child…...

图数据库 之 Neo4j - 应用场景4 - 反洗钱(9)

原理 Neo4j图数据库可以用于构建和分析数据之间的关系。它使用节点和关系来表示数据,并提供实时查询能力。通过使用Neo4j,可以将大量的交易数据导入图数据库,并通过查询和分析图结构来发现洗钱行为中的模式和关联。 案例分析 假设有一家转账服务公司,有以下交易数据,每个…...

uboot分区介绍

RK平台的U-Boot支持两种分区表 RK paramter格式&#xff08;旧&#xff09;和 标准GPT格式&#xff08;新&#xff09;&#xff0c;当机器上同时存在 两种分区表时&#xff0c;优先使用GPT分区表。无论是 GPT 还是 RK parameter&#xff0c;烧写用的分区表文件都叫parameter.t…...

快速收集诊断信息,敏捷诊断工具obdiag应用实践——《OceanBase诊断系列》之三

1. 前言 作为OceanBase的敏捷诊断工具&#xff0c;obdiag具有以下特点&#xff1a; 部署便捷&#xff1a;提供rpm包和OBD上部署的模式&#xff0c;都能够一键部署安装。用户可以选择将其部署到集群中任意一台能连接到各个节点的设备上&#xff0c;而不仅限于OBServer节点。即…...

C++错误总结(1)

1.定义函数类型时&#xff0c;如果没有返回值&#xff0c;用void void swap(int &x, int &y){ int tem x; x y; y tem; } 2.输入时&#xff0c;不加换行符 cin >> a >> b >> c >> endl ;(红色标记的是错误的部分) 3.【逆序出入…...

std::shared_from_this注意事项:exception bad_weak_ptr

1.不可以在构造函数中调用shared_from_this() 因为它的实现是&#xff1a; _LIBCPP_INLINE_VISIBILITYshared_ptr<_Tp> shared_from_this(){return shared_ptr<_Tp>(__weak_this_);}也就是它依赖的__weak_this_此时还未创建完成。 2.一定要public继承 class MyTy…...

【工具】Raycast – Mac提效工具

引入 以前看到同事们锁屏的时候&#xff0c;不知按了什么键&#xff0c;直接调出这个框&#xff0c;然后输入lock屏幕就锁了。 跟我习惯的按Mac开机键不大一样。个人觉得还是蛮炫酷的&#xff5e; 调研 但是由于之前比较繁忙&#xff0c;这件事其实都忘的差不多了&#xff0…...

蓝桥杯集训·每日一题2024 (二分,双指针)

前言&#xff1a; 开学了&#xff0c;平时学习的压力也逐渐大起来了&#xff0c;不过还算可以接受&#xff0c;等到后面阶段考的时候就不一样了&#xff0c;我目前为了转专业退选了很多课&#xff0c;这些课我都需要花时间来刷绩点&#xff0c;不然保研就没有竞争力了。我自己会…...

在Linux(Ubuntu)中使用终端编译 vscode安装

文章目录 &#x1f4da;在Linux&#xff08;Ubuntu&#xff09;中使用终端编译&#x1f407;.cpp程序编译&#x1f407;.py程序编译&#x1f407;查看Python、C编程环境 &#x1f4da;vscode安装 &#x1f4da;在Linux&#xff08;Ubuntu&#xff09;中使用终端编译 虚拟机安装…...

官网正在被哪些产品蚕食,定制网站又被哪些建站产品挤占。

2023-12-09 16:22贝格前端工场 官网建设是一个被大多数人看衰的市场&#xff0c;本文来理性分析下&#xff0c;谁在蚕食这个市场&#xff0c;谁又在挤占这个产品生存空间&#xff0c;欢迎大家评论&#xff0c;探讨。 网站正在被以下产品形式取代&#xff1a; 1. 移动应用&…...

BUUCTF---[MRCTF2020]你传你呢1

1.题目描述 2.打开题目链接 3.上传shell.jpg文件&#xff0c;显示连接成功&#xff0c;但是用蚁剑连接却连接不上。shell文件内容为 <script languagephp>eval($_REQUEST[cmd]);</script>4.用bp抓包&#xff0c;修改属性 5.需要上传一个.htaccess的文件来把jpg后缀…...

vite+vue3门户网站菜单栏动态路由控制

门户网站用户端需要分板块展示&#xff0c;板块内容由管理端配置&#xff0c;包括板块名称&#xff0c;访问路径&#xff0c;路由组件&#xff0c;展示顺序&#xff0c;是否展示。如下图所示&#xff1a; 用户访问门户网站时&#xff0c;展示菜单跳转通过板块配置&#xff0c;动…...

【C语言】linux内核packet_setsockopt

一、中文注释 // 发送数据包函数。它尝试通过特定的网络设备队列直接传输一个skb&#xff08;socket缓冲区&#xff09;。 static int packet_direct_xmit(struct sk_buff *skb) {return dev_direct_xmit(skb, packet_pick_tx_queue(skb)); // 调用dev_direct_xmit函数&#x…...

LeetCode的使用方法

LeetCode的使用方法 一、LeetCode是什么&#xff1f;1.LeetCode简介2.LeetCode官网 二、LeetCode的使用方法1.注册账号2.力扣社区力扣编辑器 2.1 讨论发起讨论参与讨论关注讨论 2.2 文章撰写文章关注文章 3.力扣面试官版测评面试招聘竞赛 4.力扣学习LeetBook 书架我的阅读猜您喜…...

Vue事件处理:.passive修饰符与应用场景

.passive修饰符 passive这个修饰符会执行默认方法。你们可能会问&#xff0c;明明默认执行为什么会设置这样一个修饰符。这就要说一下这个修饰符的本意了。 浏览器只有等内核线程执行到事件监听器对应的JavaScript代码时&#xff0c;才能知道内部是否会调用preventDefa…...

智慧城市中的数字孪生:构建城市管理的未来框架

目录 一、引言 二、数字孪生技术概述 三、数字孪生技术在智慧城市中的应用 1、实时监测与预警 2、模拟与优化 3、智能化决策 4、协同与共享 四、数字孪生技术构建城市管理的未来框架的价值 1、提高管理效率 2、优化资源配置 3、提升公共服务水平 4、增强应对突发事…...

练习(含atoi的模拟实现,自定义类型等练习)

一、结构体大小的计算及位段 &#xff08;结构体大小计算及位段 详解请看&#xff1a;自定义类型&#xff1a;结构体进阶-CSDN博客&#xff09; 1.在32位系统环境&#xff0c;编译选项为4字节对齐&#xff0c;那么sizeof(A)和sizeof(B)是多少&#xff1f; #pragma pack(4)st…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

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

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

IT供电系统绝缘监测及故障定位解决方案

随着新能源的快速发展&#xff0c;光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域&#xff0c;IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选&#xff0c;但在长期运行中&#xff0c;例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...

听写流程自动化实践,轻量级教育辅助

随着智能教育工具的发展&#xff0c;越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式&#xff0c;也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建&#xff0c;…...

AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机

这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机&#xff0c;因为在使用过程中发现 Airsim 对外部监控相机的描述模糊&#xff0c;而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置&#xff0c;最后在源码示例中找到了&#xff0c;所以感…...

Spring Security 认证流程——补充

一、认证流程概述 Spring Security 的认证流程基于 过滤器链&#xff08;Filter Chain&#xff09;&#xff0c;核心组件包括 UsernamePasswordAuthenticationFilter、AuthenticationManager、UserDetailsService 等。整个流程可分为以下步骤&#xff1a; 用户提交登录请求拦…...

6.9-QT模拟计算器

源码: 头文件: widget.h #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QMouseEvent>QT_BEGIN_NAMESPACE namespace Ui { class Widget; } QT_END_NAMESPACEclass Widget : public QWidget {Q_OBJECTpublic:Widget(QWidget *parent nullptr);…...