代码随想录算法训练营第40天|343. 整数拆分、96.不同的二叉搜索树
343. 整数拆分
题目链接:link
文章讲解:link
视频讲解:link
一、做题感受&第一想法
其实第一反应是回溯……但感觉每层的集合都会很繁琐
二、学习文章后收获
1.动态规划思路
-
动规五要素分析
- dp和i的定义:dp[i]指把i拆分后最大乘积(所以dp[1]、dp[0]都没有太大意义,因为0和1拆了乘积也是0)
- 递归公式:
dp[i] = max(j * (i - j) , j * dp[i - j]), 1 <= j < i - 1(j<i-1是为什么?因为j = i-1时,dp[j-i]也就是dp[1]为0,没有意义;而 j*(i-j)也就是(i-1)*1,这和 j=1重复了,所以可以省去j = i-1的讨论!) - 初始化:dp[0] = 0,dp[1] = 0,dp[2] = 1
- 遍历顺序:从前往后
- 手算序列(略)
-
递归公式的说明:求dp[i]可分成两种情况
- 把 i 拆成 j 和 i - j 两个数,总共两个数。
- 把 i 拆成 j 和"和为 i - j 的若干个数",总共大于等于三个数。
class Solution {
public:int integerBreak(int n) {vector<int> dp(n+1,0); //dp[i]:拆分i得到的最大乘积dp[0] = 0;dp[1] = 0; //其实这俩初始化无所谓,因为没有意义dp[2] = 1; // 1*1for(int i = 3;i <= n;i++){for(int j = 1;j < i - 1;j++){dp[i] = max(dp[i],max(j*(i-j),j*dp[i-j]));}}return dp[n];}
};
2.动态规划优化
思路:for循环上的剪枝,剪枝依据是,要想找到乘积最大的拆分方式,需要让拆出来的所有数字尽可能大小相似。所以,对于太大的 j ,可以直接跳过。
故内层for的条件改为 j <= i/2:for (int j = 1; j <= i / 2; j++)
class Solution {
public:int integerBreak(int n) {vector<int> dp(n + 1);dp[2] = 1;for (int i = 3; i <= n ; i++) {for (int j = 1; j <= i / 2; j++) { //here!dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));}}return dp[n];}
};
2.贪心思路
思路:本题也可以用贪心,每次拆成n个3,如果剩下是4,则保留4,然后相乘,但是这个结论需要数学证明其合理性!
此处没有证明,而是直接用了结论。
说明:
if(n == 2) return 1;
if(n == 3) return 2;
if(n == 4) return 4;
剩下的,拆成3的和,直到剩下4或者不足3(也就是前面是一堆3,最后剩下的值<=4即停止,作为最后一个数字)。
class Solution {
public:int integerBreak(int n) {if(n == 1 || n == 0) return 0;if(n == 2) return 1;if(n == 3) return 2;if(n == 4) return 4;int remains = n - 3,result = 3;while(remains > 4){result *= 3;remains -= 3;}result *= remains;return result;}
};
三、过程中遇到的问题
1.多个数取最大
max(a,max(b,c))
96.不同的二叉搜索树
题目链接:link
文章讲解:link
视频讲解:link
一、做题感受&第一想法
- 动规五要素分析
- dp和i的定义:dp[i]指 i 个节点的二叉搜索树共有多少种树型
- 递归公式:
dp[i] += dp[j] * dp[i-j-1], 0 <= j <= i - 1(左子树 j 个节点,右子树 i - j - 1个节点。总树型为 左子树的树型数 乘以 右子树的树型数) - 初始化:dp[0] = 1,dp[1] = 1
- 遍历顺序:从前往后
- 手算序列(略)
class Solution {
public:int numTrees(int n) {vector<int> dp(n+1,0);dp[0] = 1;dp[1] = 1;for(int i = 2;i <= n;i++){ //dp[i]for(int j = 0;j <= i - 1;j++){ //左子树:j,右子树:i-j-1dp[i] += dp[j] * dp[i-j-1]; //递推公式}}return dp[n];}
};
相关文章:
代码随想录算法训练营第40天|343. 整数拆分、96.不同的二叉搜索树
343. 整数拆分 题目链接:link 文章讲解:link 视频讲解:link 一、做题感受&第一想法 其实第一反应是回溯……但感觉每层的集合都会很繁琐 二、学习文章后收获 1.动态规划思路 动规五要素分析 dp和i的定义:dp[i]指把i拆分后最…...
二叉树算法
递归序 每个节点都能回到3次! 相当于2执行完然后返回了代码会往下走,来到3节点 小总结: 也就是4节点先来到自己一次,不会执行if,先调用自己左边的那个函数,但是是null,直接返回。 这个函数执行完了,就会回到自己,调用自己右边的那个函数,结果又是空,又返回,回到…...
【2024年5月备考新增】《软考真题分章练习(答案解析) - 4 项目范围管理(高项)》
点击跳转无答案版 1、() includes the processes required to ensure that the project includes all the work required , and only the work required , to complete the project successfully . Managing the project scope is primarily concerned with defining and con…...
Docker拉取镜像存储不足
在使用Docker时,我们经常遇到一个问题,就是拉取镜像时提示存储空间不足。这是因为Docker在拉取镜像时需要将镜像文件下载到本地存储中,而有时本地存储空间不足以容纳完整的镜像文件。 本文将介绍一些解决这个问题的方法,并提供相…...
JUNIT5+Mockito单元测试
文章目录 1、前言2、Maven依赖2.1 JDK21SpringBoot版本基于3.1.02.2 JDK17SpringBoot版本基于2.2.5.RELEASE 3、业务代码4、单元测试 1、前言 之前写过一篇使用testMe自动生成单元测试用例,使用的是junit4来编写的单元测试用例,目前很多新项目都已经使用…...
【C#】【SAP2000】读取SAP2000中所有Frame对象的应力比到Grasshopper中
if (build true) {// 连接到正在运行的 SAP2000// 使用 System.Runtime.InteropServices.Marshal.GetActiveObject 方法获取正在运行的 SAP2000 实例cOAPI mySapObject (cOAPI)System.Runtime.InteropServices.Marshal.GetActiveObject("CSI.SAP2000.API.SapObject"…...
一台服务器部署两个独立的mysql实例
🍁博主简介: 🏅云计算领域优质创作者 🏅2022年CSDN新星计划python赛道第一名 🏅2022年CSDN原力计划优质作者 🏅阿里云ACE认证高级工程师 🏅阿里云开发者社区专…...
SpringBoot(Lombok + Spring Initailizr + yaml)
1.Lombok 1.基本介绍 2.应用实例 1.pom.xml 引入Lombok,使用版本仲裁 <!--导入springboot父工程--><parent><artifactId>spring-boot-starter-parent</artifactId><groupId>org.springframework.boot</groupId><version&g…...
数据库基础知识超详细解析~(进阶/复习版)
文章目录 前言一、数据库的操作1.登入数据库2.创建数据库3.显示当前数据库4.使用数据库5.删除数据库 二、常用数据类型三、数据库的约束1约束类型2NULL约束3UNIQUE:唯一约束4DEFAULT:默认值约束5 PRIMARY KEY:主键约束6 FOREIGN KEY:外键约束…...
创建对象的方法有哪些
创建对象的方法主要取决于你使用的编程语言和上下文。下面我将列出一些主流编程语言中创建对象的方法: Python: 使用类定义和__init__方法: pythonclass MyClass: def __init__(self, name): self.name nameobj MyClass("Alice") 1.使用工厂…...
Oracle 10g字符编码
pl/sql developer查询数据时出现乱码,主要检查如下: 1、检查服务器编码 select * from v$nls_parameters;select * from nls_database_parameters;select userenv(language) from dual; 2、查看数据库可用字符集参数设置 select * from v$nls_valid_val…...
掌握抽象基础之20个必备原则,看完你还不会,你打我
抽象基础之20个必备原则 1. 面向对象编程(OOP)中抽象原则背后的基本思想是什么?2.抽象和封装的区别?3.提供一个现实生活中说明抽象的例子4.在编程语言中如何实现抽象?5.定义抽象类6.提供一个抽象类的真实世界场景7.解释…...
设计模式 -- 2:策略模式
目录 总结部分:策略模式的优点部分代码部分 总结部分: 策略模式和简单工厂模式很像 区别在于 简单工厂模式 需求的是由工程创造的类 去给客户直接答案 而策略模式在于 我有主体 一个主体 根据策略的不同来进行不同的计算 我的主体就负责收钱 然后调度相…...
【快速上手ProtoBuf】proto 3 语法详解
1 🍑字段规则🍑 消息的字段可以⽤下⾯⼏种规则来修饰: singular :消息中可以包含该字段零次或⼀次(不超过⼀次)。 proto3 语法中,字段默认使⽤该规则。repeated :消息中可以包含该…...
人工智能的幽默“失误”
人工智能迷惑行为大赏 随着ChatGPT热度的攀升,越来越多的公司也相继推出了自己的AI大模型,如文心一言、通义千问等。各大应用也开始内置AI玩法,如抖音的AI特效~在使用过程中往往会遇到一些问题,让你不得不怀疑&#x…...
js的异步请求?
在 JavaScript 中,进行异步请求通常涉及到使用 XMLHttpRequest 对象或者更现代的 Fetch API 或 Axios 库。这些工具可以帮助我们向服务器发送请求并在后台获取数据,而不会阻塞页面的其他操作。 下面是一个简单的示例,演示如何使用原生的 XML…...
华润对象存储(OBS)工具类
目录 一、备注二、工具类三、对象存储放在内网,如何实现外网访问 一、备注 1、ObjectBasicInfo、ObjectDetailInfo、ResultBody这三个类可自行替换或者去掉 二、工具类 package com.xxx.util;import com.amazonaws.HttpMethod; import com.amazonaws.auth.AWSStat…...
强缓存和协商缓存的区别?
协商缓存和强缓存是 HTTP 缓存机制中的两种不同的策略,用于减少网络请求并提高网页加载速度。它们之间的主要区别在于缓存的验证方式和服务器返回的响应头。 强缓存: 强缓存是基于过期时间(Expires)和缓存标识(Cache…...
ChatGPT提问技巧——对抗性提示
ChatGPT提问技巧——对抗性提示 对抗性提示是一种允许模型生成能够抵御某些类型的攻击或偏差的文本的技术。这种技术可用于训练更健壮、更能抵御某些类型的攻击或偏差的模型。 要在 ChatGPT 中使用对抗性提示,应为模型提供一个提示,该提示的设计应使模…...
openGauss使用BenchmarkSQL进行性能测试(上)
一、前言 本文提供openGauss使用BenchmarkSQL进行性能测试的方法和测试数据报告。 BenchmarkSQL,一个JDBC基准测试工具,内嵌了TPC-C测试脚本,支持很多数据库,如PostgreSQL、Oracle和Mysql等。 TPC-C是专门针对联机交易处理系统…...
XML Group端口详解
在XML数据映射过程中,经常需要对数据进行分组聚合操作。例如,当处理包含多个物料明细的XML文件时,可能需要将相同物料号的明细归为一组,或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码,增加了开…...
生成xcframework
打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式,可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...
QMC5883L的驱动
简介 本篇文章的代码已经上传到了github上面,开源代码 作为一个电子罗盘模块,我们可以通过I2C从中获取偏航角yaw,相对于六轴陀螺仪的yaw,qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...
【HTML-16】深入理解HTML中的块元素与行内元素
HTML元素根据其显示特性可以分为两大类:块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...
OpenLayers 分屏对比(地图联动)
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能,和卷帘图层不一样的是,分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...
第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词
Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵,其中每行,每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid,其中有多少个 3 3 的 “幻方” 子矩阵&am…...
Swagger和OpenApi的前世今生
Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章,二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑: 🔄 一、起源与初创期:Swagger的诞生(2010-2014) 核心…...
使用Spring AI和MCP协议构建图片搜索服务
目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式(本地调用) SSE模式(远程调用) 4. 注册工具提…...
人机融合智能 | “人智交互”跨学科新领域
本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...
AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机
这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机,因为在使用过程中发现 Airsim 对外部监控相机的描述模糊,而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置,最后在源码示例中找到了,所以感…...
