谁能想到，斗地主也能玩出算法 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：谁能想到，斗地主也能玩出算法

评论礼仪 见这里，违者直接拉黑。

[liwenhuiahh]

蹲个java版的

[RuiStarlit]

class Solution {
public boolean isPossible(int[] nums) {
HashMap<Integer, Integer> freq = new HashMap<>();
HashMap<Integer, Integer> need = new HashMap<>();

    for (int card: nums) {
        freq.put(card, freq.getOrDefault(card, 0)+1);
    }

    for (int v:nums) {
        if (freq.get(v) == 0) {
            continue;
        }

        if (need.getOrDefault(v, 0) != 0) {
            freq.put(v, freq.get(v) - 1);
            need.put(v, need.get(v) - 1);
            need.put(v + 1, need.getOrDefault(v + 1, 0) + 1); 
        } else if (freq.getOrDefault(v+1, 0) != 0 && freq.getOrDefault(v+2, 0) != 0) {
            freq.put(v, freq.get(v) - 1);
            freq.put(v+1, freq.get(v+1) - 1);
            freq.put(v+2, freq.get(v+2) - 1);
            need.put(v + 3, need.getOrDefault(v + 3, 0) + 1); 
        } else {
            return false;
        }

    }

    return true;
}

}

[xz777]

class Solution {
    public boolean isPossible(int[] nums) {
        HashMap<Integer,Integer> freq = new HashMap<>();
        HashMap<Integer,Integer> need = new HashMap<>();
        // 统计 nums 中元素的频率
        for(int n:nums){
            freq.put(n,freq.getOrDefault(n,0)+1);
        }

        for(int n:nums){
            // 已经被用到其他子序列中(排除)
            if(freq.get(n)==0) continue;
            // 先判断 n 是否能接到其他子序列后面
            if(need.containsKey(n) && need.get(n)>0){
                // n 可以接到之前的某个序列后面
                //对n的需求减一
                need.put(n,need.get(n)-1);
                freq.put(n,freq.get(n)-1);
                //对n+1的需求加一
                need.put(n+1,need.getOrDefault(n+1,0)+1);
            }else if(freq.containsKey(n)&&  freq.containsKey(n+1)&&freq.containsKey(n+2)
                && freq.get(n)>0 && freq.get(n+1)>0 && freq.get(n+2)>0){
                // 将 n 作为开头，新建一个长度为 3 的子序列 [n,n+1,n+2]
                freq.put(n,freq.get(n)-1);
                freq.put(n+1,freq.get(n+1)-1);
                freq.put(n+2,freq.get(n+2)-1);
                // 对 n + 3 的需求加一
                need.put(n+3,need.getOrDefault(n+3,0)+1);
            } else{
                // 两种情况都不符合，则无法分配
                return false;
            }

        }

        return true;
    }
}

java版

[zhongweiLeex]

补充一个使用贪心算法的方式，此方式优点难以理解，需要结合图和我写的注释理解

class Solution {
    public boolean isPossible(int[] nums) {
        HashMap<Integer,Integer> freq = new HashMap<>();//统计频率
        for(int i: nums){
            freq.put(i,freq.getOrDefault(i,0)+1);
        }
        for(int i : nums){
            int subNumb = 0;//子数组中元素个数 
            //往子数组中后面加的数的频率最低为 1
            int p = 1;
            while(freq.getOrDefault(i,0)>= p){
                // 频率为1的可以进这个循环 加到子数组后面
                //如果频率大于1， 只能加到子数组里面一个，因为一开始p=1，后面p更新为了原来的频率 > 1 
                //将p（原来的频率） 和 选用后剩余的频率比较，确实无法进入循环向子数组后面添加了
                //需要开辟一个新的子数组
              
                p = freq.get(i);//获取当前元素的 频率
                freq.put(i,p-1);//当前元素已经被选用了 频率减一
                subNumb++;//子数组长度+1
                i++;
            }
            if(subNumb>0 && subNumb<3){
                return false;
            }
        }
        return true;
    }
}

[Leochens]

