LeetCode: 659. 分割数组为连续子序列¶
1、题目描述¶
输入一个按升序排序的整数数组(可能包含重复数字),你需要将它们分割成几个子序列,其中每个子序列至少包含三个连续整数。返回你是否能做出这样的分割?
示例 1:
输入: [1,2,3,3,4,5] 输出: True 解释: 你可以分割出这样两个连续子序列 : 1, 2, 3 3, 4, 5
示例 2:
输入: [1,2,3,3,4,4,5,5] 输出: True 解释: 你可以分割出这样两个连续子序列 : 1, 2, 3, 4, 5 3, 4, 5
示例 3:
输入: [1,2,3,4,4,5] 输出: False
提示:
- 输入的数组长度范围为
[1, 10000]
2、解题思路¶
-
判断标准:如果连续序列的过程中,每个元素都能够用上,并且子序列长度至少为3,就表示满足要求,如果有不能用到的子元素,就表示不满足要求
-
判断当前元素是否能够被用到:
- 如果以前面元素为结尾的子序列存在,就将子序列结尾移到当前位置上面
- 如果不存在,就判断能够以当前元素作为子序列的开始,也就是判断后面两个连续的值是否存在
from collections import Counter, defaultdict class Solution: def isPossible(self, nums: List[int]) -> bool: if len(nums) < 3: return False num_count = Counter(nums) end_count = defaultdict(int) for num in nums: if num_count[num] == 0: continue num_count[num] -= 1 if end_count[num - 1] > 0: end_count[num - 1] -= 1 end_count[num] += 1 elif num_count[num + 1] > 0 and num_count[num + 2] > 0: num_count[num + 1] -= 1 num_count[num + 2] -= 1 end_count[num + 2] += 1 else: return False return True