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;
    }
}