Try   HackMD

Ch24 將陣列作為表格用途

搭配 Leetcode 解題系統
回目錄：國立科學園區實驗中學C++程式語言自學講義

將陣列作為表格用途

後面的幾個章節要學的是「表格」類型的資料結構
包括 unordered_map / unordered_set （沒有順序的表格）
和 map / set (有順序的表格)

在正式開始介紹這四樣資料結構前
我們先來熟悉一些概念類似，但不需要用到這些資料結構的題目

適用題型：計數問題

如果要統計每種數字共出現幾次
我們可以使用一個陣列來記錄
陣列的第k格紀錄的就是「數字k共出現了幾次」

有明確數值範圍

【例題】

題目給一個名為 nums 的一維陣列，裡面共有 n 個數字
剛好在 1 到 n 這 n 個數字裡面
有一個數字重複了，有一個數字缺失了，其他都正好出現一次
請找出重複的數字和缺失的數字並回傳
例如 [1, 2, 2, 4] 就是 2 重複了，3 不見了
所以要回傳 [2, 3]

這是 Leetcode 上的題目，連結是 Leetcode 645

我們可以用一個長度為 n+1 的 vector 來當作表格做計數，命名為 count
之所以會需要 n+1 格是因為這樣才有第 n 格可以使用 (而第0格用不到)
每一格都要先歸零




int n = nums.size();
vector<int> count(n+1, 0);
//               n+1格 每格為0

然後就拜訪 nums 裡的每個值
把 count 裡對應的格子 +1




for(int i=0;i<nums.size();i++){
    count[nums[i]]++;
}

最後再從 1 至 n 檢查一遍 count
是哪個數字出現兩次？是哪個數字出現0次？分別存到 ans 的第 0 和第 1 格







vector<int> ans(2);
for(int i=1;i<=n;i++){
    if(count[i]==2) ans[0]=i;
    if(count[i]==0) ans[1]=i;
}
return ans;

【學生練習題】

題目給我們一個名為 grid 的二維 vector，尺寸是 n*n
裡面剛好是 1 至 n*n 這些數字裡面
一個重複，一個缺失，其他正好出現一次
請找出重複的數字和缺失的數字

【學生練習題】

題目給一個名為 nums 的一維陣列，長度是 n+1
請問是否這 n+1 個數字裡面，n 總共有兩個
且 1, 2, …, n-1 這些數字各有一個呢？

首先令 n 為 nums.size()-1，就可以建立表格做計數
請注意 nums 裡面可能會有比 n 大的值，若看到了就要立刻回傳 false
不要放進計數表格裡（因為表格裡沒有他對應的格子！）

沒有明確數值範圍

上述的例題和類題都能夠從 input 推論出數值的範圍
例如例題的數字是 1 至 n，所以我們可以準備長度為 n+1 的陣列來計數
類題的數字是 1 至 n*n，所以我們可以準備長度為 n*n+1 的陣列來計數…

若是沒辦法直接從 input 推論出數值範圍
我們可以依據題目保證的數值大小來準備計數的陣列

【例題】

題目給一個名為 arr 的一維陣列
若有個數字 x 在 arr 裡出現的次數正好為 x 次
那麼 x 就是個幸運數字
請找出最大的幸運數字並回傳
如果幸運數字不存在，請回傳 -1

這是 Leetcode 上的題目，連結是 Leetcode 1394

因為題目裡有保證說 arr 裡面的數字最大為 500
我們就可以開一個大小為 501 的陣列來幫助計數














// 長度固定為 501 的陣列，全部歸零
int count[501] = {0};
// 拜訪 arr 裡面的每個數，記錄出現次數
for(int i=0;i<arr.size();i++){
    count[arr[i]]++;
}
// 從最大的數字 500 檢查到最小的數字 1 
for(int i=500;i>=1;i--){
    // 一旦發現幸運數字即可回傳
    if(count[i]==i) return i;
}
// 若迴圈結束後都沒有數字被回傳，代表沒有幸運數字
return -1;

【學生練習題】

題目給一個陣列共有 2n 個數字，其中有 n 個數字是相同的，其餘皆不同
請找出出現了 n 次的那個數字

提示：
題目保證數字範圍不超過10000，所以可以用長度為 10001 的陣列計數

【學生練習題】

題目給一個名為 nums 的陣列，請判斷是否能把這些數字分成兩堆，且兩堆裡面都沒有重複的數字

也就是說，如果 nums 裡面有數字重複了超過兩次，就不可以，否則就可以
題目保證數字範圍不超過100，所以可以用長度為 101 的陣列計數

