Compte tenu d'un tableau d'entiers Maintenant, si notre entrée est modifiée en [5,1,6], notre structure BST sera toujours identique.
Ainsi, étant donné un éventail d'entiers, comment trouver le nombre de différentes permutations de la matrice d'entrée qui entraîne la BST identique comme la BST formée sur l'ordre de matrice d'origine? arr = [5, 6, 1] . Lorsque nous construisons une BST avec cette entrée dans le même ordre, nous aurons «5» en tant que root, «6» comme enfant droit et «1» comme enfant gauche.
4 Réponses :
Vous pouvez le faire en arrière: étant donné une BST, énumérer tous les tableaux d'entiers pouvant donner cette BST ...
ne pouviez-vous pas (utiliser le non-déterminant ...)
Le nondéterminisme vous donnera toutes ces tableaux. Ensuite, vous pouvez les compter.
Pourquoi le nondéterminisme est-il nécessaire?
Ce n'est pas vraiment. Je pensais beaucoup au nondéterminisme en 2009. Cela convient bien à ce problème - essayez-vous une chose, émettant le résultat, puis replacez-le à un état antérieur (où l'état est (ensemble de nœuds visités, chemin jusqu'à présent)).
Votre question est équivalente à la question de compter le nombre de commandes topologiques pour la BST donnée.
Par exemple, pour la BST P>
Ord(15) = 1 Ord(30) = 1 Ord(20) = 1 x 1 x INT(1, 1) = 2 ; INT(1, 1) = 2! / 1 = 2 Ord(7) = 1 Ord(5) = 1 Ord(10) = 1 x 2 x INT(2, 3) = 2 x 5! / (2! x 3!) = 2 x 120 / 12 = 2 x 10 = 20
D'où avez-vous obtenu cette relation (l r int (| l |, | r |) et pourquoi INT (A, B) = (A + B)! / (A + B)! / (A! * B!)
lxrx int (| l |, | r |) vient de (1) "L" façons différentes de commander la séquence qui produit le sous-arbre à gauche, (2), "R" Différentes façons de commander la séquence qui produit le bon sous-arbre, et (3) INT (| L |, | R |) Différentes façons de mélanger ces deux séquences, c'est-à-dire les entrelacer. Int (A, B) = (A + B)! / (A! B!) Parmi tous les entrelacements d'éléments A + B, nous ne sommes intéressés que dans ceux où la séquence d'éléments A a une commande fixe, ideme pour la séquence d'éléments b, divisez donc par A! et B! séparément.
Merci pour l'explication Anti.Huima! Cela m'a aidé à comprendre. Voici quelques-unes C ++:
#include <vector>
#include <iostream>
using namespace std;
int factorial(int x) {
return (x <= 1) ? 1 : x * factorial(x - 1);
}
int f(int a, int b) {
return factorial(a + b) / (factorial(a) * factorial(b));
}
template <typename T>
int n(vector<T>& P) {
if (P.size() <= 1) return 1;
vector<T> L, R;
for (int i = 1; i < P.size(); i++) {
if (P[i] < P[0])
L.push_back(P[i]);
else
R.push_back(P[i]);
}
return n(L) * n(R) * f(L.size(), R.size());
}
int main(int argc, char *argv[]) {
vector<int> a = { 10, 5, 7, 20, 15, 30 };
cout << n(a) << endl;
return 0;
}
factorial pourrait avoir un problème de surplex
Cette question peut être résolue facilement si vous connaissez peu de connaissance de la récursion, de la permutation et des combinaisons et la familiarité avec l'arbre de recherche binaire (évidemment).
Vous construisez d'abord un arbre de recherche binaire avec la séquence donnée. Vous pouvez également effectuer la même opération dans la matrice, mais la visualisation de l'arborescence brosserait une bonne image. P>
pour la séquence donnée arr [1..n], le 1er élément resterait mis comme dans le tableau donné et seul dispositif doit être amené en arr [2....n]. p>
supposons: p>
sac1 = nombre d'éléments en arr [2....n] qui sont inférieurs à ARR [0]. P>
et, p>
sac2 = nombre d'éléments en arr [2....n] qui sont supérieurs à arr [0]. P>
depuis La permutation des éléments de sac1 dans la séquence ne posera pas de conflit avec les chiffres présents dans le sac2 tout en formant une arborescence de recherche binaire, on peut commencer à commencer à calculer la réponse par Picking Bag1 éléments de (n-1) Éléments à permuter forts> et Puisque chaque sous-arbre d'un arbre de recherche binaire doit être une BST. Un processus similaire serait utilisé sur chaque nœud et multiplier la réponse locale du nœud à la réponse finale. P> int ans = 1;
int size[1000000] = {0};
// calculate the size of tree and its subtrees before running function "fun" given below.
int calSize(struct node* root){
if(root == NULL)
return 0;
int l = calSize(root->left);
int r = calSize(root -> right);
size[root->val] = l+r+1;
return size[root->val];
}
void fun(struct node* root){
if(root == NULL)
return;
int n = size[root->val];
if(root->left){
ans *= nCr(n-1, size[root->left]);
ans *= 1; // (Just to understand that there is now only 1 way
//to distribute the rest (n-1)-size of root->left)
}
fun(root->left);
fun(root->right);
}
int main(){
struct node* root;
//construct tree
//and send the root to function "fun"
fun(root);
cout<<ans<<endl;
return 0;
}