LeetCode의 Unique Binary Search Trees

원제:
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

이 문제는 비교적 간단하다. 귀속으로 직접 해결하고 시간 초과를 방지하기 위해서는 기록을 하나 더 넣어야 한다.
문제 해결 방법:
1 대 1 - n의 모든 수는 루트 노드일 수 있다. 그리고 그보다 작은 것은 반드시 이 루트 노드의 왼쪽에 있고, 그보다 큰 것은 루트 노드의 오른쪽에 있다.
2 요소가 하나만 있으면 1 반환
3 내가 사용하는 것은 비교적 멍청한 방법이다. 예를 들어 대수조 1-n, 현재 i는 뿌리 노드이고 1~i-1은 모두 왼쪽 노드이고 i+1~n은 모두 오른쪽 노드이다. 그리고 좌우 노드를 각각 귀속 처리하면 된다. 그리고 좌우 나무의 결과를 i를 뿌리 노드로 곱한 상황수
4 i를 1부터 n까지의 모든 상황을 합치면 마지막 결과입니다.
5 나는 2차원수 그룹 record[][],record[i][j]는 시작점이 i이고 끝점이 j의 모든 가능한 수를 나타낸다. 만약에 i>j설명이 경계 상황을 고려하고 있다면(예를 들어 1이나 n을 고려하고 있다면), 1설명을 되돌려주는 것은 그의 왼쪽 나무나 오른쪽 나무의 상황이다(비어 있고 단지 하나의 상황만 있다)
코드는 다음과 같습니다(12ms).

class Solution {
public:
    int numTrees(int n) {
        int ** record = new int*[n+1];
        for(int i = 0; i <= n ;i++){
            record[i] = new int [n+1]();
        }
        for(int i = 0 ;i <=n ; i++){
            for(int j = 0; j<=n;j++){
                record[i][j]=-1;
            }
        }
        
        return getNum(1,n , record);
    }
    int getNum(int start , int end , int **record){
        if(start >= end) return 1;
        if(record[start][end] >0 ) return record[start][end]; 
        
        int result = 0;
        for(int i = start ; i<= end ; i++){
            result += getNum(start , i-1 , record) * getNum(i+1, end , record);
        }
        record[start][end] = result;
        return result;
    }
};

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)

이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

LeetCode의 Unique Binary Search Trees

좋은 웹페이지 즐겨찾기