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

简介: 代码随想录算法训练营第四十天 | LeetCode 343. 整数拆分、96. 不同的二叉搜索树

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

文章链接:整数拆分        不同的二叉搜索树

视频链接:整数拆分        不同的二叉搜索树

1. LeetCode 343. 整数拆分

1.1 思路

  1. 给我们一个数,如何去拆成若干个数使其相乘最大?应该尽可能给他拆成相同的数。比如 10 拆成 5*5<3*3*4。因此拆成 m 个数,这 m 个数数值是近似相等的,这样相乘才尽可能大。
  2. 确定 dp 数组及其下标的含义:dp[i]:对 i 进行拆分,得到的这个最大乘积就是 dp[i]
  3. 递推公式:如果拆成两个数就是一个 j,一个(i-j)。如果是拆成三个及以上的话,就是 j*dp[i-j]。这里可能疑惑为什么不拆分 j 而是拆分 (i-j)呢?其实这里固定 j 之后 拆分(i-j)就已经包含了所有的情况了包括拆分 j 的情况。
  4. dp 数组的初始化:dp[0]、dp[1] 没有意义,拆不了,也可以初始化为 0。dp[2]=1
  5. 遍历顺序:从 3 开始往后遍历,两层 for循环。for(int i=3;i<=n;i++)for(int j=1;j<i;i++)递推公式 dp[i]=Math.max(j*(i-j),j*dp[i-j],dp[i])。为什么还需要 dp[i] 呢?dp[i] 的最大值并不一定出现在最后一次拆分中,可能中间某一次拆分就会出现最大值,所以需要再和 dp[i] 取下最值
  6. 打印 dp 数组:主要用于 debug

1.2 代码

class Solution {
    public int integerBreak(int n) {
        //dp[i] 为正整数 i 拆分后的结果的最大乘积
        int[] dp = new int[n+1];
        dp[2] = 1;
        for(int i = 3; i <= n; i++) {
            for(int j = 1; j <= i-j; j++) {
                // 这里的 j 其实最大值为 i-j,再大只不过是重复而已,
                //并且,在本题中,我们分析 dp[0], dp[1]都是无意义的,
                //j 最大到 i-j,就不会用到 dp[0]与dp[1]
                dp[i] = Math.max(dp[i], Math.max(j*(i-j), j*dp[i-j]));
                // j * (i - j) 是单纯的把整数 i 拆分为两个数 也就是 i,i-j ,再相乘
                //而j * dp[i - j]是将 i 拆分成两个以及两个以上的个数,再相乘。
            }
        }
        return dp[n];
    }
}

2. LeetCode 96. 不同的二叉搜索树

2.1 思路

  1. 我们看上图可以发现当 n=3 时,我们以 1 为头节点时右子树的布局和 n=2 时是一样的,以 2 为头节点时左子树和右子树的布局和 n=1 时是一样的,以 3 为头节点时左子树的布局和 n=2 时是一样的。因此可以发现 n=3 的情况是可以由 n=1 和 n=2 推导出来
  2. 我们再看看 n=3 时二叉搜索树有几种结果。我们可以发现 n=3 时的二叉搜索树的数量是由 n=0、n=1、n=2 推导出来的。即 dp[3]=dp[0]*dp[2]+dp[1]*dp[1]+dp[2]*dp[0]
  3. 确定 dp 数组及其下标的含义:dp[i]:1 到 i 为节点组成的二叉搜索树的个数为 dp[i]
  4. 递推公式:我们用 j 来枚举,从 1 遍历到 i,如果以 j 为头节点,左子树应该有 j-1 个,因为是二叉搜索树,右子树应该有 i-j 个,可以自己举例看看。又以 j-1 个和 i-j 个看 dp,因此 dp[i]+=dp[j-1]*dp[i-j]。这里怎么跟 dp[3]=dp[0]*dp[2]+dp[1]*dp[1]+dp[2]*dp[0] 不一样呢?因为这个公式其实就是由那个算出来的
  5. dp 数组的初始化:dp[0]=1,因为二叉搜索树也是 1 个
  6. 遍历顺序:从前往后从小到大遍历。for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)dp[i]+=dp[j-1]*dp[i-j]
  7. 打印 dp 数组:用于 debug

