C++ 中一副牌中的 X 张同类牌

假设我们有一副牌，每张牌上都写着一个整数。我们需要检查是否可以选择一个 X（X >= 2），使得可以将整副牌分成 1 个或多个组，并且满足以下条件：每组恰好有 X 张牌。每组中的所有牌都具有相同的数字。

因此，如果输入类似于 deck = [1,2,3,4,4,3,2,1]，则输出将为 True，因为可能的划分是 [1,1],[2,2],[3,3],[4,4]。

为了解决这个问题，我们将遵循以下步骤：

  • 定义一个映射 mp
  • 对于 deck 中的所有 x
    • （将 mp[x] 加 1）
  • 对于 mp 中的所有键值对 x
    • ans := (ans 和 x 的值) 的最大公约数
  • 当 ans > 1 时返回 true，否则返回 false

让我们看下面的实现来更好地理解：

示例

实时演示

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool hasGroupsSizeX(vector<int>& deck) {
      unordered_map<int, int> mp;
      int ans;
      for (auto x : deck)
         mp[x]++;
      for (auto x : mp)
         ans = __gcd(ans, x.second);
      return (ans > 1);
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2,3,4,4,3,2,1};
   cout << (ob.hasGroupsSizeX(v));
}

输入

{1,2,3,4,4,3,2,1}

输出

1

更新于： 2020-07-04

239 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告