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 d'implémenter 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 algorithmique qui peut résister au test de codage effectué au début de l'histoire, et c'est une voie 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'un être humain, donc 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.
Je le résolve avec Python3.
Table de codes Leet commençant à zéro
Dernière fois Leet Code Day59 à partir de zéro "1221. Split a String in Balanced Strings"
À l'heure actuelle, je donne la priorité au moyen des 100 questions les plus appréciées. Easy a été résolu, donc si vous êtes intéressé, veuillez vous rendre à la table.
Twitter Je le fais.
Des articles d'environ 2 mois ont été collectés. Je suis surpris que cela continue jusqu'à présent.
1481. Least Number of Unique Integers after K Removals
Le niveau de difficulté est moyen. C'est un problème assez nouveau qui a été ajouté récemment.
Le problème est donné le tableau ʻarret l'entierk`. Le problème est de concevoir un algorithme qui trouve le nombre minimum d'entiers uniques après avoir supprimé la valeur «k» des éléments du tableau.
C'est un peu déroutant, alors regardons un exemple.
Input: arr = [5,5,4], k = 1 Output: 1 Explanation: Remove the single 4, only 5 is left.
Dans cet exemple, un élément est seulement «4» dans le tableau. Supprimez donc 4. Puisque le seul élément restant est «5», «5» est renvoyé tel quel.
Input: arr = [4,3,1,1,3,3,2], k = 3 Output: 2 Explanation: Remove 4, 2 and either one of the two 1s or three 3s. 1 and 3 will be left.
Il est décidé de supprimer "4" et "2", mais le dernier supprime "1" ou "3". «1» ou «3» reste, mais la longueur du numéro unique lui-même est «2», il est donc renvoyé.
Cette fois, nous retournerons un entier, et peu importe la façon dont nous gérons le tableau, cela n'affectera pas la réponse, donc j'ai pensé qu'il serait plus facile de comprendre si nous le triions tôt.
Si l'exemple ʻarr = [4,3,1,1,3,3,2] , que feriez-vous si vous triez comme ʻarr = [1,1,2,3,3,4]? Ce sera évident si vous devez le supprimer.
Eh bien, si je l'écris rapidement, le problème cette fois est de comparer le «k» donné avec le nombre d'éléments, et si «k» est plus que le nombre d'éléments, de «k» à «k» + Soustrayez le nombre d'éléments et comptez le nombre de soustractions. Et enfin, vous pouvez soustraire le nombre de fois que vous avez soustrait de la longueur du tableau trié d'origine.
Cependant, je ne pense pas que je puisse comprendre honnêtement même si cela est écrit, alors jetons un coup d'œil au code réel.
import collections
class Solution:
def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
sorted_counts,removed_counts = sorted(Counter(arr).items(),key=lambda x: x[1]),0
for keys,values in sorted_counts:
if k >= values:
k -= values
removed_counts += 1
return len(sorted_counts) - removed_counts
# Runtime: 496 ms, faster than 92.08% of Python3 online submissions for Least Number of Unique Integers after K Removals.
# Memory Usage: 32.9 MB, less than 33.33% of Python3 online submissions for Least Number of Unique Integers after K Removals.
En Python, il existe une bibliothèque pratique appelée Compteur de collections, c'est donc une bonne idée de compter chaque nombre pour le moment.
Dans le cas de l'exemple 1, ce sera comme suit.
Counter({5: 2, 4: 1})
Et si vous triez cela par la valeur de clé, ce sera comme suit.
[(4, 1), (5, 2)]
Au fait, si vous n'écrivez pas beaucoup de Python, jetez un coup d'œil à la partie de tri.
sorted_counts = sorted(Counter(arr))
# [4,5]
Vous voudrez peut-être écrire, mais dans ce cas, la sortie sera «[4,5]» et le nombre sera épuisé, donc c'est NG.
De plus, bien que l'expression lambda de Python soit sortie,
Nom=argument lambda,argument, ...:formule
Vous pouvez écrire sous la forme de. Cependant, dans PEP8, il est recommandé d'écrire l'expression lambda en tant que fonction anonyme en Python, donc cette fois cela suit.
De plus, cet usage est utilisé comme argument de sorted (), mais cela peut être trié en fonction du résultat en appliquant une fonction arbitraire à chaque élément en utilisant une expression lambda dans sorted (). Ceci afin de tirer le meilleur parti de cette propriété.
Bien sûr, vous pouvez définir une fonction avec def et la spécifier comme clé, mais dans une situation comme celle-ci où vous ne l'utilisez qu'une seule fois, cette façon d'écrire est plus simple. Peut écrire.
Cette fois, le problème était nouveau, et probablement parce qu'il n'y avait pas beaucoup de répondants, nous aurions pu créer quelque chose qui n'était pas mal en termes de vitesse.
Jusqu'à ici pour cette fois. Je vous remercie pour votre travail acharné.
Recommended Posts