當前位置:網站首頁>【LeetCode】Day59-醜數 & 不同的二叉搜索樹

【LeetCode】Day59-醜數 & 不同的二叉搜索樹

2022-05-14 00:21:13倒過來是圈圈

題目1

264. 醜數 II【中等】

題解

看完才發現,和之前做的這道一樣,只不過前一道是劍指offer裏的,這道是力扣自己的…詳細題解看鏈接裏那道就行

狀態定義:dp[i] 錶示第 i 個醜數

class Solution {
    
    public int nthUglyNumber(int n) {
    
        int[] dp=new int[n];
        dp[0]=1;
        int a=0,b=0,c=0;
        for(int i=1;i<n;i++){
    
            int n2=dp[a]*2,n3=dp[b]*3,n5=dp[c]*5;
            dp[i]=Math.min(n2,Math.min(n3,n5));
            if(dp[i]==n2)   a++;
            if(dp[i]==n3)   b++;
            if(dp[i]==n5)  c++;
        }
        return dp[n-1];
    }
}

時間複雜度: O ( n ) O(n) O(n)

空間複雜度: O ( n ) O(n) O(n)

題目2

96. 不同的二叉搜索樹【中等】

題解

動態規劃

首先複習一下二叉搜索樹的概念,

二叉查找樹(英語:Binary Search Tree),也稱為 二叉搜索樹、有序二叉樹(Ordered Binary Tree)或排序二叉樹(Sorted Binary Tree),是指一棵空樹或者具有下列性質的二叉樹:

  1. 若任意節點的左子樹不空,則左子樹上所有節點的值均小於它的根節點的值;
  2. 若任意節點的右子樹不空,則右子樹上所有節點的值均大於它的根節點的值;
  3. 任意節點的左、右子樹也分別為二叉查找樹;
  4. 沒有鍵值相等的節點。

接著,用動態規劃解這道題(不看題解真的不會啊嗚嗚),
在這裏插入圖片描述
綜合兩個公式可以得到卡特蘭數公式,G(n)即定義的狀態,求解這道題:
G ( n ) = G ( 0 ) ∗ G ( n − 1 ) + G ( 1 ) ∗ G ( n − 2 ) + . . . + G ( n − 1 ) ∗ G ( 0 ) G(n)=G(0)*G(n-1)+G(1)*G(n-2)+...+G(n-1)*G(0) G(n)=G(0)G(n1)+G(1)G(n2)+...+G(n1)G(0)

class Solution {
    
    public int numTrees(int n) {
    
        int[] dp=new int[n+1];
        dp[0]=dp[1]=1;
        //i為根節點
        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];
    }
}

時間複雜度: O ( n 2 ) O(n^2) O(n2)

空間複雜度: O ( n ) O(n) O(n)

卡特蘭數

考研時候學的東西怕是都還給當時的自己了…

n個結點的二叉搜索樹的個數為卡特蘭數,直接套公式就出來了
在這裏插入圖片描述

class Solution {
    
    public int numTrees(int n) {
    
        long C=1;//用long防止計算過程中的溢出
        for(int i=1;i<n;i++){
    
            C=2*(2*i+1)*C/(i+2);
        }
        return (int)C;
    }
}

時間複雜度: O ( n ) O(n) O(n)

空間複雜度: O ( 1 ) O(1) O(1)

版權聲明
本文為[倒過來是圈圈]所創,轉載請帶上原文鏈接,感謝
https://cht.chowdera.com/2022/134/202205140020143588.html

隨機推薦