leetcode打卡#day42 62. 不同路径、63. 不同路径 II、343. 整数拆分、96. 不同的二叉搜索树

2024-06-13 12:20

本文主要是介绍leetcode打卡#day42 62. 不同路径、63. 不同路径 II、343. 整数拆分、96. 不同的二叉搜索树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

62. 不同路径

class Solution {
public://动态规划int uniquePaths(int m, int n) {//dp数组,记录到达目的地的路径数vector<vector<int>> dp(m, vector(n, 0));//初始化for(int i=0; i< m; i++) dp[i][0] = 1;for(int i=0; i< n; i++) dp[0][i] = 1;//遍历for(int i = 1; i < m; i++) {for (int j = 1; j < n; j++){dp[i][j] = dp[i][j-1] + dp[i-1][j];}}return dp[m-1][n-1];}
};

63. 不同路径 II

class Solution {
//动态规划, 此时有障碍的情况 
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int m = obstacleGrid.size();int n = obstacleGrid[0].size();//记录到达目的地的不同路径数vector<vector<int>> dp(m, vector<int>(n, 0));//初始化for(int i=0; i < m && !obstacleGrid[i][0]; i++) dp[i][0] = 1;for(int i=0; i < n && !obstacleGrid[0][i]; i++) dp[0][i] = 1;//遍历for(int i = 1; i < m; i++){for(int j = 1; j < n; j++){if(!obstacleGrid[i][j]) dp[i][j] = dp[i-1][j] + dp[i][j-1];}}return dp[m-1][n-1];}
};

343. 整数拆分

class Solution {
public://动态规划 -- dp[i]的含义: 乘积最大的该整数n的拆分int integerBreak(int n) {vector<int> dp(n+1, 0);dp[2] = 1;for (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];}
};

96. 不同的二叉搜索树

class Solution {
public://动态规划问题: vector<int> dp[i]记录 i 个结点有多少种二叉搜索树int numTrees(int n) {vector<int> dp(n+1, 0);//初始化dp[0] = 1;//遍历for (int i = 1; i <= n; i++){//dp[i] = 左子树个数 * 右子树的个数for(int j = 1; j <= i; j++) {dp[i] += dp[j-1] * dp[i-j];}}return dp[n];}
};

这篇关于leetcode打卡#day42 62. 不同路径、63. 不同路径 II、343. 整数拆分、96. 不同的二叉搜索树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1057291

相关文章

MySQL中慢SQL优化的不同方式介绍

《MySQL中慢SQL优化的不同方式介绍》慢SQL的优化,主要从两个方面考虑,SQL语句本身的优化,以及数据库设计的优化,下面小编就来给大家介绍一下有哪些方式可以优化慢SQL吧... 目录避免不必要的列分页优化索引优化JOIN 的优化排序优化UNION 优化慢 SQL 的优化,主要从两个方面考虑,SQL 语

使用C语言实现交换整数的奇数位和偶数位

《使用C语言实现交换整数的奇数位和偶数位》在C语言中,要交换一个整数的二进制位中的奇数位和偶数位,重点需要理解位操作,当我们谈论二进制位的奇数位和偶数位时,我们是指从右到左数的位置,本文给大家介绍了使... 目录一、问题描述二、解决思路三、函数实现四、宏实现五、总结一、问题描述使用C语言代码实现:将一个整

Linux修改pip和conda缓存路径的几种方法

《Linux修改pip和conda缓存路径的几种方法》在Python生态中,pip和conda是两种常见的软件包管理工具,它们在安装、更新和卸载软件包时都会使用缓存来提高效率,适当地修改它们的缓存路径... 目录一、pip 和 conda 的缓存机制1. pip 的缓存机制默认缓存路径2. conda 的缓

Python实现合并与拆分多个PDF文档中的指定页

《Python实现合并与拆分多个PDF文档中的指定页》这篇文章主要为大家详细介绍了如何使用Python实现将多个PDF文档中的指定页合并生成新的PDF以及拆分PDF,感兴趣的小伙伴可以参考一下... 安装所需要的库pip install PyPDF2 -i https://pypi.tuna.tsingh

Windows系统下如何查找JDK的安装路径

《Windows系统下如何查找JDK的安装路径》:本文主要介绍Windows系统下如何查找JDK的安装路径,文中介绍了三种方法,分别是通过命令行检查、使用verbose选项查找jre目录、以及查看... 目录一、确认是否安装了JDK二、查找路径三、另外一种方式如果很久之前安装了JDK,或者在别人的电脑上,想

Python中Windows和macOS文件路径格式不一致的解决方法

《Python中Windows和macOS文件路径格式不一致的解决方法》在Python中,Windows和macOS的文件路径字符串格式不一致主要体现在路径分隔符上,这种差异可能导致跨平台代码在处理文... 目录方法 1:使用 os.path 模块方法 2:使用 pathlib 模块(推荐)方法 3:统一使

一文教你解决Python不支持中文路径的问题

《一文教你解决Python不支持中文路径的问题》Python是一种广泛使用的高级编程语言,然而在处理包含中文字符的文件路径时,Python有时会表现出一些不友好的行为,下面小编就来为大家介绍一下具体的... 目录问题背景解决方案1. 设置正确的文件编码2. 使用pathlib模块3. 转换路径为Unicod

Python使用DeepSeek进行联网搜索功能详解

《Python使用DeepSeek进行联网搜索功能详解》Python作为一种非常流行的编程语言,结合DeepSeek这一高性能的深度学习工具包,可以方便地处理各种深度学习任务,本文将介绍一下如何使用P... 目录一、环境准备与依赖安装二、DeepSeek简介三、联网搜索与数据集准备四、实践示例:图像分类1.

Python进行PDF文件拆分的示例详解

《Python进行PDF文件拆分的示例详解》在日常生活中,我们常常会遇到大型的PDF文件,难以发送,将PDF拆分成多个小文件是一个实用的解决方案,下面我们就来看看如何使用Python实现PDF文件拆分... 目录使用工具将PDF按页数拆分将PDF的每一页拆分为单独的文件将PDF按指定页数拆分根据页码范围拆分

MySQL9.0默认路径安装下重置root密码

《MySQL9.0默认路径安装下重置root密码》本文主要介绍了MySQL9.0默认路径安装下重置root密码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们... 目录问题描述环境描述解决方法正常模式下修改密码报错原因问题描述mysqlChina编程采用默认安装路径,