代码随想录算法训练营第四十天|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、增强应对突发事…...
接口测试中缓存处理策略
在接口测试中,缓存处理策略是一个关键环节,直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性,避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明: 一、缓存处理的核…...
Linux应用开发之网络套接字编程(实例篇)
服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...
华为云AI开发平台ModelArts
华为云ModelArts:重塑AI开发流程的“智能引擎”与“创新加速器”! 在人工智能浪潮席卷全球的2025年,企业拥抱AI的意愿空前高涨,但技术门槛高、流程复杂、资源投入巨大的现实,却让许多创新构想止步于实验室。数据科学家…...
Java 语言特性(面试系列2)
一、SQL 基础 1. 复杂查询 (1)连接查询(JOIN) 内连接(INNER JOIN):返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...
跨链模式:多链互操作架构与性能扩展方案
跨链模式:多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈:模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展(H2Cross架构): 适配层…...
工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配
AI3D视觉的工业赋能者 迁移科技成立于2017年,作为行业领先的3D工业相机及视觉系统供应商,累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成,通过稳定、易用、高回报的AI3D视觉系统,为汽车、新能源、金属制造等行…...
Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理
引言 Bitmap(位图)是Android应用内存占用的“头号杀手”。一张1080P(1920x1080)的图片以ARGB_8888格式加载时,内存占用高达8MB(192010804字节)。据统计,超过60%的应用OOM崩溃与Bitm…...
Android第十三次面试总结(四大 组件基础)
Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成,用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机: onCreate() 调用时机:Activity 首次创建时调用。…...
代码规范和架构【立芯理论一】(2025.06.08)
1、代码规范的目标 代码简洁精炼、美观,可持续性好高效率高复用,可移植性好高内聚,低耦合没有冗余规范性,代码有规可循,可以看出自己当时的思考过程特殊排版,特殊语法,特殊指令,必须…...
永磁同步电机无速度算法--基于卡尔曼滤波器的滑模观测器
一、原理介绍 传统滑模观测器采用如下结构: 传统SMO中LPF会带来相位延迟和幅值衰减,并且需要额外的相位补偿。 采用扩展卡尔曼滤波器代替常用低通滤波器(LPF),可以去除高次谐波,并且不用相位补偿就可以获得一个误差较小的转子位…...
