博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
【leetcode】659. Split Array into Consecutive Subsequences
阅读量:5741 次
发布时间:2019-06-18

本文共 1986 字,大约阅读时间需要 6 分钟。

题目如下:

解题思路:本题可以维护三个字典,dic_1保存没有组成序列的单元素,dic_2保存组成了包含两个元素的序列中的较大的元素,dic_3保存组成了包括三个或者三个以上元素的序列中的最大值。因为合法的序列至少要三个元素,解题的关键是要使得dic_2和dic_1的元素尽快满足条件。对于任意一个还没有加入字典的元素,加入字典的优先级从高到低排序分别是dic_2 > dic_1 > dic_3,即优先匹配dic_2,接下来匹配dic_1,再就是dic_3,如果三个都不满足,说明在目前条件下市落单的元素,加入dic_1。这里需要主要的是如果匹配上了dic_2,那么会把这个序列从dic_2中移除,加入dic_3;同理匹配dic_1的话则将dic_1移除加入dic_2。

代码如下:

class Solution(object):    def isPossible(self, nums):        dic_1 = {}        dic_2 = {}        dic_3 = {}        for i in nums:            if i-1 in dic_2:                dic_2[i-1] -= 1                if dic_2[i-1] == 0:                    del dic_2[i-1]                if i in dic_3:                    dic_3[i] += 1                else:                    dic_3[i] = 1            elif i-1 in dic_1:                dic_1[i - 1] -= 1                if dic_1[i - 1] == 0:                    del dic_1[i - 1]                if i in dic_2:                    dic_2[i] += 1                else:                    dic_2[i] = 1            elif i-1 in dic_3:                dic_3[i - 1] -= 1                if dic_3[i - 1] == 0:                    del dic_3[i - 1]                if i in dic_3:                    dic_3[i] += 1                else:                    dic_3[i] = 1            else:                if i in dic_1:                    dic_1[i] += 1                else:                    dic_1[i] = 1        #print dic_1,dic_2,dic_3        for k,v in dic_1.iteritems():            if k-1 not in dic_3 or dic_3[k-1] < v:                return False            dic_3[k-1] -= v            dic_1[k] = 0            if k in dic_3:                dic_3[k] += v            else:                dic_3[k] = 1        for k,v in dic_2.iteritems():            if k-2 not in dic_3 or dic_3[k-2] < v:                return False            dic_3[k-2] -= v            dic_2[k] = 0            if k in dic_3:                dic_3[k] += v            else:                dic_3[k] = 1        return True

 

转载于:https://www.cnblogs.com/seyjs/p/9590537.html

你可能感兴趣的文章
Laravel 服务容器
查看>>
mac安装kubernetes并运行echoserver
查看>>
多页架构的前后端分离方案(webpack+express)
查看>>
算法(第4版) Chapter 1
查看>>
前端技术选型的遗憾和经验教训
查看>>
“亲切照料”下的领域驱动设计
查看>>
SRE工程师到底是做什么的?
查看>>
解读:Red Hat为什么收购Ansible
查看>>
PHP json_encode() 函数介绍
查看>>
js动态设置元素高度
查看>>
Ossim下的安全合规管理
查看>>
DelphiWebMVC框架下BPL热部署实现
查看>>
C++与MySQL的冲突
查看>>
siki学习之观察者模式笔记
查看>>
单元测试
查看>>
spring.net 继承
查看>>
ES6:模块简单解释
查看>>
JavaScript indexOf() 方法
查看>>
用Bootstrap写一份简历
查看>>
ZJU PAT 1023
查看>>