算法训练Day40|343. 整数拆分 ● 96.不同的二叉搜索树

简介: 算法训练Day40|343. 整数拆分 ● 96.不同的二叉搜索树

343. 整数拆分 - 力扣(LeetCode)


1.思路


确定dp[]数组含义,dp[n]表示数 n 各子数的最大乘积

dp[2] 初始为 1.

遍历顺序,从 3 开始,最值从 j * (i - j) 和 j * dp[i - j] 以及 dp[i] 中选择.

dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));



2.代码实现

 1class Solution {
 2    public int integerBreak(int n) {
 3        int[] dp = new int[n + 1]; // 创建一个长度为 n + 1 的数组,用于存储每个整数的最大乘积
 4        dp[2] = 1; // 初始化 dp[2] = 1, 因为 2 只能分解为两个 1, 成绩为1
 5        // 从整数 3 开始计算最大乘积
 6        for (int i = 3; i <= n; i++) { 
 7            // 遍历从 1 到 i - j 的整数, j 表示分解的第一个整数的大小
 8            for (int j = 1; j < i - j; j++) {
 9                // 计算当前情况下的最大乘积, 有两种情况:
10                // 1. 不分解第一个整数,乘积为 j * (i - j)
11                // 2. 分解第一个整数,乘积为 j * dp[i - j], dp[i - j] 表示将 i - j 分解为多个整数后的最大乘积
12                // 去两者之间的较大值
13                // dp[i] 每次也参与其中
14                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
15            }
16        }
17        // 返回 n 对应的最大乘积
18        return dp[n];
19    }
20}

3.复杂度分析


时间复杂度:O(n^2).

空间复杂度:O(n).


LeetCode:


96. 不同的二叉搜索树 - 力扣(LeetCode)


1.思路

看完题解,这种题更像是找规律。而且未必好找,似乎只能靠熟练度刷出思维方式.

动规五部曲:

①确定dp[n]的含义:数n的二叉搜索树的个数为dp[n]

②dp[]数组声明:int[] dp = new int[n + 1];

③初始化:dp[0] = 1;dp[1] = 1;

④确定递推公式:dp[i] += dp[j - 1] * dp[i - j];

⑤确定遍历顺序:从小数到大数顺序遍历.



2.代码实现

 1class Solution {
 2    public int numTrees(int n) {
 3        int[] dp = new int[n + 1];
 4        dp[0] = 1;
 5        dp[1] = 1;
 6        for (int i = 2; i <= n; i++) {
 7            for (int j = 1; j <= i; j++) {
 8                // 对于第 i 个节点,需要考虑 1 作为根节点,直到 i 作为根节点的情况,所以需要累加
 9                // 一共 i 个节点,根节点为 j 时,左子树的节点个数为 j - 1, 右子树的节点数量为 i - j
10                dp[i] += dp[j - 1] * dp[i - j];
11            }
12        }
13        return dp[n];
14    }
15}
3.复杂度分析

时间复杂度:O(n^2).

空间复杂度:O(n).