js版

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var isPossible = function (nums) {

    // 这题比较特殊 使用2个哈希表来解决
    // freq[v]表示每个数字出现的次数 need[v]表示v可以添加到上一个子串的末尾的次数
    // 在分子序列遍历到某个数字的时候 可能有两种情况 
    // 1. 自成一派 自己开头 成为连续3个数字的第一个
    // 2. 和前面的连接上
    // 这两种情况应该优先选择第2种

    const freq = new Map();
    const need = new Map();

    // 统计出现次数
    nums.forEach(n => {
        if (freq.has(n)) {
            freq.set(n, freq.get(n)+1);
        } else {
            freq.set(n, 1);
        }
    })

    // 注意是nums
    for (let n of nums) {

        // 这个数字已经被接入其他子序列 用过了
        if (freq.get(n) === 0) {
            continue;
        }
        // 看看是否可以接入之前的序列
        if (need.has(n) && need.get(n) > 0) {
            // 从freq和need中减少一次计数
            freq.set(n, freq.get(n) - 1);
            need.set(n, need.get(n) - 1);

            // 对于下一个数字 是有需求接入这个子序列的
            need.set(n + 1, (need.get(n + 1) || 0) + 1);

        } else if (freq.get(n) && freq.get(n + 1) && freq.get(n + 2)) {
            // 不能接入之前的 看看是否可以自成一派
            // 连续三个数字
            freq.set(n, freq.get(n) - 1);
            freq.set(n + 1, freq.get(n + 1) - 1);
            freq.set(n + 2, freq.get(n + 2) - 1);
            // 三个之后的数字 可以有接入这个序列的需求
            need.set(n + 3, (need.get(n + 3) || 0) + 1);
        } else {
            // 都不行 就真不行了 分不了了
            return false
        }


    }
    return true;
};

[kakakong]

bool isPossible(vector<int>& nums) {
        vector<unordered_set<int>> caches;
        caches.push_back(unordered_set<int>{nums[0]});
        for (int i = 1; i < nums.size(); i++) {
            bool handled = false;
            for (int j = caches.size() - 1; j >= 0; j--) {
                // 序列中已经有该值了
                if (caches[j].count(nums[i])) continue;
                // 序列中没有该值，但是不连续了
                if (!caches[j].count(nums[i] - 1)) break;
                // 序列连续，插入值
                caches[j].insert(nums[i]);
                handled = true;
                break;
                
            }
            //如果值没有被处理，另外新建一个序列
            if (!handled) {
                caches.push_back(unordered_set<int>{nums[i]});
            }
        }
        for (auto cache: caches) {
            if (cache.size() < 3) return false;
        }
        return true;
    }

[Rasadell09]

东哥，想请教一下为什么一个数要优先判断自己是否可以接在已有的序列之后呢？有没有一种情况是必须让某个数称为开头才可以满足条件呢？优先判断接在已有序列之后是一种贪心的思想么？

[KLOSYX]

假设已经有了一个组成了已有的序列A，有一个新的数，它可以作为开头组成新的序列B也可以接在A的后面，那其实A+B也是满足条件的序列，所以能自己组成开头肯定也可以接在已有序列之后。其实这种算法得到的结果一定是总序列数最小的

[NanW3]

@Rasadell09 我的理解是如果一个数是接在已有序列之后，肯定能满足条件，因为已有序列中元素数量肯定>=3。而一个数自己开头的却不一定能满足条件。所以不会出现必须让某数开头才能满足条件的情况，因此优先判断是否能接在已有序列之后。

[LinjianLi]

补充一个新思路吧。因为题目说了原始数组是已排序的，所以感觉可以按顺序扫描，然后根据不同情况来做不同的操作。代码是基于 Python 的，里面的解释比较长，因为是从比较朴素的实现方法开始一步步探讨到优化后的方法。

