Parlez avec vous série #2

Introduction

Aujourd'hui, nous allons lancer notre aperçu des concepts utilisés pour résoudre divers problèmes algorithmiques. La compréhension d'un certain concept peut vous donner une intuition sous quel angle commencer à réfléchir à la solution potentielle.

Il existe différents concepts, mais pas trop. Aujourd'hui, je vais investir votre attention dans le concept de fenêtre coulissante.

Fenêtre coulissante

Le concept de la fenêtre coulissante est un peu plus complexe qu'à première vue. Je vais le démontrer à l’aide d’exemples pratiques. Pour l’instant, gardez à l’esprit que l’idée conceptuelle est que nous aurons une fenêtre que nous devrons déplacer. Commençons tout de suite par l'exemple.

Supposons que vous disposiez d'un tableau d'entiers et d'une taille prédéfinie des sous-tableaux. Il vous est demandé de trouver un tel sous-tableau (alias fenêtre) dont la somme de valeurs serait maximale parmi d'autres.

array = [1, 2, 3]
window_size = 2

# conceptually
subarray_1 = [1, 2] --> sum 3
subarray_2 = [2, 3] --> sum 5

maximum_sum = 5

Eh bien, cela semble assez simple :
(1) fenêtre coulissante de taille 2
(2) 2 sous-tableaux
(3) compter la somme de chacun
(4) trouver le max entre eux

Mettez-le en œuvre.

def foo(array: List[int], size: int) -> int:
    maximum = float("-inf")

    for idx in range(size, len(array)+1):
        left, right = idx-size, idx
        window = array[left:right]
        maximum = max(maximum, sum(window))

    return maximum 

Eh bien, il semble que nous ayons simplement utilisé efficacement le concept de fenêtre coulissante. En fait, pas exactement. Nous pourrions en obtenir une « preuve » en comprenant la complexité temporelle de la solution.

La complexité sera O(l)*O(w), où l est le nombre de fenêtres dans le tableau et w est le nombre d'éléments dans la fenêtre. En d’autres termes, nous devons parcourir l fenêtres et pour chaque l-ème fenêtre, nous devons calculer la somme des w éléments.

Qu’est-ce qui est discutable ici ? Décrivons conceptuellement les itérations pour répondre à la question.

array = [1, 2, 3, 4]
window_size = 3

iterations
1 2 3 4 5
|___|
  |___|
    |___|  

La réponse est que même si nous faisons glisser le tableau, à chaque itération, nous devons "recalculer" k-1 éléments qui ont déjà été calculés lors de l'itération précédente.

Au fond, cet aperçu devrait nous suggérer de poser une question :

"existe-t-il un moyen de profiter des calculs de l'étape précédente ?"

La réponse est oui. Nous pouvons obtenir la somme des éléments de la fenêtre en ajoutant et en soustrayant le premier et le suivant après les éléments de la fenêtre. Permettez-moi de mettre cette idée dans le code.

def foo(array: List[int] = None, size: int = 0) -> int
    window_start, max_, window_sum_ = 0, float("-inf"), 0
    for window_end in range(len(array)):
        if window_end > size - 1:
            window_sum_ -= array[window_start]
            window_start += 1
        window_sum_ += array[window_end]
        max_ = max(max_, window_sum_)
    return max_

assert foo(array=[1, 2, 3, 4], size=3) == 9

Ici, nous pourrions voir, au moment où nous avons construit le sous-tableau de longueur de taille, nous avons commencé à soustraire le tout premier élément de la somme de la fenêtre, ce qui nous permet de réutiliser les calculs de l'étape précédente.

Maintenant, nous pourrions dire que nous avons utilisé efficacement le concept de fenêtre glissante alors que nous avons obtenu une preuve vérifiant la complexité temporelle, qui est passée de O(l*w) à O(l), où l est le nombre de fenêtres que nous allons glisser.

L'idée majeure que je voudrais souligner, le concept de fenêtre coulissante ne consiste pas seulement à découper l'itérable avec la fenêtre de taille spécifique.

Permettez-moi de vous présenter quelques problèmes, où nous apprendrons comment détecter le problème peut impliquer un concept de fenêtre coulissante ainsi que ce que vous pourriez faire exactement avec la fenêtre elle-même.

Aperçu des problèmes

Puisque je ne parle ici que de concepts, je sauterais "comment compter quelque chose à l'intérieur de la fenêtre".

Problème un

Étant donné un tableau, trouvez la moyenne de tous les sous-tableaux contigus de taille K qu'il contient.

1. Fenêtre coulissante ? - contiguous subarrays le premier mot-clé, ce qui signifie qu'il faut s'occuper des fenêtres, qui représenteraient un ou plusieurs sous-tableaux contigus.
2. Connaissons-nous la taille de la fenêtre coulissante ? - ouais, K, nous avons la taille de la fenêtre, qui devrait être la longueur de K.
3. Que sommes-nous censés gérer/vérifier exactement dans une fenêtre glissante ? - trouver la moyenne de...

