当前位置: 首页 > news >正文

个人练习-Leetcode-659. Split Array into Consecutive Subsequences

题目链接:https://leetcode.cn/problems/split-array-into-consecutive-subsequences/

题目大意:给出一个非递减数列nums[],判断其是否能被分割成若干个满足以下条件的子列:

  • 长度大于等于3
  • 元素严格递增且只相差1

子列的含义是:不改变元素的相对顺序,从原数列中抽取若干个元素组成新的数列。
分割的含义是:所有元素都会被分到某个子列,没有剩余。

思路:一开始的思路是,根据元素出现的次数,将其排列成若干个数列,比如在vector<vector<int>> subs中,subs[0]是仅出现一次的元素的数列;subs[1]是仅出现两次的元素的数列,以此类推。这样subs[][]就是一种对原数组的分割了,且保证了每个元素只出现一次。随后再对每个子列做调整,使其满足题意的两个条件。

长度大于等于3倒是不难解决,但要保证每个子列元素严格递增且增量为1并不容易。很难确定要从哪个子列中的哪个位置抽出哪个元素,放到另一个子列的哪个位置。似乎无法证明其可行性。

于是看了题解,原来用贪心做。不记录子列本身而是记录以x结尾的子列个数。

不过刚知道用贪心时我没有这么做,因为我的想法是:如果遍历到某个元素x,那么以x-1为结尾的子列应该是很多的,要挑选长度最短的那个子列才是最优的。于是在代码里多加了一层【以x-1为结尾的子列】的遍历(实际上这就是在记录子列本身了)。逻辑上应该没问题,然而时间超了…

这一版代码如下:

class Solution {
public:bool isPossible(vector<int>& nums) {map<int, vector<vector<int>>> endwithx;for (auto num : nums) {if (endwithx.find(num-1) == endwithx.end() || endwithx[num-1].size() == 0) {vector<int> tmp(1, num);endwithx[num].push_back(tmp);}else {vector<int> tgt;int min_len = endwithx[num-1][0].size(), min_idx = 0;for (int i = 1; i < endwithx[num-1].size(); i++) {auto sa = endwithx[num-1][i];if (sa.size() < min_len) {min_len = sa.size();min_idx = i;}}tgt = endwithx[num-1][min_idx];endwithx[num-1].erase(endwithx[num-1].begin()+min_idx, endwithx[num-1].begin()+min_idx+1);tgt.push_back(num);endwithx[num].push_back(tgt);}  }for (auto it = endwithx.begin(); it != endwithx.end(); it++) {for (auto sa : it->second) {if (sa.size() < 3)return false;}}return true;}
};

后来看了题解的写法,原来它记录的并不仅仅只是【以x-1为结尾的子列】,而是【以x-1为结尾且长度大于等于3的子列】。(这里注意因为x只会放到以x-1为结尾的子列后,因此第二个条件是都满足的)。也就是说,我的写法并不保证长度大于等于3,而是需要后面再判断(花费了更多时间)。而题解记录的就是长度大于等于3的子列,保证了合法性。

那么如何在放入时就确保子列长度大于等于3呢?答案是如果该元素x无法找到合适的子列插入时,它必须自己起头创造新的子列,那么又需要一个x+1和一个x+2。此时如果x+1x+2的剩余量不足了,直接返回false即可。否则,消耗一个x、一个x+1和一个x+2,组成新的一个【以x+2为结尾的子列】,显然这个子列是合法的。

完整代码

