แฮนด์ออฟสเตรทใน C++

สมมติว่า Rima มีไพ่ในมือ โดยกำหนดให้เป็นอาร์เรย์ของจำนวนเต็ม ตอนนี้เธอต้องการสับไพ่ออกเป็นกลุ่มเพื่อให้แต่ละกลุ่มมีขนาด W และประกอบด้วยไพ่ W ที่ต่อเนื่องกัน เราต้องตรวจสอบก่อนว่าเป็นไปได้หรือไม่

ดังนั้นหากไพ่เป็น [1,2,3,6,2,3,4,7,8] และ W =3 คำตอบก็จะเป็นจริง เพราะเธอสามารถจัดเรียงใหม่ได้เช่น [1,2,3] ,[2,3,4],[6,7,8]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดแผนที่ m และเก็บความถี่ของแต่ละองค์ประกอบในมือเป็น m
• ในขณะที่ขนาดของมือไม่ใช่ 0
  • ก่อนหน้า :=0
  • it :=ชี้ไปที่คู่คีย์-ค่าคู่แรกในหน่วย m
  • สำหรับ i ในช่วง 0 ถึง W – 1
    • ในขณะที่ค่าของมันคือ 0 มัน :=ชี้ไปที่คู่ถัดไป
    • ถ้า i> 0 และคีย์ของมัน – 1 =ก่อนหน้าหรือ i =0 แล้ว
      • ลดค่าลง 1
      • ก่อนหน้า :=คีย์ของมัน
    • มิฉะนั้นคืนค่าเท็จ
    • มัน :=ชี้ไปที่คู่ถัดไป
  • n :=n – W
• คืนค่าจริง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool isNStraightHand(vector<int>& hand, int W) {
      map <int, int> m;
      int n = hand.size();
      if(n % W != 0) return false;
      for(int i = 0; i < n; i++){
         m[hand[i]]++;
      }
      while(n){
         map <int, int> :: iterator it = m.begin();
         int prev = 0;
         for(int i = 0; i < W; i++){
            while(it->second == 0) it++;
            if((i > 0 && it->first - 1 == prev) || i == 0){
               it->second--;
               prev = it->first;
            }else{
               return false;
            }
            it++;
         }
         n -= W;
      }
      return true;
   }
};
main(){
   vector<int> v = {1,2,3,6,2,3,4,7,8};
   Solution ob;
   cout << (ob.isNStraightHand(v, 3));
}

อินพุต

[1,2,3,6,2,3,4,7,8]
3

ผลลัพธ์

1