2.2 代码

class Solution {
    public int numTrees(int n) {
        //初始化 dp 数组
        int[] dp = new int[n + 1];
        //初始化0个节点和1个节点的情况
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                //对于第i个节点,需要考虑1作为根节点直到i作为根节点的情况,所以需要累加
                //一共i个节点,对于根节点j时,左子树的节点个数为j-1,右子树的节点个数为i-j
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
}
目录
打赏
0
0
1
0
9
分享
相关文章
近端策略优化(PPO)算法的理论基础与PyTorch代码详解
近端策略优化(PPO)是深度强化学习中高效的策略优化方法,广泛应用于大语言模型的RLHF训练。PPO通过引入策略更新约束机制,平衡了更新幅度,提升了训练稳定性。其核心思想是在优势演员-评论家方法的基础上,采用裁剪和非裁剪项组成的替代目标函数,限制策略比率在[1-ϵ, 1+ϵ]区间内,防止过大的策略更新。本文详细探讨了PPO的基本原理、损失函数设计及PyTorch实现流程,提供了完整的代码示例。
133 10
近端策略优化(PPO)算法的理论基础与PyTorch代码详解
C 语言递归算法:以简洁代码驾驭复杂逻辑
C语言递归算法简介:通过简洁的代码实现复杂的逻辑处理,递归函数自我调用解决分层问题,高效而优雅。适用于树形结构遍历、数学计算等领域。
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
100 1
通过优化算法和代码结构来提升易语言程序的执行效率
通过优化算法和代码结构来提升易语言程序的执行效率
分享一些提高二叉树遍历算法效率的代码示例
这只是简单的示例代码,实际应用中可能还需要根据具体需求进行更多的优化和处理。你可以根据自己的需求对代码进行修改和扩展。
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
阿里云MaxCompute-XGBoost on Spark 极限梯度提升算法的分布式训练与模型持久化oss的实现与代码浅析
本文介绍了XGBoost在MaxCompute+OSS架构下模型持久化遇到的问题及其解决方案。首先简要介绍了XGBoost的特点和应用场景,随后详细描述了客户在将XGBoost on Spark任务从HDFS迁移到OSS时遇到的异常情况。通过分析异常堆栈和源代码,发现使用的`nativeBooster.saveModel`方法不支持OSS路径,而使用`write.overwrite().save`方法则能成功保存模型。最后提供了完整的Scala代码示例、Maven配置和提交命令,帮助用户顺利迁移模型存储路径。
基于FPGA的图像双线性插值算法verilog实现,包括tb测试文件和MATLAB辅助验证
本项目展示了256×256图像通过双线性插值放大至512×512的效果,无水印展示。使用Matlab 2022a和Vivado 2019.2开发,提供完整代码及详细中文注释、操作视频。核心程序实现图像缩放,并在Matlab中验证效果。双线性插值算法通过FPGA高效实现图像缩放,确保质量。
基于遗传优化算法的风力机位置布局matlab仿真
本项目基于遗传优化算法(GA)进行风力机位置布局的MATLAB仿真,旨在最大化风场发电效率。使用MATLAB2022A版本运行,核心代码通过迭代选择、交叉、变异等操作优化风力机布局。输出包括优化收敛曲线和最佳布局图。遗传算法模拟生物进化机制,通过初始化、选择、交叉、变异和精英保留等步骤,在复杂约束条件下找到最优布局方案,提升风场整体能源产出效率。
基于包围盒的机械臂防碰撞算法matlab仿真
基于包围盒的机械臂防碰撞算法通过构建包围盒来近似表示机械臂及其环境中各实体的空间占用,检测包围盒是否相交以预判并规避潜在碰撞风险。该算法适用于复杂结构对象,通过细分目标对象并逐级检测,确保操作安全。系统采用MATLAB2022a开发,仿真结果显示其有效性。此技术广泛应用于机器人运动规划与控制领域,确保机器人在复杂环境中的安全作业。