class Solution:
    """
    659. Split Array into Consecutive Subsequences

    因为题目说了原始数组是已排序的，所以感觉可以按顺序扫描。

    遇到正常 +1 的情况时，加入当前序列。
    遇到相同的数字时，可能需要新开一个序列，也可能可以加入之前已有的序列末尾。
    例如 [1,1,2,2]，遇到重复的 1 就要新开一个序列，而遇到重复的 2 就可以加入序列 [1] 的末尾。
    遇到跳跃的数字时，就肯定需要新开一个序列。

    所以，根据以上推理，可能需要同时维护多个序列。
    并且还要知道当前扫描到的元素需要加到哪个序列尾部，所以可能要用哈希表。
    例如当前扫描到的元素是 k，那就需要找到所有以 k - 1 结尾的序列。

    当一个元素有多个候选序列可以放入时，为了满足“所有序列的长度都大于等于三”的条件，
    就应该优先选择短的候选序列放入，所以还需要知道每个候选序列的长度。
    最简单的办法是每次都对所有候选序列调用 len() 函数求长度，然后找到最短的，但是这样很耗时。

    想优化一下，可以用一个最小堆 min-heap 来存储，以数组长度作为排序的 key，这样就能减少每次寻找最短候选序列的时间。

    综上所述，需要一个哈希表记录不同末尾元素的序列，
    哈希表中的每一个键值对 (k, min_heap_k) 表示以 k 结尾的序列都存在了 min_heap_k 中。
    min_heap_k 是一个最小堆，其中的每一个元素都是以 k 结尾的序列，此最小堆排序的 key 是序列的长度。

    写到这里，发现其实我只关心每个序列的末尾元素，以及每个序列的长度，
    所以其实不需要存储整个序列，只需要存末尾元素和长度即可，这样能节省不少空间;
    然后又发现，其实末尾元素已经是由 k 指定了的，即必然是 k，所以只需要存储长度即可。

    可以再进一步化简代码，前面讨论了按顺序扫描时会遇到的 3 种情况，分别是正常加一、重复、跳跃。
    三种情况有不同的处理逻辑，可能是把元素添加到已有序列的末尾，也可能是用元素新开一个序列，
    需要写很多 `if ... else ...` 判断。
    但是可以发现，用某个元素新开一个序列，实际上可以看作是把这个元素添加到一个空序列的末尾。
    所以可以在扫描到元素 k 时，从哈希表中获取以 k 结尾的候选序列集合 S。
    若集合 S 不是空集，那就返回长度最小的那个候选序列；若集合 S 是空集，返回一个空序列作为长度最小的候选序列。
    这样我就只需要写“把元素加到对应序列末尾”的代码逻辑。

    写于 2022-08-19 10:52:41
    """
    def isPossible(self, nums: List[int]) -> bool:

        if len(nums) < 3:
            return False

        map_min_heap_k = {}

        # 第一个元素的处理先单独写出来，后面直接写循环，就不用再判断是否是第一个
        map_min_heap_k[nums[0]] = [1]
        nums = nums[1:]

        # 顺序扫描剩余元素
        for k in nums:

            if k not in map_min_heap_k:
                map_min_heap_k[k] = []
            if (k - 1) not in map_min_heap_k:
                map_min_heap_k[k - 1] = []

            min_heap_k_minus_1 = map_min_heap_k[k - 1]  # 找到以 k - 1 结尾的所有序列
            min_len_k_minus_1 = heapq.heappop(min_heap_k_minus_1) if len(min_heap_k_minus_1) > 0 else 0  # 选出长度最短的

            min_heap_k = map_min_heap_k[k]  # 找到存储以 k 结尾的所有序列的 min_heap_k
            heapq.heappush(min_heap_k, min_len_k_minus_1 + 1)  # 把之前以 k - 1 结尾的最短序列的长度加 1，插入 min_heap_k 中

            # print(k, map_min_heap_k)

        flag = True
        for k in map_min_heap_k:
            for l in (map_min_heap_k[k]):
                if l < 3:
                    flag = False
                    break
            if flag is False:
                break
        return flag


a = Solution()
b = a.isPossible([1,2,3])
print(True, b)
b = a.isPossible([1,2,3,3,4,5])
print(True, b)
b = a.isPossible([1,1,2,2,3,3])
print(True, b)
b = a.isPossible([1,2,3,3,4,4,5,5])
print(True, b)
b = a.isPossible([1,2,3,4,4,5])
print(False, b)
b = a.isPossible([1])
print(False, b)
b = a.isPossible([1,2])
print(False, b)

08/19/2022 10:53 提交，状态 Accepted。

[sophiezxf]

想不明白如果是[1,2,3,4,5,6]这个case，不是应该优先让4成为start，组成[4,5,6]么，如果优先让4拼在[1,2,3]的后面不就错了么，因为剩下的array长度不够了呀

[GoingMyWay]

题目要求的是连续的数。[1, 2, 3, 4, 5, 6]是连续的。但是[1, 2, 3, 6, 7, 8]就不是连续的了，需要分成[[1, 2, 3], [6, 7, 8]]。

[sophiezxf]

额，为什么不可以删评论呀，one or more subsequences。我明白了-v-

[brightwing23]

@sophiezxf 题目要求是可以分割数组可以组成一个或者多个subsequence， 所以你的例子它的subsequence就是它本身没毛病。每个frequency大于1的数才有可能是需要分割序列的地方。

[CryptoRbtree]

首先，把不连续的部分拆开，比如[1,2,2,3,3,4, 11,12,13]拆成[1,2,2,3,3,4],[11,12,13]分别处理。
然后把数组处理成每个数字的重复次数，例如[1,2,2,3,3,4,4,4,5,5,5,6,6,6,7,7,8]，可以处理为[1,2,2,3,3,3,2,1]

就拿这个例子说明，[1,2,2,3,3,3,2,1]
最左边的3个数字肯定是要连在一起的，所以最左边3个数字-1，然后去掉最左边的0，变成[1,1, 3,3,3,2,1]。在这一步中，要先判断前三个数是否是非递减的，如果有递减例如[2,1,2,3,3,3,2,1]，直接失败。
那么要不要继续往后延伸呢？如果后面的数字频次递增或者不变的时候，往后延伸，否则不再延伸。
对于[1,2,2,3,3,3,2,1]这个例子，[1,2,2,3,3,3]都在递增，所以处理到3为止，这样一轮之后，变成[1,1,2,2,2,2,1]

