[PYTHON] Verwenden Sie Sammlungen

Verwenden Sie collection.Counter

In Python gibt es standardmäßig kein MultiSet (eine Menge, die dieselben Elemente zulässt), aber Sie können stattdessen collection.Counter verwenden. Es ist nicht nur ein MultiSet, sondern verfügt über eine bequeme Zählmethode, sodass es in verschiedenen Situationen verwendet werden kann.

Referenz: https://docs.python.org/ja/3/library/collections.html#collections.Counter

Nehmen wir als Beispiel LeetCode.

169. Majority Element

Finden Sie den häufigsten Wert von nums.

Sie können most_common wie folgt verwenden.

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        return collections.Counter(nums).most_common(1)[0][0]

242. Valid Anagram

Fragt, ob die beiden Zeichenfolgen s und t Anagramme sind.

Ein Anagramm zu sein bedeutet, dass es genauso oft erscheint. Vergleichen Sie daher einfach collection.Counter mit ==.

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return collections.Counter(s) == collections.Counter(t)

299. Bulls and Cows

Finden Sie die Anzahl der Übereinstimmungen in der "Position und Anzahl" und die Anzahl der Übereinstimmungen im Zahlenschätzspiel.

"Position und Nummer" kann per Zip extrahiert und verglichen werden. Suchen Sie für die Nummer, die nur mit der Nummer übereinstimmt, den Produktsatz mit "&" und zählen Sie die Nummer ("Werte").

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"

347. Top K Frequent Elements

Finden Sie die Top K Hochfrequenzelemente.

Verwenden Sie "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

Suchen Sie den gemeinsamen Teil der beiden Listen in der Liste.

Elemente können mit "Elementen" erhalten werden.

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        c = collections.Counter(nums1) & collections.Counter(nums2)
        return list(c.elements())

383. Ransom Note

Fragt, ob jedes Zeichen in ransomNote im Magazin enthalten ist. Jedes Zeichen im Magazin kann nur einmal verwendet werden.

Sie können die eingestellte Differenz mit " - "berechnen.

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

Suchen Sie den Index des ersten eindeutigen Zeichens.

Es wird nur der mit 1 Erscheinungsbild zurückgegeben.

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

Übrigens sollte "136. Single Number", um die Nummer zu finden, die nur eine existiert, von XOR akkumuliert werden.

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        res = 0
        for i in nums:
            res ^= i
        return res

389. Find the Difference

Fügen Sie der Zeichenfolge s ein Zeichen hinzu und lassen Sie die gemischte Zeichenfolge t sein. Fragen Sie nach dem hinzugefügten Charakter.

Sie kann als Differenzsatz berechnet werden.

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        return list((collections.Counter(t) - collections.Counter(s)).keys())[0]

532. K-diff Pairs in an Array

Ermitteln Sie die Anzahl der Elementpaare, für die die Differenz k beträgt.

collection.Counter kann items () s wie ein Wörterbuch verwenden. Die Elemente sind der Wert und die Zahl.

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())

657. Robot Return to Origin

Finden Sie heraus, ob der Endpunkt des Roboters nach der Bewegung der Ursprung ist.

collection.Counter kann get (key) wie ein Wörterbuch verwenden. Es kehrt zum Ursprung zurück, wenn die Anzahl der linken Bewegungen und die Anzahl der rechten Bewegungen gleich sind und die Anzahl der Abwärtsbewegungen und die Anzahl der Aufwärtsbewegungen gleich sind. Sie können str.count verwenden, aber collection.Counter ist besser.

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)

819. Most Common Word

Finden Sie die häufigsten Wörter, die nicht in verboten enthalten sind (Groß- und Kleinschreibung).

Sie können most_common verwenden, da dies das häufigste Wort ist.

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

Wenn gerade oder ungerade Austausche ausgetauscht werden und übereinstimmen, werden sie als in derselben Gruppe befindlich betrachtet. Finden Sie die Anzahl der Gruppen.

Verwenden Sie collection.Counter, indem Sie die Gewinnchancen in Großbuchstaben ändern. Sie können die Gruppe auch mithilfe von set (tuple (sorted (c.items ()))) finden.

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))

Beiseite

Ich verwende more_itertools nicht, um mit dem LeetCode übereinzustimmen, aber es macht es einfacher.

Referenz: Beispiel für eine LeetCode-Antwort mit collection.Counter