Mysli ako programátor: Riešenie problémov

Intro

Aby som si udržal svoje programátorské zručnosti, z času na čas riešim problémy na LeetCode. Je skvelý, pretože sa neustále vyvíja, má priateľské rozhranie, môžete si vybrať problémy na témy, ktoré vás zaujímajú, a je tu výborná komunita, od ktorej sa môžete veľa naučiť.

Vždy ma zaujímalo, čo sa deje v hlavách programátorov, keď riešia problémy. Ako to naozaj prebieha? Keďže som nenašiel žiadny materiál na túto tému, rozhodol som sa napísať o tom, ako sa to stalo mne.

Táto publikácia na komunitnom fóre LeetCode vyvolala pomerne veľký ohlas a získala stovky upvotov, preto sa o svoje skúsenosti delím aj tu na blogu.

Úloha

Tu je samotná úloha:

Dané pole celých čísel nums, zoraďte pole vzostupne na základe frekvencie hodnôt. Ak má viac hodnôt rovnakú frekvenciu, zoraďte ich v klesajúcom poradí. Vráťte zoradené pole.

Example 1:

Input: nums = [1,1,2,2,2,3]
Output: [3,1,1,2,2,2]
Vysvetlenie: “3” má frekvenciu 1, “1” má frekvenciu 2 a “2” má frekvenciu 3.

Štart

Skoré nedeľné ráno, hudba zo Spotify, horúca káva, obľúbená konzola, skvelá nálada… Úloha zo zoznamu úloh “na riešenie neskôr”.

Ideme na to! Spustenie Pythonu, zadanie počiatočného vstupu…

1
2
3
4
5

~ ❯ python3                                                                         
Python 3.9.1 (default, Feb 3 2021, 07:38:02)
[Clang 12.0.0 (clang-1200.0.32.29)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> nums = [1,1,2,2,2,6,6,4,4,5,5,3]

Myslenie

Ok, takže potrebujem spočítať frekvenciu každej z jedinečných hodnôt… Prvý nápad - použite Counter. Ten vracia objekt typu collection:

1
2
3
4
5

>>> d = Counter(nums)
>>> d
Counter({2: 3, 1: 2, 6: 2, 4: 2, 5: 2, 3: 1})
>>> type(d)
<class 'collections.Counter'>

Teraz potrebujem tieto hodnoty zoradiť podľa požiadaviek v popise. Objekt Counter nemá atribút sort a sorted zoradí len hodnoty, nie frekvencie. Pri googlení možností som našiel túto StackOverflow question s množstvom užitočných odpovedí. Čítanie… Skúsme jednoduchší objekt:

1

>>> r = Counter(nums).most_common()

Vráti zoznam tuplov, kde prvé číslo je hodnota a druhé jej frekvencia. Môžem to zoradiť v tom istom príkaze? Skok na oficiálnu dokumentáciu. Nie, v samotnom príkaze sa triediť nedá, navyše: “Prvky s rovnakým počtom sa zoradia v poradí, v akom sa vyskytli ako prvé”. Dobre, zoraďme to priamo, najprv podľa hodnôt v klesajúcom poradí, potom podľa početností v rastúcom.

1
2
3
4

>>> r.sort(key = lambda x: x[0], reverse=True)
>>> r.sort(key = lambda x: x[1])
>>> r
[(3, 1), (6, 2), (5, 2), (4, 2), (1, 2), (2, 3)]

Vyzerá to sľubne. Teraz by som chcel tieto kôpky rozšíriť do jedného zoznamu… Stále hľadám odpovede na tú istú otázku. Pamätám si, že pomocou tohto môžem rozbaliť tuple a získať z neho každé číslo:

1
2
3
4
5

>>> a, b = (3, 2)
>>> a
3
>>> b
2

takže potom môžem každú hodnotu opakovať podľa čísla jej frekvencie takto:

1
2

>>> [3]*2
[3, 3]

Aha. Teraz potrebujem prázdny zoznam, aby som mohol všetky tieto kôpky spojiť do jedného zoznamu:

1
2
3
4
5
6
7

t = []
for i in r:
    a, b = i
    t.extend([a] * b)

>>> t
[3, 6, 6, 5, 5, 4, 4, 1, 1, 2, 2, 2]

Woo-hoo! To je to, čo potrebujem. Takže kompletné riešenie teraz vyzerá takto:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def frequencySort(self, nums: List[int]) -> List[int]:
        
        r = Counter(nums).most_common()
        r.sort(key = lambda x: x[0], reverse=True)
        r.sort(key = lambda x: x[1])
        
        t = []
        for i in r:
            a, b = i
            t.extend([a]*b)
            
        return t

Výsledok: Čas vykonania: 52 ms, čo je rýchlejšie ako 63,30 % iných riešení Pythonu 3 pre triedenie polí vo vzostupnej frekvencii.

Využitie pamäte: 14,2 MB, čo je menej ako 58,20 % iných riešení Pythonu 3 pre vzostupné triedenie polí.

Nie je to najlepšie, ale úloha je vyriešená.

Optimalizacia

Teraz je čas na ďalšiu zábavu - môžem to spraviť jednoriadkovo alebo optimalizovať riešenie nejakým iným spôsobom?

Pri pohľade na triediace riadky… Môžem to zoradiť na jeden záťah? Áno! Takže najprv triedime podľa hodnôt v opačnom poradí (-x[0]) a potom podľa ich frekvencií (x[1]) v priamom poradí.

1

>>> r.sort(key = lambda x: (x[1], -x[0]))

V podstate ide o rovnakú operáciu ako vyššie, ale teraz je zakódovaná v jednom riadku. Milujem Python :) Rovnaká logika platí aj pre časť rozšírenia tuple a umožňuje ušetriť ďalší riadok:

