题目链接:https://leetcode-cn.com/problems/x-of-a-kind-in-a-deck-of-cards/
这是力扣推送的每日练习题,难度是简单,应该是团队以前做题的中等水平。
思路:
1、一开始想用异或,但尝试了很多次之后总是出现大大小小的问题。所以改用一般方法。
2、题目没有明确说是分多少组,比如[1,1,1,1,1,1],分成两组可以,分成三组也可以。而每组最少得有两个人,故可以先从每组两个人开始,用 总人数/每组人数 得出 有多少组,然后遍历数组,查每组边界左右之外的区域是否存在不相同的值(如[1,1|2,2|3,3|4,4] “|”左右就是边界附近,而2与2的比较就不是。
容易出错的地方:
1、当每组人数上升的时候, 总人数/每组人数不一定能整除,故要加以判断,找出能整除的数再参与运算。
2、由于我们是从人数升序,组降序开始,人数最低是两人,组最低是一组,所以要特别注意[1,1]这种极限情况,由于我的算法过于垃圾的问题,一开始[1,1],[1,1,1],[1,1,1,1]的结果分别为false false true,实际上都是true才对。
代码如下:
bool hasGroupsSizeX(vector<int>& deck)
{
int flag;
int group_number,people_number=2;
int n = deck.size();
if (n < 2) return false;
sort(deck.begin(), deck.end());
while (n%people_number!=0)//找到第一个能整除的组
people_number++;
group_number = n / people_number;
while (group_number > 1)
{
flag = 1;
for (int i = 1;i < n;i++)
{
if (deck[i] != deck[i - 1]&& i% people_number != 0)
{
flag = 0;
people_number++;
while (n % people_number != 0)
people_number++;
break;
}
}
if (flag == 1) return true;
group_number = n / people_number;
}
if (group_number == 1) //判断[1,1]这种情况
{
for (int i = 1;i < n;i++)
if (deck[i] != deck[i - 1])
return false;
return true;
}
return false;
}