Category Archives: 算法题

Unique Binary Search Trees leetcode

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-n中选择i作为根,其可能出现的情况为[1,i-1]中BST种类 和 [i+1,n]中BST种类的 乘积, 因此n个节点的总可能性就是把1到n逐步作为根节点的情况总数,而每一个情况又可以按照同样的方式继续计算,因此,我们可以将问题逐步缩小。tip:可以用DP讲计算过的结果存储起来。 Advertisements

Posted in 算法题, Tree | Leave a comment

Substring with Concatenation of All Words

You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without … Continue reading

Posted in 算法题 | Tagged | Leave a comment