专栏首页前端小书童分割数组为连续子序列 (难度:中等) - Day20201204

分割数组为连续子序列 (难度:中等) - Day20201204

20201204

题目:

给你一个按升序排序的整数数组 num(可能包含重复数字),请你将它们分割成一个或多个子序列,其中每个子序列都由连续整数组成且长度至少为 3 。

如果可以完成上述分割,则返回 true ;否则,返回 false 。

示例:

  1. 示例 1:
输入: [1,2,3,3,4,5]
输出: True
解释:
你可以分割出这样两个连续子序列 :
1, 2, 3
3, 4, 5
  1. 示例 2:
输入: [1,2,3,3,4,4,5,5]
输出: True
解释:
你可以分割出这样两个连续子序列 :
1, 2, 3, 4, 5
3, 4, 5
  1. 示例 3:
输入: [1,2,3,4,4,5]
输出: False

提示:

  • 输入的数组长度范围为 [1, 10000]

抛砖引玉

思路:

贪心

抛砖引玉

从前到后遍历 nums,模拟分割子序列,对应遇到的任意元素,其可以作为新子序列的起点也可以附加到前一个子序列。

以为题目要求子序列最少要三个元素,那么保证子序列满足要求,优先将遇到的子序列附加到前一个子序列:

  1. 遍历 nums 记录每个元素出现的次数
  2. 逐个取 nums 元素 item(map 统计数量减少):
    • item 出现次数和其之后的两个元素数量均大于 0,则他们可以作为一个新子序列存在,新子序列的结尾为 item+3
    • 如果 item 是一个子序列的结尾,那么优先将其附加到上一个子序列,将其后一个元素看做子序列的结尾 item+1
    • 如果 nums 所有元素均可以按照上面逻辑分割成子序列,则返回 true,否则返回 false

注意: 在标记元素作为子序列结尾时,其可以存在也可以不存在,因为前面的序列已经满足题目要求

var isPossible = function(nums) {
    const len = nums.length
    if (len < 3) return false
    let countMap = new Map(),
        map = new Map()
    // 统计每个数字出现的次数
    for (let i = 0; i < len; i++) {
        const num = countMap.get(nums[i]) || 0
        countMap.set(nums[i], num + 1)
    }
    // 模拟分割 优先附加到先前构造的连续序列中
    for (let i = 0; i < len; i++) {
        const item = nums[i],
            // 一组三个连续数组
            num = countMap.get(item) || 0,
            next1 = countMap.get(item + 1) || 0,
            next2 = countMap.get(item + 2) || 0,
            // 动态记录元素作为子序列结束的次数
            end = map.get(item) || 0,
            endNext1 = map.get(item + 1) || 0,
            endNext2 = map.get(item + 3) || 0
        // 如果数字出现次数归零,则进行向后查找
        if (num === 0) continue
        // 遇到可以作为子序列结束的元素,将其附加到前子序列,其下一个元素代替其作为子序列的结尾
        if (end > 0) {
            map.set(item, end - 1)
            map.set(item + 1, endNext1 + 1)
        } else if (next1 > 0 && next2 > 0) {
            // 连续三个数后标记一个可能的子序列结尾
            countMap.set(item + 1, next1 - 1)
            countMap.set(item + 2, next2 - 1)
            map.set(item + 3, endNext2 + 1)
        } else {
            // 如果数组中遇到既不是子序列结尾,右不能组成新子序列的元素,则直接返回false
            return false
        }
        countMap.set(item, num - 1)
    }
    return true
}

博客: 前端小书童

每天的每日一题,写的题解会同步更新到公众号一天一大 lee 栏目 欢迎关注留言

公众号:前端小书童

