Comprendre les modèles d'éléments K dans LeetCode : les bases (partie 1)

Je comprends enfin ! La meilleure façon d'apprendre LeetCode n'est pas de résoudre problème après problème, en prenant parfois une heure entière pour les résoudre de manière inefficace. La clé pour maîtriser LeetCode est l’étude des modèles. Étudions-en un commun !

Les enquêteurs adorent poser des questions sur la recherche, la maintenance ou la manipulation de K éléments dans une chaîne ou un tableau. Au début, je pensais que chaque problème était totalement différent, mais ensuite j'ai commencé à voir les liens. Laissez-moi vous montrer ce que je veux dire avec deux problèmes qui m'ont vraiment aidé à comprendre ce modèle.

Problème 1 : Trouver la sous-séquence de longueur K avec la plus grande somme

Il s'agit techniquement d'une question de niveau « facile » (posée seulement par une seule entreprise), mais elle vous apprend tellement de choses sur la façon de réfléchir à ces problèmes d'éléments k !

Ce qu'ils demandent

Vous obtenez un tableau de nombres et une valeur k, et vous devez trouver k nombres dans le tableau qui totalisent la plus grande somme possible. MAIS (et c'est la partie qui m'a fait trébucher au début), il faut garder les numéros dans leur ordre d'origine !

Exemple :

Oh ! celui-ci est plus délicat :

Ok, je comprends

Au début, je pensais "il suffit de prendre les k plus gros nombres, c'est fait !" Mais non, cette exigence de commande change tout. Voici ce qui a finalement cliqué :

1. Nous devons nous rappeler d'où vient chaque numéro, n'est-ce pas ? Donc J'ai pensé : "Je devrais associer chaque numéro avec son position?"

1. Ensuite, nous pouvons trier ces paires par valeurs (c'est le premier numéro de chaque paire), mais nous gardons une trace de d'où ils viennent (c'est le deuxième numéro) !

1. Maintenant, la partie cool - nous n'en avons besoin que de k, alors prenez le k premières paires et gardent simplement leurs positions :

1. Enfin, parcourez le tableau d'origine et ne gardez que numéros dont les positions sont dans notre ensemble :

Voici le code

2 : Kème plus grand élément dans un flux

Ok, donc celui-ci est également étiqueté « facile » (demandé par cinq entreprises), mais celui-ci était plus déroutant pour moi que n'importe lequel des problèmes les plus difficiles de l'élément K.

Ce qu'ils demandent

Imaginez que vous travaillez dans une université et que les étudiants continuent de soumettre leurs résultats aux tests. Votre travail consiste à toujours connaître le score le plus élevé à tout moment. De nouveaux scores continuent d’arriver et vous devez les suivre.

Ils vous donnent des k et quelques scores initiaux, puis ils continuent de vous lancer de nouveaux scores et veulent connaître le kème le plus élevé à chaque fois. Regardons un exemple :

Ok, je pense que j'ai compris

Au début, j'essayais de trier l'ensemble du tableau à chaque fois qu'un nouveau score arrivait, mais je sais que le tri peut être inefficace. Ensuite, je me suis demandé pourquoi est-ce que je garde une trace de tous les scores alors que je ne me soucie que des meilleurs ?

Voici comment je l'ai décomposé :

1. Tout d'abord, triez les scores initiaux et ne gardez que les premiers k :

1. Maintenant, quand un nouveau score arrive :

S'il est plus petit que notre kième plus haut (premier chiffre), ignorez-le
S'il est plus gros, il a sa place quelque part dans notre liste

Voici ce qui se passe à chaque ajout :

Le code

Pourquoi ces deux problèmes sont liés

Les deux problèmes m'ont appris quelque chose de très important sur la gestion des k éléments :

• Premier problème : Parfois, vous devez savoir où se trouvent les éléments je viens de
• Deuxième problème : Parfois, il suffit de conserver k éléments autour

Ces problèmes de l'élément K consistent à être intelligent avec les informations que vous conservez et ce que vous jetez.
La prochaine fois, nous examinerons deux autres problèmes d'éléments k qui s'appuient sur ces idées. J'espère qu'à la fin vous voyez une tendance et que ces types de problèmes semblent moins effrayants !

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!