【學生練習題】

題目給一個名為 nums 的陣列，請找出所有「只出現一次」的數字，並算出這些數字的總和

先計數，再看看有哪些數字出現次數為1，將它們加總

【學生練習題】

題目給一個二維陣列 nums
nums 裡面的每一個一維陣列裡都沒有重複的數字
但是會有些數字同時出現在多個一維陣列裡
請找出所有這樣的數字

可以統計 nums 裡每個數字出現的次數，並找出所有出現次數為nums.size()的數字
注意題目要求回傳的是依照小排到大的陣列，因此最後迴圈可以從小的數字往大的數字逐一拜訪

【學生練習題】

村裡有 n 個人，編號為 1 到 n，其中有一個人是法官
法官不相信任何人，且法官以外的所有人都相信法官
題目給一個數字 n 和一個二維陣列 trust
trust 裡面的每一行都代表「編號為 trust[i][0] 的人」相信「編號為 trust[i][1] 的人」
請依據判斷誰是法官的規則，找出法官

可以用兩個陣列，一個統計每個人「相信幾個人」
另一個統計每個人「被幾個人相信」
最後再找出誰「相信0個人且被n-1個人相信著」

區間問題

【例題】

題目給一個二維陣列 ranges
對於每一個 ranges[i]，它代表從 ranges[i][0] 到 ranges[i][1] 的範圍都被覆蓋了
題目還給了一個 left 和一個 right
請問從 left 到 right 的整個範圍都有被覆蓋到嗎？

這是 Leetcode 上的題目，連結是 Leetcode 1893

我們可以用一個 bool 的陣列來代表每一個座標有沒有被覆蓋到
把 ranges 裡的每個線段都蓋上去
再從 left 到 right 依序檢查是否有任何一個座標沒被覆蓋
題目表示了座標都在 1 到 50 的範圍內，所以用長度為 51 的陣列即可













bool covered[51] = {false}; // 先全部設為 false
for(int i=0;i<ranges.size();i++){
    // 被每個 ranges 覆蓋到的座標，都設為 true
    for(int j=ranges[i][0];j<=ranges[i][1];j++) covered[j] = true;
}
// 從 left 檢查到 right
for(int i=left;i<=right;i++){
    // 如果有任何一處沒被覆蓋，回傳 false
    if(!covered[i]) return false;
}
// 都檢查完了，代表都有覆蓋到
return true;

適用題型：配對或分配問題

剛才的題目只關注哪些人的數量符合條件
接下來的題目要用到所有人的數量，來達成配對或分配

平分問題

【例題】

題目給一個名為 words 的陣列
裡面有k個字串，每個都由小寫英文字母組成
請問能不能把這些字串裡面的所有英文字母重新分配成k組
使得每一組裡面的英文字母種類數量都相同呢？
例如 ["ab","aabc","bcc"] 可以重新分配成三組，每組有 a, b, c 各一個

這是 Leetcode 上的題目，連結是 Leetcode 1897

要判斷一堆英文字母能不能平分成 k 組
我們要檢查每個英文字母的數量是不是皆為 k 的倍數
若有任何一個英文字母數量不為 k 的倍數，他就無法被平分成 k 等分了

另外，要如何對「英文字母」做統計呢？
我們可以把 'a' 的數量存在第 0 格
'b' 存在第 1 格, …, 'z' 存在第 25 格, 以此類推
這樣就能用長度為 26 格的陣列來計數了！

對於任意小寫英文字母
我們只要算出他在字元表裡離 'a' 有多遠
就可以得知他應該存在第幾格
這就是將英文字母轉換成數字的小技巧



















// 長度為 26 格的陣列，每格歸零
int count[26] = {0};
// 拜訪 words 裡面的每個字串
for(int i=0;i<words.size();i++){
    // 拜訪字串裡的每個字元
    for(int j=0;j<words[i].length();j++){
        // 把這個字元減去 'a' 即可得知他的數量要存在哪一格
        // 把那一格 +1
        count[words[i][j]-'a']++;
    }
}
// 檢查這 26 個字母，大家的數量都是 words.size() 的倍數嗎？
for(int i=0;i<26;i++){
    // 若有一個字母的數量不是 words.size() 的倍數，即無法平分 
    if(count[i]%words.size()!=0) return false;
}
// 大家都可被 words.size() 整除，代表可以平分！
return true;

【學生練習題】