Bien, maintenant nous pourrions définir l'approche de la manière suivante : parcourir le tableau d'entrée avec la fenêtre de taille K. À chaque itération, comptez la moyenne de la fenêtre...

Problème deux

Étant donné un tableau de nombres positifs et un nombre positif K, trouvez la somme maximale de tout sous-tableau contigu de taille K.

1. Fenêtre coulissante ? - encore une fois les sous-tableaux contigus, le premier mot-clé, signifiant qu'il faut s'occuper des fenêtres, qui représenteraient un ou plusieurs sous-tableaux contigus.
2. Connaissons-nous la taille de la fenêtre coulissante ? - ouais, K, nous avons la taille de la fenêtre, qui devrait être la longueur de K.
3. Que sommes-nous censés gérer/vérifier exactement dans une fenêtre glissante ? - .. la somme...

Maintenant : parcourez le tableau d'entrée avec la fenêtre de taille K. A chaque itération comptez la somme de la fenêtre...

Troisième problème

Étant donné un tableau de nombres positifs et un nombre positif S, trouvez la longueur du plus petit sous-tableau contigu dont la somme est supérieure ou égale à S.

1. Fenêtre coulissante ? - encore une fois les sous-tableaux contigus, le premier mot-clé, signifiant qu'il faut s'occuper des fenêtres, qui représenteraient un ou plusieurs sous-tableaux contigus.
2. Connaissons-nous la taille de la fenêtre coulissante ? - en fait non, nous devons le découvrir.
3. Que sommes-nous censés gérer/vérifier exactement dans une fenêtre glissante ? - ... la somme est >= à S ...

Maintenant, nous pourrions définir l'approche de la manière suivante : "tout d'abord, parcourez le tableau d'entrée et construisez une telle première fenêtre, qui satisferait aux conditions (la somme est >= à S). Une fois cela fait, déplacez la fenêtre, gérez la fenêtre début et fin..."

Problème quatre

Étant donné une chaîne, trouvez la longueur de la sous-chaîne la plus longue ne contenant pas plus de K caractères distincts.

1. Fenêtre coulissante ? - la sous-chaîne la plus longue, le premier mot-clé, ce qui signifie qu'il faut s'occuper de windows, qui représenterait une sous-chaîne.
2. Connaissons-nous la taille de la fenêtre coulissante ? - non, nous devons le découvrir.
3. Que sommes-nous censés gérer/vérifier exactement dans une fenêtre glissante ? - ... quantité de caractères distincts...

L'approche ici est un peu plus complexe, je vais donc la sauter ici.

Problème cinq

Étant donné un tableau d'entiers où chaque entier représente un arbre fruitier, vous recevez deux paniers, et votre objectif est de mettre le maximum de fruits dans chaque panier. La seule restriction est que chaque panier ne peut contenir qu'un seul type de fruit.
Vous pouvez commencer avec n’importe quel arbre, mais vous ne pouvez pas sauter un arbre une fois que vous avez commencé. Vous cueillirez un fruit de chaque arbre jusqu'à ce que vous ne puissiez plus, c'est-à-dire que vous vous arrêterez lorsque vous devrez cueillir un troisième type de fruit.
Écrivez une fonction pour renvoyer le nombre maximum de fruits dans les deux paniers.

Cela ne semble pas si évident, simplifions d'abord les conditions.

Il existe un tableau d'entrée. Le tableau peut contenir seulement 2 chiffres distincts (compartiments). Il vous est demandé de trouver un tel sous-réseau contigu dont la longueur serait maximale.

Il est désormais plus facile de voir que nous pourrions travailler avec le concept de fenêtre coulissante.

1. Fenêtre coulissante ? - sous-réseau contigu
2. Connaissons-nous la taille de la fenêtre coulissante ? - non, nous devons le découvrir.
3. Que sommes-nous censés gérer/vérifier exactement dans une fenêtre glissante ? - ... si les chiffres sont distincts et la longueur de la fenêtre ...

Problème six

Étant donné une chaîne et un motif, découvrez si la chaîne contient une permutation du motif.

Tout d'abord, nous avons 2 ficelles, originales et à motifs. Nous savons que nous devons d'une manière ou d'une autre comparer l'original et le motif, ce qui a conduit à l'idée, nous devons construire la fenêtre de taille du motif et effectuer ensuite une vérification des permutations. Cela signifie que nous pourrions utiliser le concept de fenêtre coulissante.

Sortie

Lorsque vous traitez avec une fenêtre coulissante, gardez à l'esprit les questions suivantes :

• Comprenez-vous la taille de la fenêtre
• Comprenez-vous comment construire la fenêtre
• Comprenez-vous comment déplacer/réduire la fenêtre
• Comprenez-vous ce qu'est une fenêtre valide/invalide
• Comprenez-vous comment rendre une fenêtre invalide valide

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!