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

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

hdu1240、hdu1253(三维搜索题)

1、从后往前输入,(x,y,z); 2、从下往上输入,(y , z, x); 3、从左往右输入,(z,x,y); hdu1240代码如下: #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc

2. c#从不同cs的文件调用函数

1.文件目录如下: 2. Program.cs文件的主函数如下 using System;using System.Collections.Generic;using System.Linq;using System.Threading.Tasks;using System.Windows.Forms;namespace datasAnalysis{internal static

hdu2544(单源最短路径)

模板题: //题意:求1到n的最短路径,模板题#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#i

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

uva 10061 How many zero's and how many digits ?(不同进制阶乘末尾几个0)+poj 1401

题意是求在base进制下的 n!的结果有几位数,末尾有几个0。 想起刚开始的时候做的一道10进制下的n阶乘末尾有几个零,以及之前有做过的一道n阶乘的位数。 当时都是在10进制下的。 10进制下的做法是: 1. n阶位数:直接 lg(n!)就是得数的位数。 2. n阶末尾0的个数:由于2 * 5 将会在得数中以0的形式存在,所以计算2或者计算5,由于因子中出现5必然出现2,所以直接一

poj 1734 (floyd求最小环并打印路径)

题意: 求图中的一个最小环,并打印路径。 解析: ans 保存最小环长度。 一直wa,最后终于找到原因,inf开太大爆掉了。。。 虽然0x3f3f3f3f用memset好用,但是还是有局限性。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#incl

PTA求一批整数中出现最多的个位数字

作者 徐镜春 单位 浙江大学 给定一批整数,分析每个整数的每一位数字,求出现次数最多的个位数字。例如给定3个整数1234、2345、3456,其中出现最多次数的数字是3和4,均出现了3次。 输入格式: 输入在第1行中给出正整数N(≤1000),在第二行中给出N个不超过整型范围的非负整数,数字间以空格分隔。 输出格式: 在一行中按格式“M: n1 n2 ...”输出,其中M是最大次数,n

hdu 4517 floyd+记忆化搜索

题意: 有n(100)个景点,m(1000)条路,时间限制为t(300),起点s,终点e。 访问每个景点需要时间cost_i,每个景点的访问价值为value_i。 点与点之间行走需要花费的时间为g[ i ] [ j ] 。注意点间可能有多条边。 走到一个点时可以选择访问或者不访问,并且当前点的访问价值应该严格大于前一个访问的点。 现在求,从起点出发,到达终点,在时间限制内,能得到的最大