Giả sử Rima có một bàn bài, được cho dưới dạng một mảng các số nguyên. Bây giờ cô ấy muốn xáo trộn các thẻ thành các nhóm để mỗi nhóm có kích thước là W và bao gồm W thẻ liên tiếp. Chúng tôi phải kiểm tra xem nó có khả thi hay không.
Vì vậy, nếu các thẻ là [1,2,3,6,2,3,4,7,8] và W =3, thì câu trả lời sẽ là đúng, vì cô ấy có thể sắp xếp lại chúng như [1,2,3] , [2,3,4], [6,7,8]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- Xác định m bản đồ và lưu trữ tần suất của từng phần tử trong tay vào m
- trong khi kích thước bàn tay không phải là 0
- trước:=0
- it:=con trỏ đến cặp khóa-giá trị đầu tiên trong m
- cho tôi trong phạm vi từ 0 đến W - 1
- trong khi giá trị của nó là 0, nó:=trỏ đến cặp tiếp theo
- nếu i> 0 và khóa của nó - 1 =trước hoặc i =0, thì
- giảm giá trị của nó đi 1
- trước:=chìa khóa của nó
- nếu không thì trả về false
- it:=trỏ đến cặp tiếp theo
- n:=n - W
- trả về true.
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#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));
} Đầu vào
[1,2,3,6,2,3,4,7,8] 3
Đầu ra
1