南阳建设网站制作,wordpress关闭更新,柳州网站建设 来宾市网站制作,老网站绑定新网站如何做?Every day a Leetcode
题目来源#xff1a;659. 分割数组为连续子序列
解法1#xff1a;哈希 贪心
定义两个哈希表#xff1a;
numsCount#xff1a;统计数组 nums 中各元素出现次数。tailCount#xff1a;存储以数字 i 结尾的且符合题意的连续子序列个数。
算法659. 分割数组为连续子序列
解法1哈希 贪心
定义两个哈希表
numsCount统计数组 nums 中各元素出现次数。tailCount存储以数字 i 结尾的且符合题意的连续子序列个数。
算法
先去寻找一个长度为3的连续子序列 ii1i2找到后就将 numsCount[i]numsCount[i1]numsCount[i2] 中对应数字消耗 1 个即 -1并将 tail[i2] 加 1即以 i2 结尾的子序列个数 1。如果后续发现有能够接在这个连续子序列的数字 i3则延长以 i2 为结尾的连续子序列到 i3此时消耗 numsCount[i3] 一个由于子序列已延长因此 tailCount[i2] 减 1tailCount[i3] 加 1。在不满足上面的情况下 如果 numsCount[i] 0说明这个数字已经消耗完可以不管了。如果 numsCount[i] ! 0说明这个数字多出来了且无法组成连续子序列直接返回 false。
因此只有检查到某个数时这个数未被消耗完且既不能和前面组成连续子序列也不能和后面组成连续子序列时无法分割。
关于上面 1 和 2 的优先度也就是说当遇到一个新数是新建一个长度为 3 的子序列好还是补充到原有子序列的末尾好
优先开新序列不够贪会丢失部分子序列尾的位置而这可能造成丢解。
优先补前面更贪心这种做法会覆盖优先开新序列时的尾的位置补这补这总能到补的过程中出现的尾位置也不会丢失。
代码
/** lc appleetcode.cn id659 langcpp** [659] 分割数组为连续子序列*/// lc codestart
class Solution
{
public:bool isPossible(vectorint nums){if (nums.size() 3)return false;unordered_mapint, int numsCount, tailCount;// 统计数组 nums 中各元素出现次数for (int num : nums)numsCount[num];// tailCount[i] 表示以 i 结尾的符合条件的子序列个数for (int num : nums){if (numsCount[num] 0)continue;else if (numsCount[num] 0 tailCount[num - 1] 0){// 1. 补充到已有子序列的尾部numsCount[num] - 1;tailCount[num - 1] - 1;tailCount[num] 1;}else if (numsCount[num] 0 numsCount[num 1] 0 numsCount[num 2] 0){// 2. 新建一条长度为 3 的子序列// 注意 1 的优先级比 2 高numsCount[num] - 1;numsCount[num 1] - 1;numsCount[num 2] - 1;tailCount[num 2] 1;}elsereturn false;}return true;}
};
// lc codeend结果 复杂度分析
时间复杂度O(n)其中 n 是数组 nums 的长度。
空间复杂度O(n)其中 n 是数组 nums 的长度。
