558. Intersection Quadtree: simple question récursive

Description du sujet

C'est LeetCode Oui. 「558. Intersection Quadtree」 ,La difficulté est 「Moyenne」.

Tag : 「Récursion」

Tous les éléments de la Matrice binaire ne sont pas C'est .

Voici deux quadtrees,quadTree1 Et quadTree2.

Parmi eux quadTree1 Représente un Matrice binaire,Et quadTree2 Représente l'autre Matrice binaire.

Veuillez retourner une représentation Quadtree of Binary Matrix,C'est... quadTree1 Et quadTree2 Les deux matrices binaires représentées sont exécutées Logique ou opération bitwise Les résultats de.

Attention!,Quand isLeaf Pour False Heure,Vous pouvez mettre True Ou False Assigner une valeur au noeud,Les deux valeurs sont déterminées par le mécanisme du problème Accepté .

Dans la structure de données Quadtree,Il n'y a que quatre noeuds enfants par noeud interne.En outre,Chaque noeud a deux propriétés：

• val：Stocke la valeur de la zone représentée par le noeud foliaire. Correspondant à True, Correspondant à False;
• isLeaf: Quand ce noeud est un noeud foliaire True,Si elle a Le noeud enfant est False .

class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;
}

Nous pouvons construire un Quadtree pour une zone 2D en suivant les étapes suivantes ：

1. Si la grille actuelle a la même valeur （C'est - à - dire:,Tout est Ou les deux. ）,Oui. isLeaf Set to True ,Oui. val Définir la valeur pour la grille , Et Réglez les quatre sous - noeuds à Null Et arrête..
2. Si la valeur actuelle de la grille est différente ,Oui. isLeaf Set to False, Oui. val Définir à n'importe quelle valeur ,Ensuite, comme le montre la figure ci - dessous, Diviser la grille actuelle en quatre sous - Grilles .
3. Récursion de chaque noeud enfant à l'aide d'une sous - grille appropriée .

Format Quadtree ：

Sortie sous forme sérialisée d'un Quadtree post - traversée en utilisant la séquence ,Parmi eux null Indique le Terminateur de chemin , Il n'y a pas de noeud en dessous .

C'est très similaire à la sérialisation d'un arbre binaire . La seule différence est que les noeuds sont représentés sous forme de liste [isLeaf, val] .

Si isLeaf Ou val La valeur de True , Indique qu'il est dans la liste  [isLeaf, val] La valeur dans est ;Si isLeaf Ou val La valeur de False ,Alors la valeur est .

Exemple 1：

