版权声明:本文为博主原创文章,转载请注明出处:http://blog.jerkybible.com/2017/08/19/LeetCode-650-2-Keys-Keyboard/
题目要求
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]
题意解析
给一个数组,数组中的数字按顺序排列并且存在重复数字,需要将这个数组拆分为几个子数组。子数组的至少包含3个连续数字。返回是否可以满足这样的拆分。
解法分析
首先进行参数的校验,只要数组为空或者数组的大小小于3
直接返回false
。
然后我们进行拆分。新建一个ListA
,里面包含所有拆分结果。从数组的第一个数字开始遍历:
- 如果
A
为空,则新建一个列表B1
将这个数字放进去,然后将B1
放入A
中 - 如果
A
不为空则遍历A
中的每一个串,如果一个串的最后一个数字为当前数字减1并且这个串的大小小于3,则放入这个串中 - 如果满足最后一个数字为当前数字减1的串的大小都是大于等于3,则将这个数字放入第一个满足条件的串后
- 当这个串的最后一个数字小于当前数字减1并且串大小小于3直接返回
false
,这是因为给定的数组的是有序的,那么这个串永远不会满足条件 - 如果以上都没有进行处理则新建一个列表
B2
将这个数字放进去,然后将B2
放入A
中
最后轮询A
中的每一个列表,是否满足条件。满足返回true
,不满足返回false
。
解题代码
|
|