96. 不同的二叉搜索树
问题描述
给定一个整数 n,求以 1 ... n 为节点组成的二叉搜索树有多少种?
解题思路
首先,进行问题分解。构建以1...n为节点的二叉搜索树,可以依次构建以1、2...i...n作为根节点的二叉搜索树,然后求这些不同根节点的树的数量之和。
然后来看每个子问题如何求解。构建以i(1<= i <= n)为根节点的二叉搜索树,其中1到i-1作为左子树的节点,i+1到n作为右子树的节点。如果左子树有m种可能,右子树有n种可能,那么满足条件的二叉搜索树就是所有满足条件的左右子树两两组合,数量为m*n。
值得注意的是,项数相等的数列能够构建的二叉搜索树的数量是一样的,也就是说以{1,2,3}和{5,6,7}为节点组成的二叉搜索树都是5种。
dp数组定义:dp[i]表示长度为n的序列能够组成的二叉搜索树的数量。
base case:当i=0时,只有空树一种可能,即dp[0]=1;当i=1时,只能构建出一颗只有根节点的树,即dp[1]=0。
状态转移:dp[i]是以1...i为根节点的二叉搜索树的数量的和。
代码实现
class Solution {
public int numTrees(int n) {
//dp[i]表示长度为n的序列能够组成的二叉搜索树的数量
int[] dp = new int[n + 1];
//base case
dp[0] = 1;
dp[1] = 1;
for(int i = 2 ; i <= n; i++){
//循环求和
for(int j = 1 ; j <= i; j++){
dp[i] += dp[j-1]*dp[i-j];
}
}
return dp[n];
}
}
121. 买卖股票的最佳时机
问题描述
给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。
解题思路1-暴力破解
首先,想到的是暴力破解。用双层for循环遍历,求最大差值。
class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
int max = 0;
for(int i = 0; i < len -1; i++){
for(int j = i + 1; j < len; j++){
int profit;
if(prices[i] >= prices[j]){
profit = 0;
}else{
profit = prices[j] - prices[i];
}
if(profit > max){
max = profit;
}
}
}
return max;
}
}
这种解法时间复杂度为O(n^2),提交之后因为超出时间限制所以没有通过。
解题思路2-动态规划
class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
int min = prices[0];
//dp[i]表示前i天的最大利润
int[] dp = new int[len];
dp[0] = 0;
for(int i = 1; i < len; i++){
if(prices[i] < min){
min = prices[i];
}
dp[i] = Math.max(dp[i-1], prices[i] - min);
}
return dp[len -1];
}
}
因为dp[i]只依赖于dp[i-1],所以可以对空间复杂度进行压缩,优化后如下:
class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
int max = 0, min = prices[0];
for(int i = 1; i < len; i++){
if(prices[i] < min){
min = prices[i];
}
int profit = prices[i] - min;
if(profit > max){
max = profit;
}
}
return max;
}
}
网友评论