逐步解析力扣846. 一手顺子 （贪心）

逐步解析力扣846. 一手顺子 （贪心）

https://leetcode-cn.com/problems/hand-of-straights/solution/yi-shou-shun-zi-by-leetcode-solution-4lwn/

理解

• 一副手牌hand和可以分的顺子组数量groupSize，当手牌数取余groupSize等于0时才可能完成分组，否则直接返回false
• 贪心对于顺序的处理，存哈希表最合适，先将hand里所有数据都存到表中，以(x,1)的形式存，value+1
• 当组出一幅牌的时候，将该牌从表中value-1，如果表内为0则remove，下次遍历的时候直接跳过已经组好的这幅牌
• 一共有n/groupSize组牌，每组牌的范围是[x,x+groupSize−1]
• 遍历升序排序好后的hand，开始按照图顺序遍历

代码

public static boolean isNStraightHand(int[] hand, int groupSize) {
        int n = hand.length;
        if (n % groupSize !=0) return false;
        Arrays.sort(hand);
        Map cnt = new HashMap<>();
        for (int x:hand) {
            cnt.put(x,cnt.getOrDefault(x,0)+1);
        }
        for (int x:hand) {
            if (!cnt.containsKey(x)) continue;
            for (int j = 0; j < groupSize; j++) {
                int num = x + j;
                if (!cnt.containsKey(num)) return false;
                cnt.put(num,cnt.get(num)-1);
                if (cnt.get(num)==0)cnt.remove(num);
            }
        }
        return true;
    }

根据上面整理的思路逻辑代码就很好读懂了