leetcode96-不同的二叉搜索树

原题

给定一个整数 n,求以 1 ... n 为节点组成的二叉搜索树有多少种?

示例:

输入: 3
输出: 5
解释: 给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

解法

思想

对于每一个n对应的数量应该是相同的,我们从1~n中任选一个做根节点(假设是第i个),那么左右两边各有F(i-1)F(n-i)中情况,将它们相乘就是此时第i个元素做根节点的情况。如此递归计算总数量。

代码

我一开始的写法:

class Solution {
    public int numTrees(int n) {
        return kindsCount(1,n);
    }

    public int kindsCount(int start,int end){
        if(start >= end) return 1;
        int count = 0;
        for(int i = start;i<=end;i++){
            count += kindsCount(start,i-1)*kindsCount(i+1,end);
        }
        return count;
    }
}

但是发现这样写消耗非常多时间,leetcode执行用时1700 ms

优化的思路主要是:
1. end和start并不关键,只要start-end(即范围内的数字数量,用n表示)相同,对应的值就相同。
2. 假如优化上条,很多F(n)单元会被重复计算,可以使用数组做缓存。

优化后:

class Solution {
    Integer[] cache;
    public int numTrees(int n) {
        cache = new Integer[n+1];
        return kindsCount(n);
    }

    public int kindsCount(int n){
        if(n <= 1) return 1;
        if(cache[n]!=null) return cache[n];
        int count = 0;
        for(int i = 1;i<=n;i++){
            count += kindsCount(i-1)*kindsCount(n-i);
        }
        cache[n] = count;
        return count;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode96-%e4%b8%8d%e5%90%8c%e7%9a%84%e4%ba%8c%e5%8f%89%e6%90%9c%e7%b4%a2%e6%a0%91/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年1月22日 16:54
下一篇 2020年1月22日

相关推荐

  • leetcode485-最大连续1的个数

    原题 给定一个二进制数组, 计算其中最大连续1的个数。 示例 1: 输入: [1,1,0,1,1,1] 输出: 3 解释: 开头的两位和最后的三位都是连续1,所以最大连续1的个数是…

    算法 2019年11月20日
    0120
  • leetcode146-LRU缓存机制

    原题 运用你所掌握的数据结构,设计和实现一个  LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put 。 获取数据 get(key) -…

    算法 2020年5月25日
    0100
  • leetcode47-全排列II

    原题 给定一个可包含重复数字的序列,返回所有不重复的全排列。 示例: 输入: [1,1,2] 输出: [ [1,1,2], [1,2,1], [2,1,1] ] 解法 思想 这道题…

    算法 2020年5月10日
    090
  • leetcode54-螺旋矩阵

    原题 给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素。 示例 1: 输入: [ [ 1, 2, 3 ], [ 4, 5, 6…

    算法 2019年11月15日
    080
  • leetcode313-超级丑数

    原题 编写一段程序来查找第 n 个超级丑数。 超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。 示例: 输入: n = 12, primes = [2…

    算法 2020年2月11日
    0110
  • leetcode994-腐烂的橘子

    原题 在给定的网格中,每个单元格可以有以下三个值之一: 值 0 代表空单元格;值 1 代表新鲜橘子;值 2 代表腐烂的橘子。每分钟,任何与腐烂的橘子(在 4 个正方向上)相邻的新鲜…

    2020年3月4日
    0100
  • leetcode378-有序矩阵中第K小的元素

    原题 给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第k小的元素。请注意,它是排序后的第k小元素,而不是第k个元素。 示例: matrix = [ &nbs…

    算法 2020年2月14日
    0420
  • leetcode95-不同的二叉搜索树II

    原题 给定一个整数 n,求以 1 ... n 为节点组成的二叉搜索树有多少种? 示例: 输入: 3 输出: [   [1,null,3,2],  &n…

    算法 2020年1月22日
    0700
  • leetcode983-最低票价

    原题 在一个火车旅行很受欢迎的国度,你提前一年计划了一些火车旅行。在接下来的一年里,你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。 火车…

    算法 2020年5月6日
    0120
  • 剑指offer57-和为s的连续正数序列

    原题(来源Leetcode) 输入一个正整数 target ,输出所有和为 target 的连续正整数序列(至少含有两个数)。 序列内的数字由小到大排列,不同序列按照首个数字从小到…

    算法 2020年3月6日
    050

发表回复

登录后才能评论