HandOfStraights [source code]

public class HandOfStraights {
static
/****************************************************************************/
class Solution {
    public boolean isNStraightHand(int[] hand, int W) {
        Map<Integer, Integer> counts = new HashMap<> ();
        for (int num : hand) {
            counts.put (num, counts.getOrDefault (num, 0) + 1);
        }
        Arrays.sort (hand);
        for (int num : hand) {
            if (counts.get (num) == 0)
                continue;
            for (int i = 0; i < W; i++) {
                if (!counts.containsKey (num + i) || counts.get (num + i) == 0)
                    return false;
                counts.put (num + i, counts.get (num + i) - 1);
            }
        }
        return true;
    }
}
/****************************************************************************/

    public static void main(String[] args) {
        HandOfStraights.Solution tester = new HandOfStraights.Solution();
        int[][] inputs = {
            {1,2,3,6,2,3,4,7,8}, {3}, {1},
            {1,2,3,4,5}, {4}, {0},
            {2,1}, {2}, {1},
        };
        for (int i = 0; i < inputs.length / 3; i++) {
            System.out.println (Printer.separator ());
            int[] hand = inputs[3 * i];
            int W = inputs[3 * i + 1][0];
            boolean ans = inputs[3 * i + 2][0] != 0, output = tester.isNStraightHand (hand, W);
            System.out.printf ("[%s] and %d\n%s\n%b\n", 
                Printer.array (hand), W, Printer.wrap (output + "", output == ans ? 92 : 91), ans
            );
        }
    }
}

说是什么连续的subarray的设定, 其实最后要解决的应该是一个subseq设定的问题; 感觉又是一个最好用DP来写的?

这不是打麻将理牌吗? 怎么总是感觉这题哪里见过一样?
这题应该是可以greedy的, 因为所有的int都必须要被group起来, 所以不确定性其实并不是特别高;

感觉不难, 乱写一下;

我简单的想法是要用到counts这个思路的, 但是题目给的值域相当大, 所以int作为count这个做法肯定是被关了; 那么用Map的话, 会不会被卡overhead? 感觉有可能, 不过只能先尝试一下;

有惊无险的AC了;

UNFINISHED

uwi:6.5min

class Solution {  
    public boolean isNStraightHand(int[] hand, int W) {  
        int n = hand.length;  
        if(n % W != 0)return false;  

        Map<Integer, int[]> map = new HashMap<>();  
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(  
                10000,   
                (a, b) -> a[0] - b[0]  
                        );  

        for(int v : hand){  
            if(map.containsKey(v)){  
                map.get(v)[1]++;  
            }else{  
                int[] o = new int[]{v, 1};  
                map.put(v, o);  
                pq.add(o);  
            }  
        }  

        for(int i = 0;i < n/W;i++){  
            while(!pq.isEmpty()){  
                if(pq.peek()[1] <= 0){  
                    pq.poll();  
                }else{  
                    break;  
                }  
            }  
            int min = pq.peek()[0];  
            for(int j = 0;j < W;j++){  
                if(!map.containsKey(min+j)){  
                    return false;  
                }  
                int[] got = map.get(min+j);  
                if(got[1] == 0)return false;  
                got[1]--;  
            }  
        }  
        return true;  
    }  
}

Problem Description

Alice has a hand of cards, given as an array of integers.

Now she wants to rearrange the cards into groups so that each group is size W, and consists of W consecutive cards.

Return true if and only if she can.

Example 1:

Input: hand = [1,2,3,6,2,3,4,7,8], W = 3  
Output: true  
Explanation: Alice's hand can be rearranged as [1,2,3],[2,3,4],[6,7,8].

Example 2:

Input: hand = [1,2,3,4,5], W = 4  
Output: false  
Explanation: Alice's hand can't be rearranged into groups of 4.

Note:

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

Difficulty:Medium
Total Accepted:877
Total Submissions:2.2K
Contributor:awice