代码随想录算法训练营第四十天|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.整数拆分 思路:确定dp数组以及下标的含义 dp[i]代表 i可以被拆分后的最大乘积。确定递推公式,假如拆成连个数,dp[i] j*(i-j),拆成两个数以上,dp[i]j*dp[i-j],j的范围为1到i-1.dp[i]找到所有情况的最大值。初始化…...
接口自动化测试用例如何设计
说到自动化测试,或者说接口自动化测试,多数人的第一反应是该用什么工具,比如:Python Requests、Java HttpClient、Apifox、MeterSphere、自研的自动化平台等。大家似乎更关注的是哪个工具更优秀,甚至出现“ 做平台的 &…...
弱电综合布线:连接现代生活的纽带
在当今信息化快速发展的时代,弱电网络布线作为信息传输的重要基础设施,其作用日益凸显。它不仅保障了数据的高效流通,还确保了通信的稳定性。从商业大厦到教育机构,从政府机关到医院急救中心,再到我们居住的社区&#…...
Java零基础 - 数组的定义和声明
哈喽,各位小伙伴们,你们好呀,我是喵手。 今天我要给大家分享一些自己日常学习到的一些知识点,并以文字的形式跟大家一起交流,互相学习,一个人虽可以走的更快,但一群人可以走的更远。 我是一名后…...
CSS补充(下),弹性布局(上)
高级选择器 1.兄弟选择器 2.同时满足 div.bg{background-color: red;}p.bg{background-color: green;}spam.bg{background-color: blue;}注:选择器中间没有空格,有明确标识的选择器写在后面 3.各种伪类的应用 3.1作为第几个子元素 选择器:nth-child…...
图数据库 之 Neo4j - 应用场景4 - 反洗钱(9)
原理 Neo4j图数据库可以用于构建和分析数据之间的关系。它使用节点和关系来表示数据,并提供实时查询能力。通过使用Neo4j,可以将大量的交易数据导入图数据库,并通过查询和分析图结构来发现洗钱行为中的模式和关联。 案例分析 假设有一家转账服务公司,有以下交易数据,每个…...
uboot分区介绍
RK平台的U-Boot支持两种分区表 RK paramter格式(旧)和 标准GPT格式(新),当机器上同时存在 两种分区表时,优先使用GPT分区表。无论是 GPT 还是 RK parameter,烧写用的分区表文件都叫parameter.t…...
快速收集诊断信息,敏捷诊断工具obdiag应用实践——《OceanBase诊断系列》之三
1. 前言 作为OceanBase的敏捷诊断工具,obdiag具有以下特点: 部署便捷:提供rpm包和OBD上部署的模式,都能够一键部署安装。用户可以选择将其部署到集群中任意一台能连接到各个节点的设备上,而不仅限于OBServer节点。即…...
C++错误总结(1)
1.定义函数类型时,如果没有返回值,用void void swap(int &x, int &y){ int tem x; x y; y tem; } 2.输入时,不加换行符 cin >> a >> b >> c >> endl ;(红色标记的是错误的部分) 3.【逆序出入…...
std::shared_from_this注意事项:exception bad_weak_ptr
1.不可以在构造函数中调用shared_from_this() 因为它的实现是: _LIBCPP_INLINE_VISIBILITYshared_ptr<_Tp> shared_from_this(){return shared_ptr<_Tp>(__weak_this_);}也就是它依赖的__weak_this_此时还未创建完成。 2.一定要public继承 class MyTy…...
【工具】Raycast – Mac提效工具
引入 以前看到同事们锁屏的时候,不知按了什么键,直接调出这个框,然后输入lock屏幕就锁了。 跟我习惯的按Mac开机键不大一样。个人觉得还是蛮炫酷的~ 调研 但是由于之前比较繁忙,这件事其实都忘的差不多了࿰…...
蓝桥杯集训·每日一题2024 (二分,双指针)
前言: 开学了,平时学习的压力也逐渐大起来了,不过还算可以接受,等到后面阶段考的时候就不一样了,我目前为了转专业退选了很多课,这些课我都需要花时间来刷绩点,不然保研就没有竞争力了。我自己会…...
在Linux(Ubuntu)中使用终端编译 vscode安装
文章目录 📚在Linux(Ubuntu)中使用终端编译🐇.cpp程序编译🐇.py程序编译🐇查看Python、C编程环境 📚vscode安装 📚在Linux(Ubuntu)中使用终端编译 虚拟机安装…...
官网正在被哪些产品蚕食,定制网站又被哪些建站产品挤占。
2023-12-09 16:22贝格前端工场 官网建设是一个被大多数人看衰的市场,本文来理性分析下,谁在蚕食这个市场,谁又在挤占这个产品生存空间,欢迎大家评论,探讨。 网站正在被以下产品形式取代: 1. 移动应用&…...
BUUCTF---[MRCTF2020]你传你呢1
1.题目描述 2.打开题目链接 3.上传shell.jpg文件,显示连接成功,但是用蚁剑连接却连接不上。shell文件内容为 <script languagephp>eval($_REQUEST[cmd]);</script>4.用bp抓包,修改属性 5.需要上传一个.htaccess的文件来把jpg后缀…...
vite+vue3门户网站菜单栏动态路由控制
门户网站用户端需要分板块展示,板块内容由管理端配置,包括板块名称,访问路径,路由组件,展示顺序,是否展示。如下图所示: 用户访问门户网站时,展示菜单跳转通过板块配置,动…...
【C语言】linux内核packet_setsockopt
一、中文注释 // 发送数据包函数。它尝试通过特定的网络设备队列直接传输一个skb(socket缓冲区)。 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是什么?1.LeetCode简介2.LeetCode官网 二、LeetCode的使用方法1.注册账号2.力扣社区力扣编辑器 2.1 讨论发起讨论参与讨论关注讨论 2.2 文章撰写文章关注文章 3.力扣面试官版测评面试招聘竞赛 4.力扣学习LeetBook 书架我的阅读猜您喜…...
Vue事件处理:.passive修饰符与应用场景
.passive修饰符 passive这个修饰符会执行默认方法。你们可能会问,明明默认执行为什么会设置这样一个修饰符。这就要说一下这个修饰符的本意了。 浏览器只有等内核线程执行到事件监听器对应的JavaScript代码时,才能知道内部是否会调用preventDefa…...
智慧城市中的数字孪生:构建城市管理的未来框架
目录 一、引言 二、数字孪生技术概述 三、数字孪生技术在智慧城市中的应用 1、实时监测与预警 2、模拟与优化 3、智能化决策 4、协同与共享 四、数字孪生技术构建城市管理的未来框架的价值 1、提高管理效率 2、优化资源配置 3、提升公共服务水平 4、增强应对突发事…...
如何用Autolabel自动化数据标注提升25-100倍效率?
如何用Autolabel自动化数据标注提升25-100倍效率? 【免费下载链接】autolabel Label, clean and enrich text datasets with LLMs. 项目地址: https://gitcode.com/gh_mirrors/au/autolabel 在人工智能时代,高质量标注数据是模型成功的核心要素。…...
如何快速解决Krita-AI-Diffusion插件安装问题:完整技术指南
如何快速解决Krita-AI-Diffusion插件安装问题:完整技术指南 【免费下载链接】krita-ai-diffusion Streamlined interface for generating images with AI in Krita. Inpaint and outpaint with optional text prompt, no tweaking required. 项目地址: https://gi…...
从‘围成面积’到图像处理:用C++实现连通域分析与面积计算(信息学奥赛题拓展)
从网格到像素:C连通域分析在图像处理中的实战演进 第一次接触连通域问题时,我盯着那个10x10的网格看了整整半小时——那些简单的0和1背后隐藏着怎样的数学之美?后来才发现,这不仅是信息学奥赛的一道题目,更是计算机视觉…...
嵌入式系统与CPS的本质差异及核心技术解析
1. 嵌入式系统与信息物理系统的本质差异在传统认知中,嵌入式系统常被简单理解为"资源受限的小型计算机系统",这种观点已经无法适应当前技术发展的需求。嵌入式系统与信息物理系统(CPS)的根本区别在于:前者关注的是计算设备本身的实…...
从零到量产:手把手教你用U-Boot MMC命令为i.MX6ULL板卡烧录完整系统镜像
从零到量产:手把手教你用U-Boot MMC命令为i.MX6ULL板卡烧录完整系统镜像 在嵌入式产品开发中,系统镜像的烧录是连接硬件与软件的关键环节。对于采用NXP i.MX6ULL处理器的设备而言,掌握U-Boot的MMC命令操作不仅能提升开发效率,更能…...
西门子S7-1500 PLC里那个LEAD_LAG指令,到底怎么用?手把手教你调超前滞后时间
S7-1500 PLC中LEAD_LAG指令的实战应用指南 1. 理解LEAD_LAG指令的核心价值 在工业自动化控制系统中,信号处理的质量直接影响着整个控制回路的性能。西门子S7-1500 PLC提供的LEAD_LAG(超前-滞后)指令,正是解决这一问题的利器。这个…...
KMS_VL_ALL_AIO终极指南:5分钟快速搞定Windows和Office永久激活
KMS_VL_ALL_AIO终极指南:5分钟快速搞定Windows和Office永久激活 【免费下载链接】KMS_VL_ALL_AIO Smart Activation Script 项目地址: https://gitcode.com/gh_mirrors/km/KMS_VL_ALL_AIO 还在为Windows系统未激活而烦恼吗?是否因为Office办公软件…...
ADK WinPE定制进阶:除了Explorer,我的PE里还集成了这些轻量级必备工具
ADK WinPE定制进阶:打造轻量高效的PE工具生态 在系统维护与部署领域,一个精心定制的WinPE环境就像技术人员的瑞士军刀——不在于功能繁多,而在于每项工具都能精准解决实际问题。当大多数现成PE系统要么功能冗余要么过于简陋时,掌握…...
3分钟搞定:Blender 3MF插件完整指南,释放你的3D打印创意
3分钟搞定:Blender 3MF插件完整指南,释放你的3D打印创意 【免费下载链接】Blender3mfFormat Blender add-on to import/export 3MF files 项目地址: https://gitcode.com/gh_mirrors/bl/Blender3mfFormat 想要在Blender中无缝处理3D打印文件吗&am…...
Qwen3-4B-Thinking镜像安全合规说明:纯本地运行、无外呼请求、符合《生成式AI服务管理暂行办法》
Qwen3-4B-Thinking镜像安全合规说明:纯本地运行、无外呼请求、符合《生成式AI服务管理暂行办法》 1. 模型概述 Qwen3-4B-Thinking-2507-Gemini-2.5-Flash-Distill是基于vLLM部署的文本生成模型,采用chainlit作为前端调用界面。该模型在约5440万个由Gem…...
