Sunday, July 14, 2013

Unique Binary Search Tree@leetcode

刷题必备书籍Cracking the Coding Interview: 150 Programming Questions and Solutions 

简历:The Google Resume: How to Prepare for a Career and Land a Job at Apple, Microsoft, Google, or any Top Tech Company
算法学习书籍:Introduction to Algorithms
编程珠玑:Programming Pearls (2nd Edition)
C++ 学习:The C++ Programming Language, 4th Edition
经典操作系统书籍,龙书:Operating System Concepts
创业:The Start-up of You: Adapt to the Future, Invest in Yourself, and Transform Your Career
Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
For example,
Given n = 3, there are a total of 5 unique BST's.
   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3
» Solve this problem

此题刚开始看上去无从下手,但是稍作分析就会发现,比较简单。简单在于它不用我们输出所有的 BST,而仅仅是给出有多少个就可以了。这样我们可以一个一个当作root看子树的个数。这时候就是recursion and dp了。这个时候又注意到,当结点i当root时,所有小于i的,会在左子树,所有大于i的,会在右子树。就是个简单的递归了。




更简单的逻辑.

No comments:

Post a Comment

Leetcode 316. Remove Duplicate Letters

 这道题表面问的是如何删除重复,实际在问如何从多个字符选取一个保留,从而让整个字符串按升序排列。那么策略就是对于高顺位的字符比如‘a',就要选靠前位置的保留,而低顺位字符如’z'则应该尽量选取靠后位置保留。 算法大概思路:每看到一个字符,我们要决定是否保留 1. ...