Aperçu

Il semble que des tests de codage soient menés à l'étranger lors d'entretiens d'ingénieurs, et dans de nombreux cas, l'essentiel est de mettre en œuvre des fonctions et des classes spécifiques en fonction du thème.

Apparemment, de nombreux ingénieurs prennent des mesures sur le site appelé LetCode.

C'est un site qui forme la puissance de l'algorithme qui peut résister au test de codage effectué au début, et c'est un chemin inévitable pour ceux qui veulent faire carrière dans une entreprise de technologie à l'étranger.

Je l'ai écrit en grand, mais je n'ai pas l'intention d'avoir une telle interview pour le moment.

Cependant, en tant qu'ingénieur informatique, il serait préférable d'avoir le même niveau de puissance d'algorithme qu'une personne, alors j'aimerais résoudre le problème de manière irrégulière et écrire la méthode que je pensais à l'époque sous forme de mémo.

Leetcode

Je le résolve avec Python3.

Table de codes Leet commençant à zéro

Dernière fois Leet Code Day 79 à partir de zéro "1282. Regrouper les personnes en fonction de la taille du groupe à laquelle elles appartiennent"

Twitter Je le fais.

** Blog technique Commencé! !! ** ** Je pense que la technologie écrira sur LetCode, Django, Nuxt, etc. ** C'est plus rapide à mettre à jour **, merci pour votre coopération!

#problème 703. Kth Largest Element in a Stream Le niveau de difficulté est facile.

Le problème est de concevoir une classe qui trouve le «k» plus grand élément du flux. Notez qu'il s'agit du «k» élément le plus grand dans l'ordre de tri, et non du «k» élément différent.

KthLargest a un constructeur qui accepte l'entier k et le tableau d'entiers nums contenant les éléments initiaux du flux. Renvoie l'élément.

Example:

int k = 3; int[] arr = [4,5,8,2]; KthLargest kthLargest = new KthLargest(3, arr); kthLargest.add(3); // returns 4 kthLargest.add(5); // returns 5 kthLargest.add(10); // returns 5 kthLargest.add(9); // returns 8 kthLargest.add(4); // returns 8

Le point est, veuillez implémenter le constructeur et la méthode ʻadd`.

J'ai traité ce problème car il était répertorié dans la collection de problèmes Let Code recommandée par ceux qui ont réussi l'entretien de codage de Google.

Leet Code 60 questions que vous souhaitez résoudre pour la préparation des entretiens de codage

Cela semble intéressant, alors je pense que je vais essayer de le résoudre. Je n'ai résolu que de nouveaux problèmes ces derniers temps, et il semble que ce sera une initiative intéressante pour la première fois depuis longtemps.

Solution

En raison du problème de tas, j'utilise le tas tranquillement. Cela s'appelle également une file d'attente prioritaire.

À première vue, ce problème semble facile.

Après avoir ajouté un élément à chaque fois, triez-le et renvoyez l'élément de «k-1» à partir de celui-ci, non? Il semble que ce sera le cas, mais comme le processus de tri est lourd, je pense que le temps s'écoulera normalement.

Par exemple, le traitement est le suivant.

def add(val):
    lists.append(val)
    self.lists.sort()
    return self.lists[self.num-1]

Cela triera chaque fois que ʻadd` est appelé, et plus il y a d'éléments, plus il sera lourd.

Ainsi, lorsque vous ajoutez un élément depuis le début, vous n'avez pas à le trier si vous le gérez en utilisant une file d'attente prioritaire, non? C'est.

J'ai écrit le code suivant en supposant qu'il utilise le tas.

import heapq

class KthLargest:
    def __init__(self, k: int, nums: List[int]):
        self.lists,self.num = [],k
        for i in nums:
            self.add(i)

    def add(self, val: int) -> int:
        heapq.heappush(self.lists, val)
        if len(self.lists) > self.num: 
            heapq.heappop(self.lists)
        return self.lists[0]

# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)
# Runtime: 136 ms, faster than 45.40% of Python3 online submissions for Kth Largest Element in a Stream.
# Memory Usage: 17.6 MB, less than 78.45% of Python3 online submissions for Kth Largest Element in a Stream.

En faisant cela, tous les éléments du premier élément donné sont traités comme un tas, et jusqu'à ce que la valeur de la longueur de lists devienne la même valeur que num, pop, c'est-à-dire que la valeur minimale est extraite de la liste. Le processus est très fluide.

Je pensais que je l'écrivais, mais je pense que je l'avais à peine écrite dans le tas, donc c'était une bonne étude à revoir.

Alors c'est tout pour cette fois. Je vous remercie pour votre travail acharné.

Let Code Day 80 "703. Kth plus grand élément d'un flux" à partir de zéro

Aperçu

Solution