1
2
3

t = []
for i in r:
  t += ([i[0]] * i[1])

A potom som si pomyslel - ak môžem triediť podľa hodnoty a jej frekvencie, načo potrebujem medzisúpis? Môžem zoradiť pôvodný zoznam rovnakým spôsobom?! Pozrime sa na to…

1
2
3
4
5
6
7
8

>>> nums
[1, 1, 2, 2, 2, 6, 6, 4, 4, 5, 5, 3]
>>> r = Counter(nums)
>>> r
Counter({2: 3, 1: 2, 6: 2, 4: 2, 5: 2, 3: 1})
>>> nums.sort(key=lambda x: (r[x], -x))
>>> nums
[3, 6, 6, 5, 5, 4, 4, 1, 1, 2, 2, 2]

Voila! Je to veľmi dobrý pocit. Ale x.sort to robí na mieste a ja potrebujem vrátiť objekt… Takže to musím zmeniť na sorted:

1
2
3

>>> result = sorted(nums, key=lambda x: (r[x], -x))
>>> result
[3, 6, 6, 5, 5, 4, 4, 1, 1, 2, 2, 2]

Perfektné. Takže konečný variant by bol:

1
2
3
4

class Solution:
    def frequencySort(self, nums: List[int]) -> List[int]:
        r = Counter(nums)
        return sorted(nums, key=lambda x: (r[x], -x))

A je to ešte rýchlejšie!

Čas spustenia: 44 ms, čo je rýchlejšie ako 95,07 % iných riešení Pythonu 3 pre vzostupné triedenie polí.

Využitie pamäte: 14,3 MB, čo je menej ako 58,20 % iných riešení Pythonu 3 pre vzostupné triedenie polí.

Záver

Riešenie programátorských úloh si vyžaduje kombináciu vedomostí, skúseností a tvorivých schopností riešiť problémy. Pochopením myšlienkového procesu a techník, ktoré používajú skúsení programátori, môžete zlepšiť svoju schopnosť rozložiť zložitý kód a identifikovať a prekonať prekážky.

Vďaka praxi a vytrvalosti sa každý môže stať zdatným programátorom a vyniknúť vo svojom odbore. Nezabudnite zostať vždy zvedaví a pokračovať v učení, pretože technológie a programovacie jazyky sa neustále vyvíjajú.

Ale čo je najdôležitejšie, bavte sa!

😎