【每日算法Day 99】你们可能不知道只用20万赢到578万是什么概念

godweiyang

发布于 2020-04-16 16:07:15

7150

文章被收录于专栏：算法码上来算法码上来

题目链接

LeetCode 846. 一手顺子[1]

题目描述

爱丽丝有一手（hand）由整数数组给定的牌。

现在她想把牌重新排列成组，使得每个组的大小都是 W，且由 W 张连续的牌组成。

如果她可以完成分组就返回 true，否则返回 false。

说明：

1 <= hand.length <= 10000
0 <= hand[i] <= 10^9
1 <= W <= hand.length

示例1

输入：
hand = [1,2,3,6,2,3,4,7,8], W = 3
输出:
true
解释：
爱丽丝的手牌可以被重新排列为 [1,2,3]，[2,3,4]，[6,7,8]。

示例2

输入：
hand = [1,2,3,4,5], W = 4
输出:
false
解释：
爱丽丝的手牌无法被重新排列成几个大小为 4 的组。

题解

巧用 map

这也是最直观的一个方法，用 map 来保存每个数出现的次数。

然后从最小的数开始，以它作为顺子的开头，然后看顺子里的数在不在 map 里，在就次数减一，不在就直接返回 false 。

接着重复上面步骤，最后直到 map 为空，最后返回 true。

map 的特性就是你取它的第一个键值对，它的 key 就是最小的，这就很方便了。

排序统计

首先对手牌从小到大进行排序，然后从最小的开始，作为顺子开头，遍历之后的数。如果在数组里，并且没有被访问过，那么就标记为访问过了。

注意可以提前终止遍历，也就是如果发现某一个顺子还没遍历完，但是访问到的元素已经超过接在顺子后的数了，那就直接返回 false 。

排序统计2

这题还有个解法，来自于题解区网友 zhanzq，感觉挺不错的。但是我没怎么看懂，如果谁看懂了请教教我。

网友题解[2]

代码

巧用 map（c++）

class Solution {
public:
    bool isNStraightHand(vector<int>& hand, int W) {
        int n = hand.size();
        if (n%W) return false;
        map<int, int> count;
        for (auto x : hand) count[x]++;
        while (count.size()) {
            int start = count.begin()->first;
            for (int i = start; i < start+W; ++i) {
                if (count.find(i) == count.end()) return false;
                if (!--count[i]) count.erase(i);
            }
        }
        return true;
    }
};

排序统计（c++）

class Solution {
public:
    bool isNStraightHand(vector<int>& hand, int W) {
        int n = hand.size();
        if (n%W) return false;
        if (W==1) return true;
        sort(hand.begin(), hand.end());
        vector<int> vis(n, 0);
        for (int i = 0; i < n; ++i) {
            if (vis[i]) continue;
            int cnt = 1;
            vis[i] = 1;
            for (int j = i+1; j < n; ++j) {
                if (hand[j]>hand[i]+cnt) break;
                if (!vis[j] && hand[j]==hand[i]+cnt) {
                    vis[j] = 1;
                    cnt++;
                    if (cnt == W) break;
                }
            }
            if (cnt != W) return false;
        }
        return true;
    }
};

排序统计2，来自于网友zhanzq（c++）

class Solution {
public:
    bool valid(vector<int> &lst, int W){
        lst.push_back(0);
        int sz = lst.size();
        int pre = 0;
        vector<int> deltas(sz, 0);
        for(int i = 0; i < sz; i++){
            pre += deltas[i];
            if(pre < lst[i]){
                int delta = lst[i] - pre;
                pre = lst[i];
                if(i + W < sz){
                    deltas[i+W] -= delta;
                }
            }else if(pre > lst[i]){
                return false;
            }
        }
        return true;
    }

    bool isNStraightHand(vector<int>& hand, int W) {
        int sz = hand.size();
        if(sz%W){
            return false;
        }else{
            sort(hand.begin(), hand.end());
            vector<int> lst;
            int i = 0, j = 0;
            while(i < sz){
                while(j < sz && hand[i] == hand[j]){
                    j++;
                }
                lst.push_back(j - i);
                if(j >= sz){
                    break;
                }else if(hand[j] != hand[j-1] + 1){
                    lst.push_back(0);
                }
                i = j;
            }
            return valid(lst, W);
        }
    }
};