最小路径和
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-path-sum
解题思路
- 满足最优子结构，即最长路径的子路径也是对应顶点的最优值
- 用一个二维数组存储对应坐标的最长路径值，注意第一行和第一列元素的值可以直接得出
- 开始遍历，每一个元素判断从左边来和从上边来哪一个路径值最大，即去最大值作为该元素对应二维数组的值
- 遍历完成，返回二维数组最后一个元素值即为所求
代码
class Solution {
public int minPathSum(int[][] grid) {
int row = grid.length;
int col = grid[0].length;
if(row==0&&col==0){
return 0;
}
int[][] min = new int[row][col];
min[0][0]=grid[0][0];
for(int i=1;i<row;i++){
min[i][0]=min[i-1][0]+grid[i][0];
}
for(int j=1;j<col;j++){
min[0][j]=min[0][j-1]+grid[0][j];
}
for(int i=1;i<row;i++){
for(int j=1;j<col;j++){
min[i][j]=Math.min(min[i-1][j]+grid[i][j],min[i][j-1]+grid[i][j]);
}
}
return min[row-1][col-1];
}
}
结果
时间复杂度分析
数组每一个元素遍历一次，故时间复杂度为O(m*n)
不同搜索二叉树
给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？
示例:
输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-binary-search-trees
解题思路
- 满足最优子结构，即n个节点的二叉树种类对应的子二叉树种类也是最优值
- 可以这样想：n个节点的二叉搜索树种类=(0个节点左子树种类n-1个节点右子树种类)+(1个节点左子树种类n-2个节点右子树种类)+…+(n-1个节点左子树种类*0个节点右子树种类)
- 所以用一个长度为n的以为数组存储每个节点对应的二叉搜索树种类，设定n为0和1时 元素值为1，然后从2开始用上述迭代公式经行计算，直到计算到n即为所求
代码
class Solution {
public int numTrees(int n) {
if(n==0||n==1){
return 1;
}
int[] num = new int[n+1];
num[0] = num[1] = 1;
for(int i=2;i<=n;i++){
for(int k=0;k<i;k++){
num[i]+=num[k]*num[i-1-k];
}
}
return num[n];
}
}
结果
时间复杂度分析
双重循环，时间复杂度为O(n^2)
最长重复子数组
给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
示例：
输入：
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出：3
解释：
长度最长的公共子数组是 [3, 2, 1] 。
提示：
1 <= len(A), len(B) <= 1000
0 <= A[i], B[i] < 100
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray
解题思路
- 满足最优子结构，即最长的公共子字符串的子字符串也是对应元素最优值
- 用一个二维数组存储A和B字符串每两个元素的映射关系，遍历A和B字符串，当A和B某一个字符相同时，就用前一个映射值+1作为此映射值，相当于在子结构上进行扩展。
- 直至A和B字符串全部遍历完成，取出二维数组的最大元素值即为所求
代码
class Solution {
public int findLength(int[] A, int[] B) {
int findMax = 0;
int row = A.length;
int col = B.length;
int[][] max = new int[row][col];
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
if(A[i]==B[j]){
if(i==0||j==0){
max[i][j] = 1;
}
else{
max[i][j] = max[i-1][j-1]+1;
}
if(findMax<max[i][j]){
findMax = max[i][j];
}
}
}
}
return findMax;
}
}
结果
时间复杂度分析
双重循环，时间复杂度为O(m*n)
0 条评论