collections.CounterEn Python, il n'y a pas de MultiSet (un ensemble qui autorise le même élément) par défaut, mais vous pouvez utiliser collections.Counter à la place. Ce n'est pas seulement un MultiSet, mais il a une méthode pratique pour compter, il peut donc être utilisé dans diverses situations.
Référence: https://docs.python.org/ja/3/library/collections.html#collections.Counter
Prenons LeetCode comme exemple.
Trouvez la valeur la plus fréquente de «nums».
Vous pouvez utiliser most_common comme ci-dessous.
class Solution:
def majorityElement(self, nums: List[int]) -> int:
return collections.Counter(nums).most_common(1)[0][0]
Demande si les deux chaînes «s» et «t» sont des anagrammes.
Être un anagramme signifie qu'il apparaît le même nombre de fois. Par conséquent, comparez simplement collections.Counter avec ==.
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
return collections.Counter(s) == collections.Counter(t)
Trouvez le nombre de correspondances dans la rubrique «position et nombre» et le nombre de correspondances dans le jeu de devinettes.
"Position et numéro" peuvent être extraits par zip et comparés. Pour le nombre qui correspond uniquement au nombre, recherchez le jeu de produits avec "&" et comptez le nombre ("valeurs").
class Solution:
def getHint(self, secret: str, guess: str) -> str:
co = collections.Counter
a = sum(i == j for i, j in zip(secret, guess))
b = sum((co(secret) & co(guess)).values()) - a
return f"{a}A{b}B"
Trouvez les K principaux éléments haute fréquence.
Dans l'état actuel des choses, utilisez most_common.
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
return [i for i, _ in collections.Counter(nums).most_common(k)]
350. Intersection of Two Arrays II
Retrouvez la partie commune des deux listes dans la liste.
Les éléments peuvent être obtenus avec des «éléments».
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
c = collections.Counter(nums1) & collections.Counter(nums2)
return list(c.elements())
Demande si chaque personnage de ransomNote est inclus dans le magazine. Chaque personnage du magazine ne peut être utilisé qu'une seule fois.
Vous pouvez calculer la différence définie avec " - ".
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
return not (collections.Counter(ransomNote) - collections.Counter(magazine))
387. First Unique Character in a String
Trouvez l'index du premier caractère unique.
Il ne renvoie que celui avec 1 apparence.
class Solution:
def firstUniqChar(self, s: str) -> int:
for k, v in collections.Counter(s).items():
if v == 1:
return s.index(k)
return -1
Au fait, "136. Single Number" pour trouver le nombre dont un seul existe doit être accumulé par XOR.
class Solution:
def singleNumber(self, nums: List[int]) -> int:
res = 0
for i in nums:
res ^= i
return res
Ajoutez un caractère à la chaîne s et laissez la chaîne mélangée être t. Demandez le personnage ajouté.
Il peut être calculé comme un ensemble de différences.
class Solution:
def findTheDifference(self, s: str, t: str) -> str:
return list((collections.Counter(t) - collections.Counter(s)).keys())[0]
Trouvez le nombre de paires d'éléments pour lesquelles la différence est k.
collections.Counter peut utiliser ʻitems ()` comme un dictionnaire.
Les éléments sont la valeur et le nombre.
class Solution:
def findPairs(self, nums: List[int], k: int) -> int:
c = collections.Counter(nums)
return sum(k > 0 and n + k in c or k == 0 and f > 1 for n, f in c.items())
Découvrez si le point final du robot après le mouvement est l'origine.
collections.Counter peut utiliser get (key) comme un dictionnaire.
Il revient à l'origine lorsque le nombre de mouvements à gauche et le nombre de mouvements à droite sont égaux et que le nombre de mouvements vers le bas et le nombre de mouvements vers le haut sont égaux.
Vous pouvez utiliser str.count, mais collections.Counter est mieux.
class Solution:
def judgeCircle(self, moves: str) -> bool:
c = collections.Counter(moves)
return c.get("L", 0) == c.get("R", 0) and c.get("D", 0) == c.get("U", 0)
Trouvez les mots les plus fréquents qui ne sont pas inclus dans banni (majuscules et minuscules).
Vous pouvez utiliser «most_common» car c'est le mot le plus fréquent.
class Solution:
def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
c = collections.Counter(re.findall(r"\w+", paragraph.lower()))
return next(s for s, _ in c.most_common() if s not in banned)
893. Groups of Special-Equivalent Strings
Si des échanges pairs ou impairs sont échangés et correspondent, ils sont considérés comme faisant partie du même groupe. Trouvez le nombre de groupes.
Utilisez collections.Counter en changeant les cotes en majuscules.
Vous pouvez également trouver le groupe en utilisant set (tuple (sorted (c.items ()))).
class Solution:
def numSpecialEquivGroups(self, A: List[str]) -> int:
cc = [collections.Counter(i[::2].upper() + i[1::2]) for i in A]
return len(set(tuple(sorted(c.items())) for c in cc))
Je n'utilise pas more_itertools pour faire correspondre LeetCode, mais cela simplifie les choses.
Référence: Exemple de réponse LeetCode utilisant collections.Counter
Recommended Posts