美文网首页
【D14】不同的二叉搜索树 & 买卖股票的最佳时机(LC 96&

【D14】不同的二叉搜索树 & 买卖股票的最佳时机(LC 96&

作者: sirenyunpan | 来源:发表于2021-02-16 02:57 被阅读0次

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

    相关文章

      网友评论

          本文标题:【D14】不同的二叉搜索树 & 买卖股票的最佳时机(LC 96&

          本文链接:https://www.haomeiwen.com/subject/fkamxltx.html