G面经prepare: X-Straight - neverlandly - 博客园

G面经prepare: X-Straight - neverlandly - 博客园
Define "X-Straight" as X cards with consecutive numbers (X >= 3). Determine if the deck can be fully divided into sets of "X-Straight". Example: 1, 2, 3, 4, 4, 5, 6 -> True

 5     HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
 6     public boolean determine(int[] arr) {
 7         for (int elem : arr) {
 8             if (!map.containsKey(elem)) {
 9                 map.put(elem, 1);
10             }
11             else map.put(elem, map.get(elem)+1);
12         }
13         return helper(arr, 0);
14     }
15     
16     public boolean helper(int[] arr, int pos) {
17         if (pos == arr.length) return true;
18         int cur = arr[pos];
19         for (int k=3; k<map.keySet().size(); k++) {
20             HashMap<Integer, Integer> copy = new HashMap<Integer, Integer>(map);
21             for (int i=cur; i<cur+k; i++) {
22                 if (!map.containsKey(i)) return false;
23                 if (map.get(i) == 0) return false;
24                 map.put(i, map.get(i)-1);
25             }
26             while (pos<arr.length && map.get(arr[pos]) == 0) pos++;
27             if (helper(arr, pos))
28                 return true;
29             map = copy; //?
30         }
31         return false;
32         
33     }

Read full article from G面经prepare: X-Straight - neverlandly - 博客园