class Solution {
public:bool isPossible(vector<int>& nums) {map<int, int> cnt;map<int, int> endwithx;for (auto num : nums) {if (cnt.find(num) == cnt.end())cnt[num] = 1;else    cnt[num]++;}for (auto num : nums) {if (cnt[num]) {if (endwithx.find(num-1) == endwithx.end() || endwithx[num-1] == 0) {// create an new array starting with num, num+1, num+2if (cnt[num+1] && cnt[num+2]) {cnt[num]--;cnt[num+1]--;cnt[num+2]--;if (endwithx.find(num+2) == endwithx.end())endwithx[num+2] = 1;elseendwithx[num+2]++;       }elsereturn false;}else {cnt[num]--;endwithx[num-1]--;endwithx[num]++;}}}return true;}
};

相关文章:

个人练习-Leetcode-659. Split Array into Consecutive Subsequences

题目链接&#xff1a;https://leetcode.cn/problems/split-array-into-consecutive-subsequences/ 题目大意&#xff1a;给出一个非递减数列nums[]&#xff0c;判断其是否能被分割成若干个满足以下条件的子列&#xff1a; 长度大于等于3元素严格递增且只相差1 子列的含义是&…...

OTA升级差分包签名

制作差分包时添加-k <key_path>参数 ./build/tools/releasetools/ota_from_target_files -k <key_path> -i old.zip new.zip update.zip<key_path>如何取值&#xff1f;查看ProjectConfig.mk 如果MTK_SIGNATURE_CUSTOMIZATIONyes并且MTK_INTERNALno&#xf…...

使用Buildroot制作根文件系统

寒暄几句 学习了uboot、内核、busybox根文件系统&#xff0c;想着做一个音频播放器。最后发现好像busybox好像没有带aplay架构&#xff0c;这就很麻烦需要自己移植。为了简便我就找大佬沟通了一下&#xff0c;大佬推荐了Buildroot工具来制作根文件系统。 平台 开发板&#x…...

Java_Spring:5. 基于注解的 IOC 配置

目录 1 环境搭建 1.1 第一步&#xff1a;拷贝必备 jar 包到工程的 lib 目录。 1.2 第二步&#xff1a;使用Component 注解配置管理的资源 1.3 第三步&#xff1a;创建 spring 的 xml 配置文件并开启对注解的支持 2 常用注解 2.1 用于创建对象的注解 2.1.1 Component 2.1…...

Git下的.gitignore文件

.gitignore .gitignore是一个文件&#xff0c;这个文件用来指定哪些文件提交到 git 管理&#xff0c;也就是 git commit 不会提交这些文件 .gitignore文件的语法 注释 "#" 表示注释 # 注释 忽略指定文件/文件夹 直接写入文件或文件夹名即可&#xff0c;指定文…...

Unity集成GPT

GPT想必是最近互联网最火的话题了&#xff0c;作为一个Unity开发者&#xff0c;今天来介绍一下如何在Unity中使用GPT。 一、API 密钥 使用GPT的API首先要获得密钥&#xff0c;如下进入OpenAI官网(https://platform.openai.com/account/api-keys)–>选择自己的账号–>查…...

Xilinx FPGA Multiboot设计与实现(Spartan-6和Kintex-7为例)

文章目录 1. FPGA固件升级方案2. Golden镜像和Multiboot镜像简介3. ISE环境下实现(XC6SLX9)4. Vivado环境下实现(XC7K325T)5. Golden镜像Header分析6. 参考资料7. 示例工程ISE、Vivado、MicroBlaze系列教程 1. FPGA固件升级方案 FPGA的硬件可编程性给设计带来了很高的灵活…...

14、SpringMVC执行流程

文章目录14、SpringMVC执行流程14.1、SpringMVC常用组件1 DispatcherServlet&#xff08;前端控制器&#xff09;2 HandlerMapping&#xff08;处理器映射器&#xff09;3 Handler&#xff08;处理器&#xff09;4 HandlerAdapter&#xff08;处理器适配器&#xff09;5 ViewRe…...

2步搞定拼版!AD通用拼版技巧分享!

你是不是也看过很多拼版教程&#xff0c;一整篇文章全部都是文字说明和各种图示&#xff0c;照着一步步去做&#xff0c;都需要一些时间才能勉强搞定。 之前我用过AD20的自带拼版工具&#xff0c;功能上比较简单&#xff0c;而且菜单没有全部汉化&#xff0c;对于新手来说&…...

再学C语言47:字符串输出

C中有3个用于输出字符串的标准库函数&#xff1a;puts()&#xff0c;fputs()&#xff0c;printf() 一、puts()函数 示例代码&#xff1a; /* test of puts() function */ #include <stdio.h>#define ARR_T "I am an array."int main(void) {char str1[100] …...

银行数字化转型导师坚鹏:如何制定银行数字化转型年度培训规划

如何制定银行数字化转型年度培训规划 ——以推动银行数字化转型战略落地为核心&#xff0c;实现知行果合一课程背景&#xff1a; 很多银行都在开展银行数字化转型培训工作&#xff0c;目前存在以下问题急需解决&#xff1a;缺少针对性的银行数字化转型年度培训规划不清楚如…...

RFID技术在物流行业中的应用:优化物流流程,提高效率

随着物流行业的不断发展&#xff0c;如何优化物流流程、提高效率成为了每个物流从业者关注的重点。RFID技术作为一种先进的自动识别技术&#xff0c;正逐渐被广泛应用于物流行业&#xff0c;帮助企业降低成本、提高运营效率。本文将重点介绍RFID技术在物流行业中的应用&#xf…...

安卓机器学习框架学习:Android Neural Networks API (NNAPI)

Android Neural Networks API (NNAPI) 简介&#xff1a; 1、Android Neural Networks API (NNAPI) 是一个 Android C API&#xff0c;在 Android 设备上实现机器学习&#xff1b; 2、NNAPI 旨在为更高层级的机器学习框架&#xff08;如 TensorFlow Lite 和 Caffe2&#xff09…...

阿里云GPU服务器收费标准、学生价格及一个小时费用大全

阿里云GPU租用费用价格表&#xff0c;GPU计算卡包括NVIDIA V100计算卡、T4计算卡、A10计算卡和A100计算卡&#xff0c;GPU云服务器gn6i可享受3折优惠&#xff0c;阿里云百科分享阿里云GPU服务器学生优惠价格、GPU服务器收费价格表、GPU服务器多少钱一个小时等费用明细表&#x…...

Asp.net core 依赖注入 (带案例以及注释理解)

1.很多朋友不知道什么是依赖注入&#xff0c;接下来我用比较通俗易懂的话语 来帮助大家理解 依赖注入&#xff08;Dependency Injection&#xff0c;简称DI&#xff09;是一种设计模式&#xff0c;用于减少组件之间的耦合度。它的核心思想是&#xff0c;将组件之间的依赖关系从…...

【微信小程序】-- uni-app 项目-- 购物车 -- 首页 - 轮播图效果(五十二)

&#x1f48c; 所属专栏&#xff1a;【微信小程序开发教程】 &#x1f600; 作  者&#xff1a;我是夜阑的狗&#x1f436; &#x1f680; 个人简介&#xff1a;一个正在努力学技术的CV工程师&#xff0c;专注基础和实战分享 &#xff0c;欢迎咨询&#xff01; &…...

GO实现Redis:GO实现Redis集群(5)

采用一致性hash算法将key分散到不同的节点&#xff0c;客户端可以连接到集群中任意一个节点https://github.com/csgopher/go-redis本文涉及以下文件&#xff1a; consistenthash&#xff1a;实现添加和选择节点方法 standalone_database&#xff1a;单机database client&#x…...

高阶数据结构之 B树 B+树 B*树

文章目录B树B树节点的设计插入key的过程B树的验证B树的性能分析B树和B*树B树B*树总结B树、B树、B*树B树的应用做索引MySQL索引MyISAMInnoDBB树 在前面几章中我们介绍了AVL树和红黑树&#xff0c;简单复习一下&#xff0c;我们说到原本的二叉搜索树会存在缺陷&#xff08;不能保…...

CSS3之动画属性

系列文章目录 前端系列文章——传送门 CSS系列文章——传送门 文章目录系列文章目录CSS3 中的动画第一步&#xff1a;定义一个动画第二步&#xff1a;执行这个动画第三步&#xff1a;暂停或启动这个动画过渡和动画的区别CSS3 中的动画 CSS3 动画是使元素从一种样式逐渐变化为…...

python --Matplotlib详解

安装 pip install matplotlib导包 import matplotlib.pyplot as plt绘制散点图 如果输入的是两个列表&#xff0c;一个表示 x 轴的值&#xff0c;一个表示 y 轴的值&#xff0c;那么就可以在直角坐标系中划出很多个点&#xff0c;然后将这些点用指定的线段连接起来就得到了散…...

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)

更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...

Device Mapper 机制

Device Mapper 机制详解 Device Mapper&#xff08;简称 DM&#xff09;是 Linux 内核中的一套通用块设备映射框架&#xff0c;为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程&#xff0c;并配以详细的…...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...

IP如何挑?2025年海外专线IP如何购买?

你花了时间和预算买了IP&#xff0c;结果IP质量不佳&#xff0c;项目效率低下不说&#xff0c;还可能带来莫名的网络问题&#xff0c;是不是太闹心了&#xff1f;尤其是在面对海外专线IP时&#xff0c;到底怎么才能买到适合自己的呢&#xff1f;所以&#xff0c;挑IP绝对是个技…...