題目給一個名為 nums 的陣列，請問能不能把裡面的數字均分成兩組呢？

這一題不需要處理字元，只是一般的數字，範圍為 1 至 500
計算完數量後，只需要檢查大家的數量是否皆為 2 的倍數即可

【例題】

題目給一個名為 deck 的陣列，裡面有一些數字
請問是否能夠把這些數字均分成多個組呢？
也就是說，是否存在一個數字 x （大於1）能讓我們把 deck 裡的數字均分成 x 組呢？

這是 Leetcode 上的題目，連結是 Leetcode 914
我們要做的就是統計每個數字的數量，並算出大家的最大公因數是否大於 1
計算公因數可以使用 c++ 的內建函數 gcd

  • 計算 a, b 兩數的最大公因數可以呼叫 gcd(a, b)
  • 計算 a, b, c 三數的最大公因數可以先取 a 和 b 的最大公因數，再和 c 取最大公因數，也就是 gcd(gcd(a, b), c)
  • 計算某個陣列 arr 裡面每個數字的最大公因數，可以寫成
    • g = arr[0];
    • for(int i=1;i<arr.size();i++) { g = gcd(g, arr[i]);}
    • 最後 g 就是整個陣列 arr 的最大公因數

應用到這題如下所示：
















// 先完成計數
int count[10001] = {0};
for(int i=0;i<deck.size();i++){
    count[deck[i]]++;
}
// 計算大家數量的公因數
// 先把最大公因數 greated_common_divider 初始化為 deck 裡任一數字的數量
int greated_common_divider = count[deck[0]];
for(int n=0;n<10000;n++){ // 拜訪每個數量
    if(count[n]==0) continue; // 跳過數量為 0 的
    // 用此數的數量來更新「目前的最大公因數」
    greated_common_divider = gcd(greated_common_divider, count[n]); 
}
// 若最大公因數大於 1 則答案為 true，否則為 false
return greated_common_divider>1;

配對問題

【例題】

題目給一個字串 s
請問從 s 裡面取若干個字元能夠組成的最長回文可以是多長？
舉例來說，s="abccccdd"
我們可以取一個 a，四個 c，兩個 d，拼成 "dccaccd"，因此答案為 7

這是 Leetcode 上的題目，連結是 Leetcode 409

回文就是前後對稱的字串，像是 ABCBA 或是 ABBA
第一個字母等於最後一個字母，第二個字母等於倒數第二個字母…兩兩配對以此類推
因此要盡可能從 s 裡取走很多的「對子」
例如：若 A 有 5 個，我們就取走 4 個 A；若 B 有 6 個，我們就把 6 個 B 都取走…
如果取完所有對子還有剩下的（例如 5 個 A 取走 4 個剩下一個）
就取一個來放在回文的正中間，它不需跟其他字母配對（像是 ABCBA 的 C）

這一題的英文字母有大寫也有小寫，總共有 52 種可能，稍微麻煩一點









// 用 52 格的陣列來計數
int count[52] = {0};
for(int i=0;i<s.length();i++){
    // 如果是小寫，就放在第 0 至 25 格
    if('a'<=s[i] && s[i]<='z') count[s[i]-'a']++;
    // 如果是大寫，就放在第 26 至 51 格
    else count[s[i]-'A'+26]++;
}

接下來計算「可以組成幾個對子」和「剩下幾個孤隻」
也就是「除以二的商是幾」，「餘數是幾」







int num_of_pairs = 0; // 計算有幾個對子
int num_of_singles = 0; // 計算剩幾個孤隻
for(int i=0;i<52;i++){ // 拜訪這 52 個英文字母
    num_of_pairs += count[i]/2;
    num_of_singles += count[i]%2;
}

最後取可以做成回文的材料




int ans = num_of_pairs*2; // 對子全部拿來使用
if(num_of_singles>0) ans++; // 若有孤隻，就拿一個
return ans;

【學生練習題】

題目給一個名為 nums 的陣列，請問可以把裡面的數字配成幾對？剩下幾個孤隻？

這一題也只要用數字計數就好，不需處理字元
最後要回傳的是一維 vector，第 0 格放「有幾個對子」，第 1 格放「剩幾個孤隻」

適用題型：成員比對問題

兩組成員是否相同

【例題】

題目給兩個字串 s 和 t
請問兩者的字元組成是相同的嗎？
例如 "anagram" 和 "nagaram" 就是相同的
因為兩者都有三個 a，一個 g, 一個 m, 一個 n 和一個 r

