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:

  1. The length of the input is in range of [1, 10000]

题目分类应属于  模拟。

题目大意,将一升序的数组,分割多个成长度大于等于3的连续的序列,问能不能分割成功。

开始的想法是,第一遍扫一下,依次枚举3个连续的数作为一个分割,并记录每个分割最后的一个数(为后期拓展所用)。

第二次扫描,看剩下的数能不能放到任何一个分割的后面。如果能,那么更新分割的最后一个值。

第三次扫描,看还有没有剩下的数字,如果没有那么返回true,否则false

看似天一无缝,却始终过不了倒数第二个测试例子------>               179 / 180 test cases passed.

手写了一个样例  [1,2,3,4,5,5,5,6,6,7,7,8,9,10]

在处理的时候,按照上上面的套路(1,2,3)(4,5,6),(5,6,7),(7,8,9) 剩下 5和10,   5,和10 只能放在 3,6,7,9后面,10可以放在9后面,但是5没有地方放,返回false。

可是 我们肉眼能找到(1,2,3,4,5)(5,6,7)(5,6,7)(8,9,10)这样合法的分割,应该返回true。思路有瑕疵。其实我们思考的顺序有错误,对于当前的数字x,我们应该先判断x-1是否存在,如果存在就直接放上就好了,不存在的时候再构建一个长度为3个分割,如果长度为3的分割都构建不了,那么直接返回false就ok了。说道这里,这题目还是有贪心的味道的....

这里mp2[y]记录以y作为i分割末尾的数量。

class Solution {
public:
bool isPossible(vector<int>& nums) {
int n = nums.size();
//sort(nums.begin(), nums.end());
if (n < ) return false;
map<int, int>mp;
for (int i = ; i < n; ++i) mp[nums[i]]++; map<int, int>mp2;
for (int i = ; i < n; ++i) {
int x = nums[i];
if (mp[x] <= ) continue;
if (mp2[x-] > ) {
mp2[x]++, mp2[x-]--, mp[x]--;
} else if (mp[x+] > && mp[x+] > ) {
mp[x]--, mp[x+]--, mp[x+]--;
mp2[x+]++;
} else {
return false;
}
}
return true;
}
};
05-06 14:53
查看更多