[846] Hand of Straights

ㄟ～寫的很慢沒有錯啦～但是誰叫它的hint 說什麼"符合就拿掉, 等到空了就是達成條件"的說法呢！！！先貼吧Orz 之後再去姐妹題寫了有map 的寫法好了...如果我有參透C要怎麼寫的話= =

int comp(const void *a, const void *b)

{

return (*(int*)a - *(int*)b);

}

bool remove_target(int target ,int* hand,int handSize)

{

for (int i=0;i<handSize; i++)

{

if (hand[i]==target)

{

while (i<handSize-1)

{

hand[i]= hand[i+1];

i++;

}

return true;

}

}

return false;

}

bool isNStraightHand(int* hand, int handSize, int groupSize) {

if (handSize % groupSize != 0)

return false;

int group_len = handSize / groupSize;

qsort(hand, handSize, sizeof(int),comp);

bool atlease = false;

for (int i=0; i<group_len; i++)

{

int start = hand[0];

int j=0;

while (j<groupSize)

{

if (!remove_target(start+j, hand, handSize))

{

if (j>0)

return false;

else

break;

}

j++;

handSize--;

}

if (j==groupSize && !atlease)

atlease = true;

}

return atlease;

}

結果~姐妹題的測資不一樣，以為是快寫法的，其實慢的要死XD 那只好先把, 用掉的數目設成 -1 的寫法先貼在這裡的update了QQ

int comp(const void *a, const void *b)

{

return (*(int*)a - *(int*)b);

}

bool isNStraightHand(int* hand, int handSize, int groupSize) {

if (handSize%groupSize !=0)

return false;

qsort(hand, handSize, sizeof(int), comp);

for (int i=0; i<handSize; i++)

{

if (hand[i]<0)

continue;

int idx = i;

int start = hand[idx];

for (int j=0; j<groupSize; j++)

{

while (idx <handSize && hand[idx]< start+j)

idx++;

if (idx==handSize || hand[idx] != start+j)

return false;

hand[idx++] = -1;

}

}

return true;

}

[20251104更新]

我也可以寫不用sorting 的版本了?! 感覺應該要加速一下但是現在有點懶 QQ

bool check(int* count, int start, int groupSize) {

for (int i= start; i<start + groupSize; i++)

{

if (count[i]==0)

return false;

count[i]--;

}

return true;

}

bool isNStraightHand(int* hand, int handSize, int groupSize) {

if (handSize % groupSize != 0 )

return false;

int *count = calloc (1000000001, sizeof(int));

int min = INT_MAX;

int max = INT_MIN;

for (int i=0; i<handSize; i++)

{

count[hand[i]]++;

if (hand[i] < min)

min = hand[i];

if (hand[i] > max)

max = hand[i];

}

for (int i=min; i<= max-groupSize +1; i++ )

{

if (count[i] ==0)

continue;

while (count[i] > 0)

if (!check(count, i,groupSize ))

return false;

}

for (int i=min; i<= max; i++ )

if ((count[i] >0))

return false;

return true;

}