https://leetcode.com/problems/split-array-into-consecutive-subsequences/
For each element,
To all who are confused why we should put 'append existed split' part before 'create a new split' part. Generally, this is followed by a strict mathematics proof but intuitively you can think in this way. Given example '1 2 3 3 4 4 5 5' the greedy way to handle this is by appending '1 2 3' with '4 5' and what's left is '3 4 5' then we're done. However, if you stop by '1 2 3' and when you see the second '3' you create a new split that is '3 4 5' then we fail ('4 5' are left). This example illustrates why you should adopt 'append' strategy first. Is there any example we should stop immediately when we have three numbers in a split? Yes, given '1 2 3 3 4 5', you might not scan till the end to format '1 2 3 4 5', otherwise '3' will be alone. However, our strategy also works in some way. Once it reaches the second '3' it will automatically add '4' to
https://leetcode.com/problems/split-array-into-consecutive-subsequences/discuss/106496/Java-O(n)-Time-O(n)-Space
http://www.cnblogs.com/grandyang/p/7525821.html
博主第一眼看到这题，心想，我去，这不就是打牌么，什么挖坑，拐3，红桃4啊，3个起连，有时候排组合的好，就不用划单儿。这道题让我们将数组分割成多个连续递增的子序列，注意这里可能会产生歧义，实际上应该是分割成一个或多个连续递增的子序列，因为[1,2,3,4,5]也是正确的解。这道题就用贪婪解法就可以了，我们使用两个哈希表map，第一个map用来建立数字和其出现次数之间的映射freq，第二个用来建立可以加在某个连续子序列后的数字及其可以出现的次数之间的映射need。对于第二个map，举个例子来说，就是假如有个连，[1,2,3]，那么后面可以加上4，所以就建立4的映射。这样我们首先遍历一遍数组，统计每个数字出现的频率，然后我们开始遍历数组，对于每个遍历到的数字，首先看其当前出现的次数，如果为0，则继续循环；如果need中存在这个数字的非0映射，那么表示当前的数字可以加到某个连的末尾，我们将当前数字的映射值自减1，然后将下一个连续数字的映射值加1，因为当[1,2,3]连上4后变成[1,2,3,4]之后，就可以连上5了；如果不能连到其他子序列后面，我们来看其是否可以成为新的子序列的起点，可以通过看后面两个数字的映射值是否大于0，都大于0的话，说明可以组成3连儿，于是将后面两个数字的映射值都自减1，还有由于组成了3连儿，在need中将末尾的下一位数字的映射值自增1；如果上面情况都不满足，说明该数字是单牌，只能划单儿，直接返回false。最后别忘了将当前数字的freq映射值自减1。退出for循环后返回true
X. https://leetcode.com/problems/split-array-into-consecutive-subsequences/discuss/106495/java-on-time-o1-space-solution-greedily-extending-shorter-subsequence
http://blog.csdn.net/u014688145/article/details/77148515
public boolean isPossible(int[] nums) { TreeMap<Integer, Integer> map = new TreeMap<>(); Map<Integer, Integer> append = new HashMap<>(); for (int num : nums) map.put(num, map.getOrDefault(num, 0) + 1); for (int i : nums){ if (map.get(i) == 0) continue; if (append.getOrDefault(i, 0) > 0){ // 先拼接 append.put(i, append.get(i) - 1); append.put(i + 1, append.getOrDefault(i + 1, 0) + 1); } else if (map.getOrDefault(i + 1, 0) > 0 && map.getOrDefault(i + 2, 0) > 0){ // 再独立 map.put(i + 1, map.get(i + 1) - 1); map.put(i + 2, map.get(i + 2) - 1); append.put(i + 3, append.getOrDefault(i + 3, 0) + 1); } else return false; map.put(i, map.get(i) - 1); } return true; }
X. http://blog.jerkybible.com/2017/08/19/LeetCode-659-Split-Array-into-Consecutive-Subsequences/
You are given an integer array sorted in ascending order (may contain duplicates), you need to split them into several subsequences, where each subsequences consist of at least 3 consecutive integers. Return whether you can make such a split.
Example 1:
Input: [1,2,3,3,4,5] Output: True Explanation: You can split them into two consecutive subsequences : 1, 2, 3 3, 4, 5
Example 2:
Input: [1,2,3,3,4,4,5,5] Output: True Explanation: You can split them into two consecutive subsequences : 1, 2, 3, 4, 5 3, 4, 5
Example 3:
Input: [1,2,3,4,4,5] Output: False
Note:
- The length of the input is in range of [1, 10000]
For each element,
1. It could append to an existing subsequence OR 2. It could be the start of a new subsequence. Otherwise, return false.To all who are confused why we should put 'append existed split' part before 'create a new split' part. Generally, this is followed by a strict mathematics proof but intuitively you can think in this way. Given example '1 2 3 3 4 4 5 5' the greedy way to handle this is by appending '1 2 3' with '4 5' and what's left is '3 4 5' then we're done. However, if you stop by '1 2 3' and when you see the second '3' you create a new split that is '3 4 5' then we fail ('4 5' are left). This example illustrates why you should adopt 'append' strategy first. Is there any example we should stop immediately when we have three numbers in a split? Yes, given '1 2 3 3 4 5', you might not scan till the end to format '1 2 3 4 5', otherwise '3' will be alone. However, our strategy also works in some way. Once it reaches the second '3' it will automatically add '4' to
apendfreq which means we've already finished '1 2 3' and let's start a new split.- We iterate through the array once to get the frequency of all the elements in the array
- We iterate through the array once more and for each element we either see if it can be appended to a previously constructed consecutive sequence or if it can be the start of a new consecutive sequence. If neither are true, then we return false.
Call a chain a sequence of 3 or more consecutive numbers.
Considering numbers
x from left to right, if x can be added to a current chain, it's at least as good to add x to that chain first, rather than to start a new chain.
Why? If we started with numbers
x and greater from the beginning, the shorter chains starting from x could be concatenated with the chains ending before x, possibly helping us if there was a "chain" from x that was only length 1 or 2.
Algorithm
Say we have a count of each number, and let
tails[x] be the number of chains ending right before x.
Now let's process each number. If there's a chain ending before
x, then add it to that chain. Otherwise, if we can start a new chain, do so.
It's worth noting that our solution can be amended to take only additional space, since we could do our counts similar to Approach #1, and we only need to know the last 3 counts at a time.
- Time Complexity: , where is the length of
nums. We iterate over the array. - Space Complexity: , the size of
countandtails.
public boolean isPossible(int[] nums) {
Counter count = new Counter();
Counter tails = new Counter();
for (int x : nums)
count.add(x, 1);
for (int x : nums) {
if (count.get(x) == 0) {
continue;
} else if (tails.get(x) > 0) {
tails.add(x, -1);
tails.add(x + 1, 1);
} else if (count.get(x + 1) > 0 && count.get(x + 2) > 0) {
count.add(x + 1, -1);
count.add(x + 2, -1);
tails.add(x + 3, 1);
} else {
return false;
}
count.add(x, -1);
}
return true;
}
}
class Counter extends HashMap<Integer, Integer> {
public int get(int k) {
return containsKey(k) ? super.get(k) : 0;
}
public void add(int k, int v) {
put(k, get(k) + v);
}
http://www.cnblogs.com/grandyang/p/7525821.html
博主第一眼看到这题，心想，我去，这不就是打牌么，什么挖坑，拐3，红桃4啊，3个起连，有时候排组合的好，就不用划单儿。这道题让我们将数组分割成多个连续递增的子序列，注意这里可能会产生歧义，实际上应该是分割成一个或多个连续递增的子序列，因为[1,2,3,4,5]也是正确的解。这道题就用贪婪解法就可以了，我们使用两个哈希表map，第一个map用来建立数字和其出现次数之间的映射freq，第二个用来建立可以加在某个连续子序列后的数字及其可以出现的次数之间的映射need。对于第二个map，举个例子来说，就是假如有个连，[1,2,3]，那么后面可以加上4，所以就建立4的映射。这样我们首先遍历一遍数组，统计每个数字出现的频率，然后我们开始遍历数组，对于每个遍历到的数字，首先看其当前出现的次数，如果为0，则继续循环；如果need中存在这个数字的非0映射，那么表示当前的数字可以加到某个连的末尾，我们将当前数字的映射值自减1，然后将下一个连续数字的映射值加1，因为当[1,2,3]连上4后变成[1,2,3,4]之后，就可以连上5了；如果不能连到其他子序列后面，我们来看其是否可以成为新的子序列的起点，可以通过看后面两个数字的映射值是否大于0，都大于0的话，说明可以组成3连儿，于是将后面两个数字的映射值都自减1，还有由于组成了3连儿，在need中将末尾的下一位数字的映射值自增1；如果上面情况都不满足，说明该数字是单牌，只能划单儿，直接返回false。最后别忘了将当前数字的freq映射值自减1。退出for循环后返回true
X. https://leetcode.com/problems/split-array-into-consecutive-subsequences/discuss/106495/java-on-time-o1-space-solution-greedily-extending-shorter-subsequence
The basic idea is that, for each distinct element
ele in the input array, we only need to maintain three pieces of information: the number of consecutive subsequences ending at ele with length of 1, length of 2 and length >= 3.
The input array will be scanned linearly from left to right. Let
cur be the element currently being examined and cnt as its number of appearance. pre is the element processed immediately before cur. The number of consecutive subsequences ending at pre with length of 1, length of 2 and length >= 3 are denoted as p1, p2 and p3, respectively. There are two cases in general:cur != pre + 1: for this case,curcannot be added to any consecutive subsequences ending atpre, therefore, we must havep1 == 0 && p2 == 0; otherwise the input array cannot be split into consecutive subsequences of length>= 3. Now letc1, c2, c3be the number of consecutive subsequences ending atcurwith length of1, length of2and length>= 3, respectively, we will havec1 = cnt, c2 = 0, c3 = 0, which means we only have consecutive subsequence ending atcurwith length of1and its number given bycnt.cur == pre + 1: for this case,curcan be added to consecutive subsequences ending atpreand thus extend those subsequences. But priorities should be given to those with length of1first, then length of2and lastly length>= 3. Also we must havecnt >= p1 + p2; otherwise the input array cannot be split into consecutive subsequences of length>= 3. Again letc1, c2, c3be the number of consecutive subsequences ending atcurwith length of1, length of2and length>= 3, respectively, we will have:c2 = p1, c3 = p2 + min(p3, cnt - (p1 + p2)), c1 = max(cnt - (p1 + p2 + p3), 0). The meaning is as follows: first addingcurto the end of subsequences of length1will make them subsequences of length2, and we havep1such subsequences, thereforec2 = p1. Then addingcurto the end of subsequences of length2will make them subsequences of length3, and we havep2such subsequences, thereforec3is at leastp2. Ifcnt > p1 + p2, we can add the remainingcurto the end of subsequences of length>= 3to make them even longer subsequences. The number of such subsequences is the smaller one ofp3andcnt - (p1 + p2). In total,c3 = p2 + min(p3, cnt - (p1 + p2)). Ifcnt > p1 + p2 + p3, then we still have remainingcurthat cannot be added to any subsequences. These residuecurwill form subsequences of length1, hencec1 = max(cnt - (p1 + p2 + p3), 0).
For either case, we need to update:
pre = cur, p1 = c1, p2 = c2, p3 = c3 after processing the current element. When all the elements are done, we check the values of p1 and p2. The input array can be split into consecutive subsequences of length >= 3 if and only if p1 == 0 && p2 == 0.
Here is the
O(n) time and O(1) space Java solution:public boolean isPossible(int[] nums) {
int pre = Integer.MIN_VALUE, p1 = 0, p2 = 0, p3 = 0;
int cur = 0, cnt = 0, c1 = 0, c2 = 0, c3 = 0;
for (int i = 0; i < nums.length; pre = cur, p1 = c1, p2 = c2, p3 = c3) {
for (cur = nums[i], cnt = 0; i < nums.length && cur == nums[i]; cnt++, i++);
if (cur != pre + 1) {
if (p1 != 0 || p2 != 0) return false;
c1 = cnt; c2 = 0; c3 = 0;
} else {
if (cnt < p1 + p2) return false;
c1 = Math.max(0, cnt - (p1 + p2 + p3));
c2 = p1;
c3 = p2 + Math.min(p3, cnt - (p1 + p2));
}
}
return (p1 == 0 && p2 == 0);
}
PS: in case you're curious, here is how I come up with this solution.
First note that if the array can be split into consecutive subsequences of length
>= 3, then every element in the array must belong to such a subsequence of length >= 3. So let's take any integer m in the array as an example. Apparently you can only add it to consecutive subsequences ending at m - 1. This tells you that we need information about consecutive subsequences ending at m - 1. But what kind of information about those subsequences are relevant here?
Think about what distinguishes one subsequence from another. Since all the subsequences are ending at
m - 1, they can only differ by length, i.e., each subsequence will be uniquely identified by its length. Now what if two subsequences have the same length? This suggests that we also need to keep track of the number of appearance of each length. Therefore in summary, we need to maintain information of subsequences ending at m - 1 with various lengths and their corresponding number of appearance.
Of course I know we cannot keep track of all lengths, as this would require an infinite amount of memory. So the next question is to ponder more carefully the role that the length of each subsequence is playing here. From the point view of
m - 1, we care more about subsequences of length 1 and 2. Since if there are no other elements that can extend these subsequences, we know the input array cannot be split into consecutive subsequences of length >= 3. On the other hand, we don't really care about subsequences of length >= 3, since they already meet the required condition. So I conclude that for subsequences ending at m - 1, there are really only three types are needed: those of length 1, of length 2 and of length >= 3.
Once I figure this out, the next thing is to extend the conclusion to subsequences ending at
http://bookshadow.com/weblog/2017/08/13/leetcode-split-array-into-consecutive-subsequences/m, so we can have a working recurrence relation. The key here is how we add m to those subsequences ending at m - 1. As I mentioned above, priorities should be given to those of length 1 and 2, since if these subsequences cannot be extended, the input array cannot be split into consecutive subsequences of length >= 3. After those subsequences are extended, if we have more elements of m, they can be used to extend subsequences ending at m - 1 with length >= 3. At last, if we still have elements of m, then they will form subsequences of length 1 since there are no more subsequences ending at m - 1 available for them. Therefore for subsequences ending at m, we still just need subsequences of length 1, length 2 and length >= 3. We can continue in this fashion until all elements are processed, at which point we need to check the number of subsequences of length 1 and 2 that ends at the last element of the input array to see if the input array can be split into consecutive subsequences of length >= 3 (since these subsequences cannot be extended any longer as there are no more elements).
Map + PriorityQueue
思路类似于排列扑克牌，优先将数字排在长度较小的扑克牌队列后面
Map<Integer, PriorityQueue<Integer>> dmap的key为扑克牌队列的末尾，value为优先队列，存储扑克牌队列的长度
private HashMap<Integer, PriorityQueue<Integer>> dmap;
public boolean isPossible(int[] nums) {
dmap = new HashMap<>();
for (int num : nums) {
PriorityQueue<Integer> pq0 = getOrPut(num - 1);
int len = pq0.isEmpty() ? 0 : pq0.poll();
PriorityQueue<Integer> pq1 = getOrPut(num);
pq1.offer(len + 1);
}
for (int key : dmap.keySet()) {
for (int len : dmap.get(key)) {
if (len < 3) return false;
}
}
return true;
}
public PriorityQueue<Integer> getOrPut(int num) {
PriorityQueue<Integer> pq = dmap.get(num);
if (pq == null) {
pq = new PriorityQueue<Integer>();
dmap.put(num, pq);
}
return pq;
}http://blog.csdn.net/u014688145/article/details/77148515
思路总结：把每个独立的片段先求出来，接着考虑如何拼凑在一起，因为只能往前拼凑，所以解是唯一的，模拟就好了。
此题相对较难，要抓住一些性质不容易，采用模拟，模拟的策略很有意思，首先按要求求出至少三个连续序列组成的所有情况，接着就是【拼接】了。
很有意思的是，在写代码时，先考虑拼接，最后才考虑是否单独（即分桶摆放）摆放。
像此题，我的思路是从频次最大的那个数开始着手，先假设某个数num的频次最大，因此，一定会从num开始，找到num+1，和num+2，组成至少三个序列的情况，如果不存在则可以直接返回false。
那么问题来了，num+1，num+2的频次一定小于等于num，遇到不能分配的情况该怎么办？啥时候是不能分配的时候？
条件： num 还存在待分配的名额时，num+2的个数为0
所以不管num + 1是否被分配完毕，我们都需要将剩余的num 和 num + 1拼接到之前的某个桶的结尾处。
如果找不到这样的桶，同样返回false，否则拼接后，更新桶的最后一个元素。（map实现）
拼谁？一定是num，拼完num，该桶下一步就应该拼num+1的元素，此时再把num+1放进去，两步完成了num和num+1的拼接，完美。
public boolean isPossible(int[] nums) { TreeMap<Integer, Integer> map = new TreeMap<>(); Map<Integer, Integer> append = new HashMap<>(); for (int num : nums) map.put(num, map.getOrDefault(num, 0) + 1); for (int i : nums){ if (map.get(i) == 0) continue; if (append.getOrDefault(i, 0) > 0){ // 先拼接 append.put(i, append.get(i) - 1); append.put(i + 1, append.getOrDefault(i + 1, 0) + 1); } else if (map.getOrDefault(i + 1, 0) > 0 && map.getOrDefault(i + 2, 0) > 0){ // 再独立 map.put(i + 1, map.get(i + 1) - 1); map.put(i + 2, map.get(i + 2) - 1); append.put(i + 3, append.getOrDefault(i + 3, 0) + 1); } else return false; map.put(i, map.get(i) - 1); } return true; }
X. http://blog.jerkybible.com/2017/08/19/LeetCode-659-Split-Array-into-Consecutive-Subsequences/
首先进行参数的校验，只要数组为空或者数组的大小小于
3直接返回false。
然后我们进行拆分。新建一个List
A，里面包含所有拆分结果。从数组的第一个数字开始遍历：- 如果
A为空，则新建一个列表B1将这个数字放进去，然后将B1放入A中 - 如果
A不为空则遍历A中的每一个串，如果一个串的最后一个数字为当前数字减1并且这个串的大小小于3，则放入这个串中 - 如果满足最后一个数字为当前数字减1的串的大小都是大于等于3，则将这个数字放入第一个满足条件的串后
- 当这个串的最后一个数字小于当前数字减1并且串大小小于3直接返回
false，这是因为给定的数组的是有序的，那么这个串永远不会满足条件 - 如果以上都没有进行处理则新建一个列表
B2将这个数字放进去，然后将B2放入A中
最后轮询
A中的每一个列表，是否满足条件。满足返回true，不满足返回false。
|