然后重复上述过程，最后数组为空，说明成功。

class Solution {
public:
    bool isPossible(vector<int>& nums) {
        vector<vector<int>> arrs = split(nums);
        for (vector<int> &arr : arrs) {
            if (!subIsPossible(arr)) return false;
        }
        return true;
    }

    vector<vector<int>> split(const vector<int>& nums) {
        vector<vector<int>> results;
        vector<int> result{1};
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] == nums[i - 1]) {
                result.back()++;
            } else if (nums[i] == nums[i - 1] + 1) {
                result.push_back(1);
            } else {
                results.push_back(std::move(result));
                result.resize(0);
                result.push_back(1);
            }
        }
        results.push_back(std::move(result));
        return results;
    }

    bool subIsPossible(vector<int>& nums) {
        assert(nums[0] > 0);
        const int N = 3;
        int left = 0;
        int right = nums.size() - 1;
        while (left <= right) {
            int minRight = left + N - 1;
            if (minRight > right) return false;
            for (int i = left + 1; i <= minRight; i++) {
                if (nums[i] < nums[i - 1]) return false;
            }

            int curr = left;
            while (curr <= minRight) {
                nums[curr]--;
                if (nums[curr] == 0) left++;
                curr++;
            }

            while (curr <= right && nums[curr] >= nums[curr - 1] + 1) {
                nums[curr]--;
                if (nums[curr] == 0) left++;
                curr++;
            }
        }
        return true;
    }
};

[chenxiiang]

Java保存所有子序列的，自己跑了几个用例，看起来没有问题，大概流程应该是没错的

    //如果需要的不是布尔值，而是要把所有的子序列都打印出来，可以把need改为Map<Integer, List<List<Integer>>>，表示可以以integer结尾的所有的子序列，每个子序列是是一个List<Integer>
    boolean isPossible1(int[] nums) {
        Map<Integer, Integer> freq = new HashMap<>();
        Map<Integer, LinkedList<LinkedList<Integer>>> need = new HashMap<>();
        Arrays.stream(nums).forEach(num -> freq.put(num, freq.getOrDefault(num, 0) + 1));
        for (int n : nums) {
            if (freq.get(n) == 0) {
                continue;
            }
            if (need.containsKey(n) && need.get(n).size() > 0) {
                //可以接到已有序列后面
                freq.put(n, freq.get(n) - 1);
                //随便取一个能以n结尾的序列
                LinkedList<Integer> seq = need.get(n).pollLast();
                seq.addLast(n);
                need.putIfAbsent(n + 1, new LinkedList<>());
                need.get(n + 1).offerLast(seq);
            } else if (freq.containsKey(n) && freq.containsKey(n + 1) && freq.containsKey(n + 2) && freq.get(n) > 0
                && freq.get(n + 1) > 0 && freq.get(n + 2) > 0) {
                //将n作为开头
                freq.put(n, freq.get(n) - 1);
                freq.put(n + 1, freq.get(n + 1) - 1);
                freq.put(n + 2, freq.get(n + 2) - 1);
                //新建一个长度为3的子序列
                LinkedList<Integer> seq = new LinkedList<>();
                seq.addLast(n);
                seq.addLast(n + 1);
                seq.addLast(n + 2);
                need.putIfAbsent(n + 3, new LinkedList<>());
                need.get(n + 3).offerLast(seq);
            } else {
                return false;
            }
        }

        //打印切分出的所有子序列
        for (LinkedList<LinkedList<Integer>> list : need.values()) {
            if (list.isEmpty()) {
                continue;
            }
            for (LinkedList<Integer> list1 : list) {
                //每个list1就是一个序列
            }
        }
        return true;
    }

[cloudersecurity]

哪位大佬能解释一下{1, 2, 3, 4, 4, 5}这个序列为什么是false？？？分成123和445或者就它本身不满足条件吗？

[marcmk6]

逐个遍历，如果可以放进某个桶不违反规则就放最靠后的桶，如果没有任何合适的桶就新开一个桶放进去

[NyankoKaro]

一个元素只有两种情况:

1. 作为一个新序列的开头
2. 作为一个已有序列(长度至少已为3)的后继元素

一个元素应当优先作为一个已有序列的后继元素, 迫不得已(没有已有序列时)才作为新序列开头

原因: 假设当前元素为i

情况:

1. i+1不存在

   1无法继续, 2符合继续条件

2. i+1存在, i+2不存在

   1无法继续, 2符合继续条件

3. i+1, i+2存在

   1, 2均符合继续条件

可知作为后继元素是最优决策, 满足贪心性质