這是悅樂書的第352次更新，第377篇原創
01 看題和準備
今天介紹的是
LeetCode
算法題中
Easy
級别的第
214
題（順位題号是
914
）。在一副牌中，每張牌上都寫有一個整數。
當且僅當您可以選擇
X >= 2
時才傳回
true
，以便可以将整個牌組分成一組或多組牌，其中：
- 每組都有
X
- 每組中的所有牌都具有相同的整數。
例如：
輸入：[1,2,3,4,4,3,2,1]
輸出：true
說明：可能的分區[1,1]，[2,2]，[3,3]，[4,4]
輸入：[1,1,1,2,2,2,3,3]
輸出：false
說明：沒有可能的分區。
輸入：[1]
輸入：[1,1]
說明：可能的分區[1,1]
輸入：[1,1,2,2,2,2]
說明：可能的分區[1,1]，[2,2]，[2,2]
注意：
- 1 <= deck.length <= 10000
- 0 <= deck[i] <10000
02 第一種解法
題目的意思是将數組deck中的元素進行分組，值相等的劃分為同一組，每一組中的元素個數都相等，且大于等于2。我們可以使用一個
HashMap
，以
deck
中的元素為
key
，以其出現次數為
value
，對
HashMap
的
value
值進行周遊。
最理想的情況，
HashMap
中隻有一組
key-value
，但測試用例中肯定不會這麼輕易讓你AC。來看幾組例子分析下規律：
{1,1,1,2,2,2,3,3}
{{1,1,1},{2,2,2},{3,3}} --> {3,3,2}
{1,1,2,2,2,2,3,3,3,3,3,3}
{{1,1},{2,2,2,2},{3,3,3,3,3,3}} --> {2,4,6}
第一個例子中，他們的最大公約數為1，即分組的組數存在奇偶分布的情況。
第二個例子中，他們的最大公約數為2，即分組的組數都是偶數，并且對于其中的4個2和6個3，是還可以繼續拆分的，4個2拆成兩組2個2，6個3拆成三組2個3。
是以，我們隻需要判斷
HashMap
中每對資料的最大公約數是不是等于1即可。
public boolean hasGroupsSizeX(int[] deck) {
if (deck.length < 2) {
return false;
}
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int num : deck) {
map.put(num, map.getOrDefault(num, 0)+1);
}
int count = 0;
for (Integer value : map.values()) {
if (value < 2) {
return false;
}
if (count == 0) {
count = value;
} else {
if (count != value) {
int gcd = 1;
for (int i=1; i<= count || i<=value; i++) {
if (count%i == 0 && value%i == 0) {
gcd = i;
}
}
if (gcd == 1) {
return false;
}
}
}
}
return true;
}
03 第二種解法
思路和第一種解法一樣，隻是将其中部分代碼抽離了出來，并且簡化了一些
if-else
判斷。
public boolean hasGroupsSizeX2(int[] deck) {
if (deck.length < 2) {
return false;
}
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int num : deck) {
map.put(num, map.getOrDefault(num, 0)+1);
}
int min = 10001;
for (Integer num : map.values()) {
min = Math.min(min, num);
}
if (min == 1) {
return false;
}
for (Integer num : map.values()) {
if (getGCD(min, num) == 1) {
return false;
}
}
return true;
}
public int getGCD(int a, int b) {
int gcd = 1;
for (int i=1; i<= a || i<=b; i++) {
if (a%i == 0 && b%i == 0) {
gcd = i;
}
}
return gcd;
}
04 第三種解法
因為限定了數組
deck
中元素值範圍，是以我們可以使用一個整型數組
count
來計算
deck
中各元素的出現次數，然後周遊
count
中的元素，求出他們的最大公約數，隻要有一對數的最大公約數等于1，就直接傳回false。
public boolean hasGroupsSizeX3(int[] deck) {
int[] count = new int[10001];
for (int num : deck) {
count[num]++;
}
int temp = -1;
for (int num : count) {
if (num > 0) {
if (num < 2) {
return false;
}
if (temp == -1) {
temp = num;
} else {
if (getGCD(temp, num) == 1) {
return false;
}
}
}
}
return true;
}
public int getGCD(int a, int b) {
int gcd = 1;
for (int i=1; i<= a || i<=b; i++) {
if (a%i == 0 && b%i == 0) {
gcd = i;
}
}
return gcd;
}
05 第四種解法
對第三種解法，我們還可以再優化下，将求最大公約數的方法獨立處理，并且用遞歸處理。
public boolean hasGroupsSizeX4(int[] deck) {
int[] count = new int[10001];
for (int num : deck) {
count[num]++;
}
int tem = count[deck[0]];
for (int num : count) {
if (num > 0) {
tem = gcd(tem, num);
}
}
return tem > 1;
}
/**
* 利用遞歸求a和b的最大公約數
* @param a
* @param b
* @return
*/
public int gcd(int a, int b) {
return a == 0 ? b : gcd(b%a, a);
}
06 小結
算法專題目前已連續日更超過六個月，算法題文章220+篇，公衆号對話框回複【資料結構與算法】、【算法】、【資料結構】中的任一關鍵詞，擷取系列文章合集。
以上就是全部内容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！
![241 Different Ways to Add Parentheses（C代碼版）[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)