Entrée：quadTree1 = [[0,1],[1,1],[1,1],[1,0],[1,0]]
, quadTree2 = [[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]

Produits：[[0,0],[1,1],[1,1],[1,1],[1,0]]

Explication：quadTree1 Et quadTree2 Comme indiqué ci - dessus. La Matrice binaire représentée par l'arbre Quadtree a également été donnée .
 Si nous faisons une logique bitwise ou une opération sur ces deux matrices , Vous pouvez obtenir la Matrice binaire suivante , Représenté par un Quadtree comme résultat .
Attention!, La Matrice binaire que nous montrons n'est que pour mieux illustrer le sujet , Vous n'avez pas besoin de construire une Matrice binaire pour obtenir un Quadtree de résultats .

Exemple 2：

Entrée：quadTree1 = [[1,0]]
, quadTree2 = [[1,0]]

Produits：[[1,0]]

Explication： La taille de la matrice représentée par les deux nombres est  1*1,Toutes les valeurs sont 0 
 La taille de la matrice résultante est  1*1,Toutes les valeurs sont 0 .

Exemple 3：

Entrée：quadTree1 = [[0,0],[1,0],[1,0],[1,1],[1,1]]
, quadTree2 = [[0,0],[1,1],[1,1],[1,0],[1,1]]

Produits：[[1,1]]

Exemple 4：

Entrée：quadTree1 = [[0,0],[1,1],[1,0],[1,1],[1,1]]
, quadTree2 = [[0,0],[1,1],[0,1],[1,1],[1,1],null,null,null,null,[1,1],[1,0],[1,0],[1,1]]

Produits：[[0,0],[1,1],[0,1],[1,1],[1,1],null,null,null,null,[1,1],[1,0],[1,0],[1,1]]

Exemple 5：

Entrée：quadTree1 = [[0,1],[1,0],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]
, quadTree2 = [[0,1],[0,1],[1,0],[1,1],[1,0],[1,0],[1,0],[1,1],[1,1]]

Produits：[[0,0],[0,1],[0,1],[1,1],[1,0],[1,0],[1,0],[1,1],[1,1],[1,0],[1,0],[1,1],[1,1]]

Conseils：

• quadTree1 Et quadTree2 Ce sont tous des quadtrees qui répondent aux exigences du sujet , Chacun représente un La matrice de.
• ,Parmi eux

Récursion

Pour plus de commodité,Nous avons ordonné quadTree1 Pour t1,Ordre quadTree2 Pour t2.

Selon le titre, Et utiliser une fonction donnée comme fonction récursive ,Quand t1 Et t2 Lorsque les deux sont le nombre de noeuds foliaires ,Mise en œuvre「Et logique」,Si seulement t1 Et t2 Toute valeur est Heure,Renvoie ce noeud,Sinon（Les deux sont ）, Renvoie n'importe quel noeud .

Ensuite, considérez d'autres situations ,Comment utiliser t1 Et t2 Construire un nouveau noeud ans, Utilisez l'emplacement correspondant pour effectuer 「Récursion」Construit.（Prêt à l'emploi t1.topLeft Et t2.topLeft Pour attribuer une valeur à ans.topLeft, Les autres positions sont identiques ）, Notez qu'il peut y avoir t1 Ou t2 Si l'un des noeuds est un noeud de feuille , Le noeud enfant actuel de la feuille et le noeud enfant d'un autre noeud doivent être utilisés pour la construction .

Enfin, considérez les circonstances , Un nouveau noeud foliaire ：Si le noeud actuel ans Les quatre noeuds enfants de sont des noeuds foliaires , Et avec la même valeur ,ans Sera un noeud foliaire ,ans La valeur est la valeur du noeud foliaire , L'action à effectuer à ce stade est de isLeaf Set to True,Modifier val Est la valeur du noeud atomique , Laissez les quatre noeuds atomiques vides .

Java Code：

class Solution {
    public Node intersect(Node t1, Node t2) {
        if (t1.isLeaf && t2.isLeaf) {
            if (t1.val) return t1;
            else if (t2.val) return t2;
            else return t1;
        }
        Node ans = new Node();
        ans.topLeft = intersect(t1.isLeaf ? t1 : t1.topLeft, t2.isLeaf ? t2 : t2.topLeft);
        ans.topRight = intersect(t1.isLeaf ? t1 : t1.topRight, t2.isLeaf ? t2 : t2.topRight);
        ans.bottomLeft = intersect(t1.isLeaf ? t1 : t1.bottomLeft, t2.isLeaf ? t2 : t2.bottomLeft);
        ans.bottomRight = intersect(t1.isLeaf ? t1 : t1.bottomRight, t2.isLeaf ? t2 : t2.bottomRight);
        boolean a = ans.topLeft.isLeaf && ans.topRight.isLeaf && ans.bottomLeft.isLeaf && ans.bottomRight.isLeaf;
        boolean b = ans.topLeft.val && ans.topRight.val && ans.bottomLeft.val && ans.bottomRight.val;
        boolean c = ans.topLeft.val || ans.topRight.val || ans.bottomLeft.val || ans.bottomRight.val;
        ans.isLeaf = a && (b || !c);
        ans.val = ans.topLeft.val;
        if (ans.isLeaf) ans.topLeft = ans.topRight = ans.bottomLeft = ans.bottomRight = null;
        return ans;
    }
}

TypeScript Code：

function intersect(t1: Node | null, t2: Node | null): Node | null {
    if (t1.isLeaf && t2.isLeaf) {
        if (t1.val) return t1
        else if (t2.val) return t2
        else return t1
    }
    const ans: Node = new Node()
    ans.topLeft = intersect(t1.isLeaf ? t1 : t1.topLeft, t2.isLeaf ? t2 : t2.topLeft)
    ans.topRight = intersect(t1.isLeaf ? t1 : t1.topRight, t2.isLeaf ? t2 : t2.topRight)
    ans.bottomLeft = intersect(t1.isLeaf ? t1 : t1.bottomLeft, t2.isLeaf ? t2 : t2.bottomLeft)
    ans.bottomRight = intersect(t1.isLeaf ? t1 : t1.bottomRight, t2.isLeaf ? t2 : t2.bottomRight)
    const a: boolean = ans.topLeft.isLeaf && ans.topRight.isLeaf && ans.bottomLeft.isLeaf && ans.bottomRight.isLeaf
    const b: boolean = ans.topLeft.val && ans.topRight.val && ans.bottomLeft.val && ans.bottomRight.val
    const c: boolean = ans.topLeft.val || ans.topRight.val || ans.bottomLeft.val || ans.bottomRight.val
    ans.isLeaf = a && (b || !c)
    ans.val = ans.topLeft.val
    if (ans.isLeaf) ans.topLeft = ans.topRight = ans.bottomLeft = ans.bottomRight = null
    return ans
};

• Complexité temporelle： La complexité est liée à la taille finale de la matrice , Et la taille finale de la matrice ne dépassera pas la taille originale de la matrice ,La complexité est
• Complexité spatiale：Ignorer les frais généraux d'espace supplémentaires causés par la récursion,La complexité est

Plus de repas

「 L'autre aussi 「Quadtree」 Questions d'application récursives pertinentes : 【 Questions complètes de stylo 】Difficulté 2/5, Application récursive et préfixe et optimisation 」

Enfin

C'est nous「Brossage LeetCode」Numéro de la série No.558 Articles,La série commence à 2021/01/01,Jusqu'à la date de début LeetCode Il y a 1916 Sujet,Il y a en partie un problème de verrouillage,Nous allons d'abord brosser tous les problèmes sans serrure.

Dans cette série d'articles,En plus d'expliquer les idées de résolution de problèmes,Le Code le plus concis possible.Si une solution générique est impliquée, le modèle de code correspondant.

Afin de faciliter le débogage et la soumission de code par ordinateur,J'ai construit l'entrepôt associé：https://github.com/SharingSource/LogicStack-LeetCode .

À l'adresse de l'entrepôt,.Vous pouvez voir des liens vers des articles de la série、Code correspondant à la série d'articles、LeetCode Liens vers les sujets originaux et autres solutions préférées.

Plus, plus complet, plus chaud「Examen écrit/Interview」Les informations pertinentes peuvent être consultées Rassembler la nouvelle base