這是 Leetcode 上的題目，連結是 Leetcode 242
我們要對於兩者的字元分別計數，再比對是否「每個字元在兩字串出現的次數皆相同」














if(s.length()!=t.length()) return false; // 如果長度不同，當然不可能成員一樣
// 我們已經非常熟悉的計數部分
int s_counter[26]={0};
int t_counter[26]={0};
for(int i=0;i<s.size();i++){
    s_counter[s[i]-'a']++;
    t_counter[t[i]-'a']++;
}
// 檢查每個英文字母，在 s 和 t 出現的次數是一樣的嗎？
for(int i=0;i<26;i++){
    if(s_counter[i]!=t_counter[i]) return false; // 只要有一個不一樣就是 false
}
return true; // 已確認完大家都一樣

【學生練習題】

題目給兩個陣列 target 和 arr，裡面各自有若干個數字
請問 target 和 arr 裡的數字成員組成是相同的嗎？
例如 target = [1,2,3,3], arr = [2,3,1,3] 就是相同的
target = [1,2,3,3], arr = [1,2,3,1] 就是不同的

和例題的解法相同，但這題是數字，不需要處理英文字母
請注意數字的範圍為 1 至 1000，因此需要 1001 格的陣列來計數

【學生練習題】

題目給兩個字串 s 和 t
t 比 s 多了一個字元，其餘組成成員完全相同
請找出 t 比 s 多出的那個字元

和例題一樣，先計數，且要處理英文字母對數字的轉換（字母減去 'a'）
然後找出唯一在 t 裡比在 s 裡面多出現一次的字母即可

【學生練習題】

題目給兩個字串 word1 和 word2
請問是不是每個英文字母「出現在 word1 裡的次數」和「出現在 word2 裡的次數」
相差都不大於 3 呢？

先計數，且要處理英文字母對數字的轉換（字母減去 'a'）
然後檢查是不是 26 個字母都是「兩個次數相減小於等於 3 且大於等於 -3」

材料是否夠用來組成目標

【例題】

題目給兩個字串 ransomNote 和 magazine
請問我們能夠從 magazine 裡取若干個字元重新排列組成 ransomNote 嗎？

這是 Leetcode 上的題目，連結是 Leetcode 383
先分別統計 ransomNote 和 magazine 的成員
如果每個英文字母在 ransomNote 裡出現的次數都不超過在 magazine 裡出現的次數，就可以

















// 熟悉的計數部分
int r_count[26] = {0};
int m_count[26] = {0};
for(int i=0;i<ransomNote.size();i++){
    r_count[ransomNote[i]-'a']++;
}
for(int i=0;i<magazine.size();i++){
    m_count[magazine[i]-'a']++;
}
// 檢查 26 個英文字母
for(int i=0;i<26;i++){
    // 如果 ransomNote 需要的比 magazine 提供的多，則不可
    if(r_count[i]>m_count[i]) return false;
}
// 已確認完每個字母都夠給 ransomNote 用
return true;

【學生練習題】

題目給一個陣列 words 裡面有一些字串（相當於一些 ransomNote）
還有一個字串 chars（相當於 magazine）
請問 words 裡面的哪些字串是能夠從 chars 裡取一些字元組合成的呢？
請將符合條件的這些字串長度加總並回傳

這一題可以拿 words 裡面的每一個字串 words[i] 來呼叫例題的函數
canConstruct(words[i], chars) 來幫助判斷「可以或不可以組成」
若可以，就將 words[i] 的長度加總到答案上

材料可以組成幾組目標

【例題】

題目給兩個字串 s 和 target
我們可以從 s 裡取若干個字母重新排列組成 target，且取過的字母不可重複利用
請問可以組成幾個 target？
例如 s = "ilovecodingonleetcode", target = "code"
則答案為 2，因為我們可以從 s 中汲取兩次 "code" 出來

這是 Leetcode 上的題目，連結是 Leetcode 2287
若 s 可以拼成 X 個 target，代表每個字母在 s 裡出現的次數都是在 target 裡的 X 倍或更多
反過來說
我們可以統計每個字母「在 s 裡出現的次數」是「在 target 裡出現的次數」的幾倍
再取 26 個字母裡的最小值即可
















// 計數
int s_count[26] = {0};
int t_count[26] = {0};
for(int i=0;i<s.length();i++){
    s_count[s[i]-'a']++;
}
for(int i=0;i<target.length();i++){
    t_count[target[i]-'a']++;
} 
int ans = s.length(); // 要算出所有倍數的最小值，先初始化成一個很大的值
for(int i=0;i<26;i++){
    if(t_count[i]==0) continue; // 如果此字母根本沒出現在 target 裡，就跳過他
    ans = min(ans, s_count[i]/t_count[i]); // 算倍數，並更新最小值
}
return ans;