本文分享自微信公众号 - 前端小书童(gaowenju_web),作者:前端小书童

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-12-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 659. 分割数组为连续子序列

    CaesarChang张旭
  • LeetCode 659. 分割数组为连续子序列(哈希)

    给你一个按升序排序的整数数组 num(可能包含重复数字),请你将它们分割成一个或多个子序列,其中每个子序列都由连续整数组成且长度至少为 3 。

    Michael阿明
  • 【一天一大 lee】将数组拆分成斐波那契序列 (难度:中等) - Day20201208

    给定一个数字字符串 S,比如 S = "123456579",我们可以将它分成斐波那契式的序列 [123, 456, 579]。

    前端小书童
  • 玩个斗地主也能玩出算法?

    读完本文,可以去力扣解决如下题目: 659. 分割数组为连续子序列(Medium)

    labuladong
  • CVPR 2019 | PointConv:在点云上高效实现卷积操作

    在机器人、自动驾驶和虚拟/增强现实应用中,直接获取 3D 数据的传感器日趋普遍。由于深度信息可以消除 2D 图像中的大量分割不确定性(segmentation ...

    机器之心
  • AAAI 2018 | 中科大提出新型连续手语识别框架LS-HAN,帮助「听」懂听障人士

    机器之心
  • ACL论文 | 深度学习大神新作,神经网络的自然语言翻译应用

    在 8月7日在德国柏林召开的2016 计算语言学(ACL)大会上,学者Thang Luong、Kyunghyun Cho 和 Christopher D. Ma...

    AI科技评论
  • 盘点互联网公司最常见的面试编程题

    互联网公司面试,笔试环节或第一面往往都是现场做编程题。很多面试的老铁反映说,败在了编程题上,去不了自己心仪的公司,拿不到想要的待遇。

    不可言诉的深渊
  • 盘点互联网公司最常见的面试编程题

    互联网公司面试,笔试环节或第一面往往都是现场做编程题。很多面试的老铁反映说,败在了编程题上,去不了自己心仪的公司,拿不到想要的待遇。

    石晓文
  • 盘点互联网公司最常见的面试编程题

    互联网公司面试,笔试环节或第一面往往都是现场做编程题。很多面试的老铁反映说,败在了编程题上,去不了自己心仪的公司,拿不到想要的待遇。

    double
  • 【图形学】贝塞尔与B样条曲线曲面笔记

    这篇文章是看中国农大的图形学公开课的笔记, 简单介绍了贝塞尔Bezier曲线曲面和B样条B-Spline曲线曲面, 希望能够带来一个大概视角和总览. 本文同步存...

    ZifengHuang
  • 大牛讲堂 | 深度学习Sequence Learning技术分享

    雷锋网按:本文作者都大龙,2011年7月毕业于中科院计算技术研究所;曾任百度深度学习研究院(IDL)资深研发工程师,并连续两次获得百度最高奖—百万美金大奖;现在...

    AI科技评论
  • MADlib——基于SQL的数据挖掘解决方案(24)——分类之决策树

    决策树(Decision Tree)又称为分类树(Classification Tree),是最为广泛的归纳推理算法之一,处理类别型或连续型变量...

    用户1148526
  • 腾讯优图×厦大联队夺冠全球AI医疗大赛!刷新肝脏肿瘤影像分割世界纪录

    近日,全球LiTS (Liver Tumor Segmentation Challenge,肝脏肿瘤病灶区CT影像分割挑战)世界记录再次被刷新,腾讯旗下顶级AI...

    量子位
  • PointNet:三维点云分割与分类的深度学习

    本文是关于PointNet点云深度学习的翻译与理解,PointNet是一种直接处理点云的新型神经网络,它很好地体现了输入点云的序列不变性。

    点云PCL博主
  • Radiology:颞叶癫痫对侧脑区的术前fMRI脑网络整合情况与术后结果的关系

    请点击上面“思影科技”四个字,选择关注作者,思影科技专注于脑影像数据处理,涵盖(fMRI,结构像,DTI,ASL,EEG/ERP,FNIRS,眼动)等,希望专业...

    用户1279583
  • 图像分割综述

    这一大部分我们将要介绍的是深度学习大火之前人们利用数字图像处理、拓扑学、数学等方面的只是来进行图像分割的方法。当然现在随着算力的增加以及深度学习的不断发展,一些...

    用户1150922
  • CVPR 2020 | RandLA-Net:大场景三维点云语义分割新框架(已开源)

    本文要介绍的是 CVPR 2020上被录用的文章《RandLA-Net: Efficient Semantic Segmentation of Large-Sc...

    AI科技评论
  • 快速排序(基础版)

    用户1260737

扫码关注云+社区

领取腾讯云代金券