# Python-LeetCode 581 第六招 Counter
「小皮球，香蕉油，滿地開花二十一，二五六，二五七，二八二九三十一」，數數。
本單元中我們說明使用計數器(counter)來記錄數量的基本操作以及LeetCode中常見的題型。
## 基本操作
通常有兩種方式來計算數量：表格(list)與字典(dict)。當計算對象是小範圍的整數時，可以用list來做；如果對象是範圍很廣(很稀疏)的範圍，或者是字串之類不容易轉成index來代表時，用dict是比較好的方式。Python的dict好用又快，所以往往可以用list來做的也用dict來做。
### 表格計數
用list或陣列來做表格計數是一種很基本的程式操作，在學習基本程式時經常都會做過一些練習，所以這一類很多題目的難度並不高。
最直接的使用是計算對象是小範圍的整數，尤其像是$[0,100]$或$[1,1000]$這種區間。初始時，我們先開一個list，初值給0，碰到某對象$p$，就將對應位置+1，如果要扣除就-1。例如
```python=
cnt = [0]*101
for p in nums:
cnt[p] += 1
# do something
cnt[p] -= 1
```
Python的list初始常用上面這樣的方式，乘法是表示重複，list的大小要小心，因為是從0開始編號，如果要做到100，大小需要到101。二維陣列的初始要小心，下面是常用的方式
```python=
cnt = [[0]*101 for i in range(101)]
for p,q in nums:
cnt[p][q] += 1
# do something
```
不可以使用
```python
cnt = [[0]*101]*101
```
的方式，因為把一個list $*101$是重複該物件101次，裡面的每一個list都是同一個，而非獨立不同的101個。
如果對象不是從0開始，那麼可以將它做一個平移轉換，例如常用的字元。英文字母或數字字元的ASCII都是連續的，數字字元是0x30 ~ 0x39、大寫字母是0x41 ~ 0x5A、小寫字母是0x61 ~ 0x7A。如果只有小寫字母(LeetCode這樣的題很多)，我們可以用長度26的list來計。用ord()可以轉換為ASCII，例如下面的手法將'a' ~ 'z'轉換到0 ~ 25。
```python=
cnt = [0]*26
for ch in s: # char in string
cnt[ord(ch)-0x61] += 1
# do something
```
### 字典計數
Python的字典是hash table，使用方便，存取也快。基本的操作請讀者自行參考[官方dict說明文件](https://docs.python.org/zh-tw/3/library/stdtypes.html?highlight=dict#dict)，網路上也找得到很多基本教學。我們這裡就不再重複。
文件中的操作與運算很多，以下我們列舉一些解題比較常用到的。
#### 基本dict以及常用運算與函數
* 初始化(有多種方式)
* 檢查key在不在。key in d, key not in d
* 單一key加入或改變與存取：d[key] = val、d[key]+=1、d[key] -= x、p = d[key]
* 刪除key值：del d[key]
* 取出字典內容(例如轉到一個list)：list(d.items())。或取出dict所有的對應值(例如取最大)：max(d.values())
* 兩個字典合併
#### defaultdict與Counter
使用dict有件討厭的事，就是若key值不存在時，取用會噴發KeyError的執行錯誤。因此有個衍生的字典類型稱為defaultdict [(說明文件)](https://docs.python.org/zh-tw/3/library/collections.html#collections.defaultdict)，它的差別是你可指定在key值不存在時呼叫的函數來產生預設值。常用的是
defaultdict(int)
defaultdict(list)
defaultdict(set)
請參考上述說明文件中的範例就很容易了解基本的使用方式。
Python有一個常用的dict稱為Counter [(說明文件)](https://docs.python.org/zh-tw/3/library/collections.html#collections.Counter)，基本上很類似於defaultdict(int)，就是對應欄位是數字的字典，但它有一些擴充的函數很好用，請參考上述說明文件。
## 範例
### 基本範例
#### 統計數字出現次數
[(題目連結) 347. Top K Frequent Elements (Medium)](https://leetcode.com/problems/top-k-frequent-elements/)
題目很簡單，給一個數列以及$k$，找出出現次數最多的$k$個數字。
第一個重點是統計出每個數字出現的次數，我們用字典來做，第二個重點是找出出現次數的前$k$大。我們以下提供三個寫法。用哪一個就看讀者對Python字典的熟悉程度。
1. 使用Counter().most_common()
2. 使用Counter()與sort
3. 只使用基本的字典
以下是範例程式。裡面用到的Counter().most_common()、dict.items()與sort()的使用方法皆可於Python的線上說明文件中查到。
```python=
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
'''
method 1, oneliner
#return [p[0] for p in Counter(nums).most_common(k)]
# mthod 2: using Counter() + sort
cnt = Counter(nums)
s = sorted([(cnt[p],p) for p in cnt],reverse=True)
return [p[1] for p in s[:k]]
'''
# method 3: using plain dict
cnt = {}
for p in nums:
if p in cnt: cnt[p] += 1
else: cnt[p] = 1
# dict.items = [(key,value)]
s = sorted(cnt.items(), key=lambda x:x[1],reverse=True)
return [p[0] for p in s[:k]]
```
三種方法的速度差不多。
#### 字串的範例
下面這一題與前一題很類似，但統計的對象是字串。
[(題目連結) 692. Top K Frequent Words (Medium)](https://leetcode.com/problems/top-k-frequent-words/)
題目說有一個字串陣列，要找出出現最多的前$k$個字串，並依照出現次數有多到少排列，相同次數者依照字典順序由小到大。
這題可以用上題類似的方法建立字典來統計次數，然後做排序找出前$k$個需要的字串。但這題的題目尾端有希望能在$O(n\log k)$的時間完成的需求。所以我們不使用排序(時間複雜度$O(n\log n)$而用heap來做。此外這題有個稍微麻煩的是排列順序，我們必須先用次數當主要的key，當次數一樣時，用字串的字典順序。Python的heap是min-heap，我們在heap中要的是讓字典序比較大的浮出以便丟棄，所以要用點技巧讓字典序反序。
在下面的範例程式中，我們是對每一個字串$w$用一個list作為heap中的比較key值，第一個欄位給的是出現次數，接下來的欄位用的是$128-ord(c)$，其中$c$是字串$w$的每一個字元，最後再接一個常數128。因為字元的ord(ASCII code)取負號就類似用補數，會將大小反序，另外尾端用128的是讓比較長的字串先浮出來，因為字元的ASCII比128要小。
```python=
class Solution:
def topKFrequent(self, words: List[str], k: int) -> List[str]:
c = Counter(words)
pq = []
for w in c:
heappush(pq,[c[w]]+[128-ord(c) for c in w]+[128])
if len(pq)>k: heappop(pq)
ans = []
while pq:
w = heappop(pq)
ans.append("".join([chr(128-i) for i in w[1:-1]]))
return ans[::-1]
```
第3行我們先把輸入的字串陣列丟進Counter()去統計各自串的出現次數。然後把Counter中的字串一一丟進pq中，用來比較的key是前面說的list。當heap內字串數量$>k$時會把key值最小的丟棄。
第8行開始準備要輸出的答案。我們把pq內的$k$個字串還原並且反轉順序就是要求的答案。將字串由我們定義的list $w$還原，我們用字串函數
$string.join(list)$
此函數將list中的每一個字串(或字元)以string當作連接字元加以連接成為一個字串。這裡我們的list用
[chr(128-i) for i in w[1:-1]]
因為最前面與最後面的不是字串內容，而字串內容是ASCII為128-i的字元。
時間複雜度$O(n\log k)$，因為$n$個字串進出heap各一次，此處字串長度看成constant。如果時間複雜度是要求$O(n\log n)$的話，可以用排序，會簡單一些。
#### 二維的例子以及Equivalence class
這題是Easy的題目，但算是典型而有趣的Counting問題，我們把它選進來。
[(題目連結)1128. Number of Equivalent Domino Pairs (Easy)](https://leetcode.com/problems/number-of-equivalent-domino-pairs/)
題目是說有一些骨牌(上下各有一個數字的長方形牌)，請問有**幾對相同的骨牌**？每張骨牌以一對數字$[a,b]$表示，但骨牌可以上下反轉視為相同，也就是$[a,b]$與$[b,a]$是相同骨牌。
這可以看成一個簡單的分類的問題，我們知道如果同一類的東西有$k$個，則就是有$C(k,2)=k\times(k-1)/2$對相同的物品。在處理分類時，最簡單的方式就是定義每一類的**標準型**，將每一個物品轉換成標準型之後就容易歸類了。
本題每一個骨牌有兩個數字，可以交換。所以我們可以定義標準型是**先小後大**。
以下的範例程式我們還是用Counter()，這題也可用二維陣列來記錄，因為數字的範圍只有$[1,9]$。在歸類後每一類的數量可以用dict.values()的函數取出所有的對應值。
```python=
class Solution:
def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:
cnt = Counter([(min(a,b),max(a,b)) for a,b in dominoes])
total = 0
for v in cnt.values():
total += v*(v-1)//2
return total
```
以下是二維陣列來計數的範例程式。請有興趣的讀者自行參考，就不多贅述了。
```python=
class Solution:
def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:
# using table
cnt = [[0]*10 for i in range(10)]
for a,b in dominoes:
cnt[a][b] += 1
total = 0
for i in range(1,10):
total += cnt[i][i]*(cnt[i][i]-1)//2
for j in range(i+1,10):
v = cnt[i][j] + cnt[j][i]
total += v*(v-1)//2
return total
```
### 從值域下手
以下這題動一點腦筋之後應該算簡單。
[(題目連結) 299. Bulls and Cows (Medium)](https://leetcode.com/problems/bulls-and-cows/)
題目是常玩的幾A幾B的猜數字遊戲，有兩個長度相同的數字，一個數字是$secret$，另外一個數字$guess$。如果所猜數字與謎底有一個位數位置與數字皆相同，則有一個A；如果數字相同但位置不同，則有一個B，要計算此次猜的數字結果是幾A幾B。計算B的時候不重複計算，例如在給的範例
Input: secret = "1123", guess = "0111"
Output: "1A1B"
輸入的數字可能達到1000位，以字串的方式給予。
這題目要算A是很容易的，但要算B的時候要動一點腦筋，因為數字很長，如果一一比對的話，會達到$1000\times 1000$個字元比較。
因為每一位數字只會是0 ~ 9，值域很小。
值域很小時可以在值域上動腦筋。
我們計算secret中0出現的次數$count1[0]$。
計算guess中0出現的次數$count2[0]$。
那麼，$\min(count1[0],count2[0])$就是有幾個0猜對了，對0 ~ 9每個數字當作相同的處理就可以了。當然這包含了位置也對的A，所以最後要再把算在A中的扣回來就可以了。
以下是範例程式。第3行計算有幾個A，用zip枚舉兩序列的相同位置的對應字元，把邏輯式放在sum()裡面，True 會轉成1而False 就是0。接著計算每個數字字元出現的次數，這裡我們用表格(list)當作計數器，數字字元s取$ord(s)-0x30$就會轉換到0 ~ 9。程式很簡短，時間複雜度$O(n)$。
```python=
class Solution:
def getHint(self, secret: str, guess: str) -> str:
x = sum(s==t for s,t in zip(secret,guess))
count1 = [0]*10
for s in secret:
count1[ord(s)-0x30] += 1
count2 = [0]*10
for s in guess:
count2[ord(s)-0x30] += 1
y = sum(min(s,t) for s,t in zip(count1,count2)) - x
return str(x)+'A'+str(y)+'B'
```
#### Counting char
在字串中計算字元出現次數是常見的題型。以下是一例。
[(題目連結)1347. Minimum Number of Steps to Make Two Strings Anagram (Medium)](https://leetcode.com/problems/minimum-number-of-steps-to-make-two-strings-anagram/)
題目是輸入兩個長度相同的字串$s$與$t$，每一步你可以任選$t$的一個字元將其更換為任何其它字元，請問最少要幾步可以將$t$變成一個$s$的anagram，所謂字串的anagram是指所含字母相同但排列可能不同的字串。
這一題跟前面一題很類似，只是對象從數字換成了字元。我們不必去兩個字串中相互比對，而是應該統計每個字串中字元出現的次數。
我們先計算每一個字母出現次數的差值。
接下來有兩個方法都可以：一是去累加「$s$中出現次數比$t$中出現數多」的字母頻率的差值，像下面程式中第8行。因為兩字串長度相同，$s$中較多的差值總和一定剛好等於較少的差值總和，每一步可以將$t$中較多的一個字母換成$t$中一個較少的字母。所以最少的步驟只要計算較多(或較少)的差值總和就是答案。
另外一個方式是算每個字母差值的絕對值總和，最後除以2，像第6 ~ 7行那樣，道理與前面是一樣的。
以下是範例程式，此處我們用list來做計數器，因為字元只會是小寫字母，所以用長度26就夠了，對於字元$c$，用$ord(c)-0x61$就可以將結果對應到0 ~ 25的位置。
時間複雜度是$O(n)$。
```python=
class Solution:
def minSteps(self, s: str, t: str) -> int:
cnt1,cnt2=[0]*26,[0]*26
for c in s: cnt1[ord(c)-0x61] += 1
for c in t: cnt2[ord(c)-0x61] += 1
#total = sum(abs(p-q) for p,q in zip(cnt1,cnt2))
#return total//2
return sum(p-q for p,q in zip(cnt1,cnt2) if p>q)
```
接下來再看一個字元計算的題目。
[(題目連結) 1400. Construct K Palindrome Strings (Medium)](https://leetcode.com/problems/construct-k-palindrome-strings/)
本題中，輸入一個字串與一個整數$k$，請問你可否用這些字母做出$k$個迴文(palindrome)。所謂palindrome是一個左右對稱的字串，也就是由前往後讀與由後往前讀是一樣的，例如aba與abba。
迴文在LeetCode的字串題中出現非常多，但這裡只要知道**一個Palindrome中最多只有一個出現奇數次的字母**就可以了，這其實是**充分且必要條件**，一群字母，只要奇數次數的字母只有一個或沒有，必然可重排成為一個palindrome。
因此本題只要計算字母出現的次數就可以了。在$k$個回文的情形下，我們最多只能有$k$個字母出現奇數次，如果超過$k$個字母出現奇數次，就一定無法建構，如果少於$k$個是可以的，但是有個小陷阱，所給字串的長度必須至少為$k$。以下是範例程式，時間複雜度$O(n)$。
```python=
class Solution:
# at most k odd, len>=k
def canConstruct(self, s: str, k: int) -> bool:
cnt = Counter(s)
odd = 0
for c in cnt:
if cnt[c]&1: odd += 1
return odd<=k and len(s)>=k
```
### 邊走邊算 Sweeping and Counting
接下來看需要在掃描過程中邊走邊紀錄個數的題目。
[(題目連結) 1419. Minimum Number of Frogs Croaking (Medium)](https://leetcode.com/problems/minimum-number-of-frogs-croaking/)
本題定義，一隻青蛙叫是「依序出現c,r,o,a,k五個字母」，多隻青蛙的叫聲可能相互混雜，但每隻青蛙的五個字母仍然保持其順序。一隻青蛙在叫完一次croak之後可能再開始叫一次croak。輸入一個字串，請問最少有幾隻青蛙，或者不是一個合法的青蛙叫聲字串。
因為有不合法的字串而且一隻青蛙叫完一輪可能再叫一輪，所以不能只是算一下長度，或者只算一下每種字母出現的次數。對於一個合於規定的字串，其切割的方法並不唯一，簡單的例子ccrrooaakk就有$2^4=16$種切割的方式，但這不是本題的重點，我們只需要判斷是否合法以及在合法的情形下最少有幾隻青蛙。
這題有Greedy的味道，但其實是很直覺的：「當一隻青蛙結束一輪croak之後，下一個出現的c就計算為已經結束叫聲的青蛙的再一次叫聲開始」。所以最小值的問題是看這些混合字串的「厚度」。
假設這個字串是合法的，我們只抓第一個c與最後一個字母k。從前往後掃的過程中，每當一個c進入時，就多了一隻青蛙，每當一個k出現時，就減少一隻青蛙。在任何一個時刻的青蛙數的最大值，就是最少的青蛙數。
至於在判斷不合法的字串方面：「如果是一個合法的字串，每一個r會屬於它前方的某一個c，而每一個c只能有一個r跟他同一組。同樣的道理對接續的o,a,k都是一樣。」以下說明的本題演算法。
1. 我們對於c,r,o,a,k五個字母各用一個計數器紀錄目前尚未找到下一個字母的個數。定義c,r,o,a,k五個字母的順序分別是0 ~ 4。用變數num紀錄同時在線的青蛙數量，ans則是目前為止同時在線數量的最大值。
2. 由前往後掃描字串，如果碰到c，則cnt[c]+1；如果碰到其它字母，檢查順序在它前面那個字母的計數器，如果是0，則判斷為不合法，因為沒有前一個可以跟；如果不是0，則將前一個字母的計數器減一，自己的計數器加一。
3. 掃描過程中，碰到c則num+1，並檢查是否要更新ans；如果碰到k則num-1。
4. 到字串結尾時，除了k以外的所有的計數器必須都是0，否則不合法。
以下是範例程式，一開始我們用字典定義了五個字母的順序，然後開五個計數器，這是方便後面判斷字母順序之用。時間複雜度$O(n)$。
```python=
class Solution:
# status of a frog: 0~3 -> croa
def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
d = {'c':0, 'r':1,'o':2,'a':3,'k':4}
cnt = [0]*5
ans = num = 0
for ch in croakOfFrogs:
if ch=='c': # new frog
cnt[0] += 1
num += 1
if num>ans: ans=num
else:
t = d[ch]
if cnt[t-1]==0: return -1
cnt[t-1] -= 1
cnt[t] += 1
if t==4: num -= 1
for i in range(4):
if cnt[i]: return -1
return ans
```
### Sliding window and Couting
[(題目連結) 992. Subarrays with K Different Integers (hard)](https://leetcode.com/problems/subarrays-with-k-different-integers/)
這個題目是說有一整數序列以及一個整數$k$，要計算有多少個子陣列包含恰好$k$個不同的數字。
這看起來是個sliding window的題目，搭配計算視窗內有多少個不同數字的技巧。當右端往右滑動時，視窗內的數字種類可能增加，所以我們必須滑動左端來減少視窗內數字種類。與基本滑動視窗不同的是，同一個右端可能可以對應很多個左端，例如$k=3$時，
$[0,1,2,1,1,2,1,2,3]$
對於右端在最後一個位置時，index 1 ~ 6都是合法的左端。
對一個固定右端，視窗的範圍越大，它所包含的不同數字種類顯然是**單調非遞減**的，也就是合法(恰含$k$個不同數字)的左端會是**一個連續區間**。
因此我們可以維護所有合法左端的區間上下界，當右端移動時，只要依照上下界的定義滑動左端上下界就可以了。此外，對於一個固定右端，它的合法視窗數就是左端上下界的差值。
以下的範例程式中，我們用list當計數器，並且要維護好目前視窗內不同數字的個數，因為有上下界，所以維護的指令都有兩套。寫法上可以先找出第一個合法視窗，再開始一步一步推動右端。這裡的寫法是從一開始就逐步滑動右端，用一個if(第31行)來檢查是否已經到達第一個合法視窗。
當右端滑動時，我們對左端的上下界基本上是做非常類似的操作。
1. 先將新進入的右端數字計數器加一
2. 如果是新數字，則個數加一
3. 當數字個數太多時，持續移動左端並記錄檢查計數器。對於下界來說，視窗內的個數必須$=k$；對上界來說，視窗內的個數必須$<k$(端點不含)。
時間複雜度都是$O(n)$。計數器用字典或Counter來做也是很合適的。因為這題數字的範圍是$[1,n]$，所以用list來做也很適合。
```python=
class Solution:
# sliding windows
# for each right, maintain lower and upper obound (smallest and largest)
# left boundary, such that the windows contains k different int
def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:
n = len(nums)
low,up = 0,0
lowcnt,upcnt = [0]*(n+1), [0]*(n+1)
low_d = up_d = 0 # num of different
ans = 0
for right,p in enumerate(nums):
# update low
lowcnt[p] += 1
if lowcnt[p] == 1: low_d += 1 # new
while low_d > k:
q = nums[low]
lowcnt[q] -= 1
if lowcnt[q] == 0:
low_d -= 1
low += 1
# update up
upcnt[p] += 1
if upcnt[p] == 1: up_d += 1 # new
while up_d >= k:
q = nums[up]
upcnt[q] -= 1
if upcnt[q] == 0:
up_d -= 1
up += 1
#
if low_d==k: ans += up-low
# end for right
return ans
```
### Couting on a tree
[(題目連結)1519. Number of Nodes in the Sub-Tree With the Same Label (Medium)](https://leetcode.com/problems/number-of-nodes-in-the-sub-tree-with-the-same-label/)
輸入一個rooted tree，每一個節點有一個英文字母的label，要計算以每一點為root的subtree中有多少點的label與該點相同。
我們做一個DFS的走訪來歷遍所有的點，用一個計數器邊走邊累加紀錄每一個字元出現的總次數。根據DSF的特性，進入一點$v$後，會歷遍它的所有後代節點，然後離開$v$，因此我們所求的答案就是**進入與離開$v$點時，$v$的字元標籤計數器的差值**。
根據儲存的資料結構的不同，樹狀圖的DFS寫法有幾種，本題樹狀圖輸入是以無根樹的方式輸入邊集合，然後指定了0是根。所以我們先將邊的集合轉換成adjacent list，也就是每一點用一個list紀錄其鄰居的編號。以下是範例程式。
第3 ~ 6行做輸入轉換，這是常用寫法，第7行準備一個放答案的ans，第8行準備一個計數器，這裡用Counter來做，這題用長度26的list也可以，因為label都是小寫字母。
接著編寫一個dfs($v$,$p$)的函數，留意這裡樹狀圖的DFS寫法，我們傳入拜訪的點$v$以及它的parent $p$，在拜訪時，對該點除了parent的所有鄰居遞迴進行DFS，如第11 ~ 13行。因為樹狀圖沒有環路，所以每個點只要不呼叫它的parent，就不會重複走訪，因此沒有必要紀錄是否已經走過。
進入每一點時紀錄該點標籤字元計數器的值(第10行)，離開時將該計數器的差值存入答案(第15行)，其中第14行做加一是計入$v$本身。主程式呼叫時以根結點0進入，此時的根給-1代表沒有parent，所以用任何只要不是根的鄰居的假編號都可以。
時間複雜度$O(n)$，因為樹狀圖的邊數比點數少一。
```python=
class Solution:
def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:
adj = [[] for i in range(n)]
for u,v in edges:
adj[u].append(v)
adj[v].append(u)
ans = [0]*n
cnt= Counter()
def dfs(v,p): # visit v, parent p
out = cnt[labels[v]]
for u in adj[v]:
if u != p:
dfs(u,v)
cnt[labels[v]] += 1
ans[v] = cnt[labels[v]] - out
dfs(0,-1)
return ans
```
## 結語
計數器不是一個難的東西，LeetCode中標籤在*counting*的題目大多也相對較簡單，很多是屬於Easy與Medium的困難度。
本單元介紹了一些使用字典或list來做計數器的題目與常用技巧，包含一維與二維的數字、字元與字串。當然很多題目會用到多項技巧的合併，本單元中我們也介紹了計數器結合Sweeping、Sliding window、或Tree DFS的題目。Sliding window在前面的單元介紹過了([Python-LeetCode 第二招 Sliding Window](/Yt6Zukv-SSSYFOKonWq8Bw))，有關Tree與DFS後面還會有單元做詳細的介紹。
Sign in with Wallet
Connect another wallet