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:
给一个升序排列的整数数(可能含有重复元素)，把这个数组拆分成几个至少含有3个整数的子序列，求是否可以拆分成功？（也就是能够全部拆分组成顺子）
解法：贪婪算法Greedy
Java:
public boolean isPossible(int[] nums) {
Map<Integer, Integer> freq = new HashMap<>(), appendfreq = new HashMap<>();
for (int i : nums) freq.put(i, freq.getOrDefault(i,0) + 1);
for (int i : nums) {
if (freq.get(i) == 0) continue;
else if (appendfreq.getOrDefault(i,0) > 0) {
appendfreq.put(i, appendfreq.get(i) - 1);
appendfreq.put(i+1, appendfreq.getOrDefault(i+1,0) + 1);
}
else if (freq.getOrDefault(i+1,0) > 0 && freq.getOrDefault(i+2,0) > 0) {
freq.put(i+1, freq.get(i+1) - 1);
freq.put(i+2, freq.get(i+2) - 1);
appendfreq.put(i+3, appendfreq.getOrDefault(i+3,0) + 1);
}
else return false;
freq.put(i, freq.get(i) - 1);
}
return true;
}
Python:
# Time: O(n)
# Space: O(1)
class Solution(object):
def isPossible(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
pre, cur = float("-inf"), 0
cnt1, cnt2, cnt3 = 0, 0, 0
i = 0
while i < len(nums):
cnt = 0
cur = nums[i]
while i < len(nums) and cur == nums[i]:
cnt += 1
i += 1
if cur != pre + 1:
if cnt1 != 0 or cnt2 != 0:
return False
cnt1, cnt2, cnt3 = cnt, 0, 0
else:
if cnt < cnt1 + cnt2:
return False
cnt1, cnt2, cnt3 = max(0, cnt - (cnt1 + cnt2 + cnt3)), cnt1, cnt2 + min(cnt3, cnt - (cnt1 + cnt2))
pre = cur
return cnt1 == 0 and cnt2 == 0
Python:
def isPossible(self, nums):
left = collections.Counter(nums)
end = collections.Counter()
for i in nums:
if not left[i]: continue
left[i] -= 1
if end[i - 1] > 0:
end[i - 1] -= 1
end[i] += 1
elif left[i + 1] and left[i + 2]:
left[i + 1] -= 1
left[i + 2] -= 1
end[i + 2] += 1
else:
return False
return True
C++:
class Solution {
public:
bool isPossible(vector<int>& nums)
{
unordered_map<int, priority_queue<int, vector<int>, std::greater<int>>> backs;
// Keep track of the number of sequences with size < 3
int need_more = 0;
for (int num : nums)
{
if (! backs[num - 1].empty())
{ // There exists a sequence that ends in num-1
// Append ‘num‘ to this sequence
// Remove the existing sequence
// Add a new sequence ending in ‘num‘ with size incremented by 1
int count = backs[num - 1].top();
backs[num - 1].pop();
backs[num].push(++count);
if (count == 3)
need_more--;
}
else
{ // There is no sequence that ends in num-1
// Create a new sequence with size 1 that ends with ‘num‘
backs[num].push(1);
need_more++;
}
}
return need_more == 0;
}
};
C++:
class Solution {
public:
bool isPossible(vector<int>& nums) {
unordered_map<int, int> freq, need;
for (int num : nums) ++freq[num];
for (int num : nums) {
if (freq[num] == 0) continue;
else if (need[num] > 0) {
--need[num];
++need[num + 1];
} else if (freq[num + 1] > 0 && freq[num + 2] > 0) {
--freq[num + 1];
--freq[num + 2];
++need[num + 3];
} else return false;
--freq[num];
}
return true;
}
};
[LeetCode] 659. Split Array into Consecutive Subsequences 将数组分割成连续子序列
原文：https://www.cnblogs.com/lightwindy/p/9808139.html