题意:给你一个数组vector,给你一个数W,问能否将vector数组均分,对每份来说数量都是W,而且每份都是连续的数字。
解题思路:先对vector做个排序,然后使用一个map(其实可以使用set的)存储下标数,遍历map通过iter->first获得vector的下标,然后判断取出的一列数否能排成连续的一个W序列,最后判断总序列数是否等于vector.size() / W。
class Solution {
public:
bool isNStraightHand(vector<int>& hand, int W) {
if(hand.size() % W) return false;
sort(hand.begin(), hand.end());
map<int, int> imap;
for(int i = 0; i < hand.size(); i++)
imap[i] = 0;
int times = hand.size() / W;
int len = 0, n = 0, cnt = 0;
for(map<int,int>::iterator iter = imap.begin();
iter != imap.end(); ){
cout << iter->first << " " << hand[iter->first] << endl;
if(len == 0){
n = hand[iter->first];
len++;
}else if(hand[iter->first] - n == 1){
n = hand[iter->first];
len++;
}else if(hand[iter->first] - n == 0){
iter++;
continue;
}else{
return false;
}
map<int,int>::iterator tmp = iter;
iter++;
imap.erase(tmp);
if(len == W){
cnt++;
len = 0;
iter = imap.begin();
continue;
}
}
return cnt == times;
}
};
需要注意的地方:
map 一边遍历一边删除。
map<int, int> imap;
imap[0] = 0;
imap[1] = 1;
imap[2] = 2;
for(map<int, int>::iterator iter = imap.begin(); iter != imap.end(); ){
if(iter->second == 1){
map<int, int>::iterator tmp = iter;
iter++; //iter指向下一个元素。
imap.erase(tmp); //把该元素从imap中删除
continue; //跳过循环体内的内容
}
iter++ //如果把iter放在for循环的第三部分,continue之后还会执行,会造成iter++重复。
}