【學生練習題】

題目給一個字串 text，請問以他為材料可以拼成幾個 "balloon"?

和例題類似，例題的 s 是這題的 text，例題的 target 是這題的 "balloon"

成員的交集

【例題】

題目給若干個字串，請找出這些字串共有的字元（複數個的也要算入）
例如 ["bella","label","roller"] 大家都有一個 e 兩個 l，所以答案是 ["e", "l", "l"]
例如 ["cool","lock","cook"] 的答案就是 ["c", "o"]，雖然 cool 和 cook 都有兩個 o，但因為 lock 只有一個 o，所以 o 在三者的共通點裡就只有一個

這是 Leetcode 上的題目，連結是 Leetcode 1002

首先是計數的部分
因為有多個字串，所以我們要用多個長度為 26 的陣列來計數
我們可以用尺寸為 (26, n) 的二維陣列（n 是字串的數量）來計數









// count[字母][編號] 存的是某字母在第某號的字串裡出現的次數
// 例如 count[0][5] 代表字母 'a' 在第 5 個字串裡出現的次數
vector<vector<int>> count(26, vector<int>(words.size(), 0));
for(int i=0;i<words.size();i++){
    for(int j=0;j<words[i].length();j++){
        count[words[i][j]-'a'][i]++;
    }
}

接著是共通點的部分
舉例來說，字母 a 在三個字串裡出現的次數分別為 5, 8, 4，那麼這三個字串的共通點就只有 4 個 a，因為 4 是 [5, 8, 4] 的最小值
也就是說，對於每個字母，我們都要找它在每個字串出現的次數的最小值，才可知最後答案要出現幾次這個字母












vector<string> ret;
for(int i=0;i<26;i++){ // 對於每個字母
    int min_count = count[i][0];
    for(int j=0;j<words.size();j++){ // 找出它在每個字串出現次數的最小值
        min_count = min(min_count, count[i][j]);
    }
    for(int j=0;j<min_count;j++){ // 於是這個字母要在答案裡重複 min_count 次
        ret.push_back(string(1, 'a'+i)); // 不知道為何題目要回傳字串，在此處理一下
    }
}
return ret;

【學生練習題】

題目給兩個整數陣列，請找出這兩個陣列共有的數字（複數個的也要算入）

這題只有兩個陣列，且不需處理字元！

用陣列無法處理的情況

在正式開始介紹 unordered_map 這個資料結構前
我們竟然已經光靠著陣列就解了 20 幾道計數問題
可見陣列用途真的很廣泛
但因為還是有不少「陣列無法處理」或「用陣列處理就會不太理想」的例子
讓我們一起來認識這些例子
並且學習如何使用 unordered_map 來解題

數字範圍太廣，浪費陣列空間

假設有一個題目，給一個陣列，裡面有 1000 個數字
這些數字的範圍是 1 到 1000000000
若題目要我們找出「出現了最多次的數字」
我們是不是就需要一個長度為 1000000000 的陣列來計數了呢
但明明題目裡只有 1000 個數字，代表我們最多只會用到 1000 個格子
剩下 999999000 個格子都浪費了
這樣的程式不只浪費記憶體，也會浪費時間（因為我們要看遍這1000000000格去找最大值）










int count[1000000000] = {0}; // 用了 1000000000 格記數
for(int i=0;i<1000;i++){ // 題目其實只有 1000 個數字，只是數字的值的範圍很大而已
    count[nums[1000]]++;
}
int ans = 0;
for(int i=0;i<1000000000;i++){ // 迴圈要跑 1000000000 才能找最大值
    ans = max(ans, count[i]);
}
return ans;

千奇百怪的資料型態

假設有一個題目，給一個陣列，裡面有 1000 個數字
這些數字的範圍都是 -1000000000 到 1000000000，要找出現最多次的數字
這就更慘了，先不論浪費記憶體的問題
負數根本沒有對應的格子可以存（因為陣列的編號是0和正整數）

或是有一個題目，給一個陣列，裡面有 1000 個「字串」
要找出現最多次的「字串」，這就完全沒辦法用陣列來計數了

從下一章開始，我們會介紹如何使用 unordered_map 來處理這些問題！

Last changed by 
 
Chu-Ling Ko
0
449
Published on HackMD