相关文章
|
7月前
|
机器学习/深度学习 存储 算法
解锁文件共享软件背后基于 Python 的二叉搜索树算法密码
文件共享软件在数字化时代扮演着连接全球用户、促进知识与数据交流的重要角色。二叉搜索树作为一种高效的数据结构,通过有序存储和快速检索文件,极大提升了文件共享平台的性能。它依据文件名或时间戳等关键属性排序,支持高效插入、删除和查找操作,显著优化用户体验。本文还展示了用Python实现的简单二叉搜索树代码,帮助理解其工作原理,并展望了该算法在分布式计算和机器学习领域的未来应用前景。
|
4月前
|
存储 监控 算法
公司内部网络监控中的二叉搜索树算法:基于 Node.js 的实时设备状态管理
在数字化办公生态系统中,公司内部网络监控已成为企业信息安全管理体系的核心构成要素。随着局域网内终端设备数量呈指数级增长,实现设备状态的实时追踪与异常节点的快速定位,已成为亟待解决的关键技术难题。传统线性数据结构在处理动态更新的设备信息时,存在检索效率低下的固有缺陷;而树形数据结构因其天然的分层特性与高效的检索机制,逐渐成为网络监控领域的研究热点。本文以二叉搜索树(Binary Search Tree, BST)作为研究对象,系统探讨其在公司内部网络监控场景中的应用机制,并基于 Node.js 平台构建一套具备实时更新与快速查询功能的设备状态管理算法框架。
133 3
|
6月前
|
算法 Java
算法系列之数据结构-二叉搜索树
二叉查找树(Binary Search Tree,简称BST)是一种常用的数据结构,它能够高效地进行查找、插入和删除操作。二叉查找树的特点是,对于树中的每个节点,其左子树中的所有节点都小于该节点,而右子树中的所有节点都大于该节点。
191 22
|
6月前
|
存储 监控 算法
基于 PHP 二叉搜索树算法的内网行为管理机制探究
在当今数字化网络环境中,内网行为管理对于企业网络安全及高效运营具有至关重要的意义。它涵盖对企业内部网络中各类行为的监测、分析与管控。在内网行为管理技术体系里,算法与数据结构扮演着核心角色。本文将深入探究 PHP 语言中的二叉搜索树算法于内网行为管理中的应用。
69 4
|
7月前
|
存储 算法 Java
解锁“分享文件”高效密码:探秘 Java 二叉搜索树算法
在信息爆炸的时代,文件分享至关重要。二叉搜索树(BST)以其高效的查找性能,为文件分享优化提供了新路径。本文聚焦Java环境下BST的应用,介绍其基础结构、实现示例及进阶优化。BST通过有序节点快速定位文件,结合自平衡树、多线程和权限管理,大幅提升文件分享效率与安全性。代码示例展示了文件插入与查找的基本操作,适用于大规模并发场景,确保分享过程流畅高效。掌握BST算法,助力文件分享创新发展。
|
7月前
|
监控 算法 安全
关于公司电脑桌面监控中 PHP 二叉搜索树算法的深度剖析
在现代企业管理中,公司电脑桌面监控系统通过二叉搜索树(BST)算法保障信息安全和提高效率。本文探讨PHP中的BST在监控场景的应用,包括节点定义、插入与查找操作,并展示如何管理时间戳数据,以快速查询特定时间段内的操作记录。BST的高效性使其成为处理复杂监控数据的理想选择。
65 2
|
8月前
|
存储 算法 安全
U 盘管控情境下 Python 二叉搜索树算法的深度剖析与探究
在信息技术高度发达的今天,数据安全至关重要。U盘作为常用的数据存储与传输工具,其管控尤为关键。本文探讨Python中的二叉搜索树算法在U盘管控中的应用,通过高效管理授权U盘信息,防止数据泄露,保障信息安全。二叉搜索树具有快速插入和查找的优势,适用于大量授权U盘的管理。尽管存在一些局限性,如树结构退化问题,但通过优化和改进,如采用自平衡树,可以有效提升U盘管控系统的性能和安全性。
94 3
|
11月前
|
存储 机器学习/深度学习 算法
蓝桥杯练习题(三):Python组之算法训练提高综合五十题
蓝桥杯Python编程练习题的集合,涵盖了从基础到提高的多个算法题目及其解答。
492 3
蓝桥杯练习题(三):Python组之算法训练提高综合五十题
|
10月前
|
分布式计算 Java 开发工具
阿里云MaxCompute-XGBoost on Spark 极限梯度提升算法的分布式训练与模型持久化oss的实现与代码浅析
本文介绍了XGBoost在MaxCompute+OSS架构下模型持久化遇到的问题及其解决方案。首先简要介绍了XGBoost的特点和应用场景,随后详细描述了客户在将XGBoost on Spark任务从HDFS迁移到OSS时遇到的异常情况。通过分析异常堆栈和源代码,发现使用的`nativeBooster.saveModel`方法不支持OSS路径,而使用`write.overwrite().save`方法则能成功保存模型。最后提供了完整的Scala代码示例、Maven配置和提交命令,帮助用户顺利迁移模型存储路径。
|
11月前
|
机器学习/深度学习 算法 决策智能
【机器学习】揭秘深度学习优化算法:加速训练与提升性能
【机器学习】揭秘深度学习优化算法:加速训练与提升性能

热门文章

最新文章