Catalan Number

1, 2, 5, 14, 42…

背景知識

組合公式：𝐶(n, r)= n!/r!(n-r)!
卡塔蘭數：𝐶𝑛=𝐶(2𝑛, 𝑛)/(n+1)=(2n)!/(n+1)!n!, n = 1, 2, 3, …

return int((math.factorial(2*n) / (math.factorial(n+1) * math.factorial(n))))

理解問題

• 22. Generate Parentheses
• 96. Unique Binary Search Trees
• 所有在n × n格點中不越過對角線的最短路徑的個數
• 將n + 2邊的凸多邊形分成三角形的方法個數

思路視覺化

(0,0)>(n,n)方格，不越過對角線個數

5*5，一次只能上/右，走到方法132

𝐶𝑛=(2n)!/(n+1)!n!, n = 6 (5條線6個點)
=12!/7!6!
=132

Python

• Formula
  TC: O(n), SC: O(1)

from math import factorial

def CatalnNumber(num):
  return int(factorial(2 * num) / (factorial(num + 1) * factorial(num)))

• DP
  TC: O(nˆ2), SC: O(n)

class Solution:
    def CatalnNumber(self, n: int) -> int:
		# Base case is dp[0] is 1.
        dp = [1] + ([0] * n)
        for i in range(1, n + 1):
            for j in range(i):
                dp[i] += dp[j] * dp[i - 1 - j]
        return dp[n]

Java

class CatalnNumber {
    /*factorial*/
    static int factorial(int n){    
        if (n == 0) return 1;    
        else return(n * factorial(n-1));
    }    
    public static void main(String[] args) {
        int i,fact=1; // i not initial
        int num=6; 
        fact = factorial(num);   
        //System.out.println("Factorial of "+num+" is: "+fact);   
        System.out.println(factorial(2*num) / (factorial(num + 1) * factorial(num)));
    }
}


class CatalnNumber {
    int catalan(int n) {
        int res = 0;
        if (n <= 1) {return 1;}
        for (int i = 0; i < n; i++) {
            res += catalan(i) * catalan(n - i - 1);
        }
        return res;
    }
  
    public static void main(String[] args) {
        int n = 10;
        CatalnNumber cn = new CatalnNumber();
        for (int i = 0; i < n; i++) {
            System.out.print(cn.catalan(i) + " ");
        }
    }
}

相似

• 22
  Number is catanlan
  1(1), 2(2), 3(5), 4(14)

from typing import List
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        def dfs(left, right, temp):
            if left:
                dfs(left-1, right, temp + "(")
            if right and left < right:
                dfs(left, right-1, temp + ")")
            if not right:
                res.append(temp)
            return res        
        return dfs(n, n, "") # n left, right
print(Solution().generateParenthesis(4))
> 
['(((())))', '((()()))', '((())())', '((()))()', '(()(()))', '(()()())', '(()())()', '(())(())', '(())()()', '()((()))', '()(()())', '()(())()', '()()(())', '()()()()']

• 95

class Solution:
    def generateTrees(self, n: int) -> List[TreeNode]:
        def dfs(start, end):
            if start > end:return [None]	
            if start == end:return [TreeNode(start)]
            
            ret = []
            for i in range(start, end+1):
                left = dfs(start, i-1)
                right = dfs(i+1, end)
                for pair in product(left, right):
                    ret.append(TreeNode(i, pair[0], pair[1]))
            return ret
        
        return  dfs(1,n)
>
[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

• 96
• 241

class Solution(object):
    def diffWaysToCompute(self, inp):
        ops = {
            '-': lambda x, y: x - y,
            '+': lambda x, y: x + y,
            '*': lambda x, y: x * y,
            }
        def helper(l, r):
            ans = []
            for i in range(l, r):
                if inp[i] not in ops: # skip number
                    continue
                # handle operator, shift ()  
                # ans += [ops[inp[i]](le, ri) for le in helper(l, i) for ri in helper(i + 1, r)]
                
                for le in helper(l, i):
                    for ri in helper(i + 1, r):
                        ans.append(ops[inp[i]](le, ri))
                        
            return ans if len(ans) != 0 else [int(inp[l:r])]
        return helper(0, len(inp)) # "2-1-1"

• 894

class Solution:
    def allPossibleFBT(self, N: int) -> List[TreeNode]:
        if N % 2 == 0: return [] # binary tree + root should be odd
        trees_all = collections.defaultdict(list)
		
        trees_all[1] = [TreeNode(0)]
        for n in range(3, N+1, 2):
            for k in range(1, n, 2):
				# consider all potential pairs
                for tree1, tree2 in itertools.product(trees_all[k], trees_all[n-k-1]):
                    tree = TreeNode(0)
                    tree.left = tree1
                    tree.right = tree2
                    trees_all[n].append(tree)
                    
        return trees_all[N]

---

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)