当前位置:网站首页>leetcode:1562. 查找大小为 M 的最新分组【模拟 + 端点记录 + 范围合并】
leetcode:1562. 查找大小为 M 的最新分组【模拟 + 端点记录 + 范围合并】
2022-08-01 00:55:00 【白速龙王的回眸】
分析
建立数字points
每个元素代表的是第几个位置的含1的连续段的开头和结尾
然后每加入一个新的相当于从0变1,考虑和左边和右边的合并
可能会剪掉两个合理的块
以及可能会加上一个合理的块
最后如果存在M的1块,可以计入结果
最后更新两个端点的left和right即可
因为中间的不可能再被用到~
ac code
class Solution:
def findLatestStep(self, arr: List[int], m: int) -> int:
# 模拟
n = len(arr)
# fuck[i]表示包含i在内的连续1的最左侧和最右侧
# [1..n]
fuck = [(-1, -1) for _ in range(n + 1)]
cntM = 0
ans = -1
for i in range(n):
# 初次来到
left = right = arr[i]
# 左侧1合并
if arr[i] >= 1 and fuck[arr[i] - 1][1] != -1:
# 更新left
left = fuck[arr[i] - 1][0]
# 更新cntM
if fuck[arr[i] - 1][1] - fuck[arr[i] - 1][0] + 1 == m:
cntM -= 1
# 右侧1合并
if arr[i] < n and fuck[arr[i] + 1][0] != -1:
# 更新right
right = fuck[arr[i] + 1][1]
# 更新cntM
if fuck[arr[i] + 1][1] - fuck[arr[i] + 1][0] + 1 == m:
cntM -= 1
if right - left + 1 == m:
cntM += 1
if cntM > 0:
ans = i + 1
fuck[left] = fuck[right] = (left, right)
return ans
总结
强悍模拟 + 端点记录 + 区间范围合并大法
边栏推荐
猜你喜欢
Blueprint: Yang Hui's Triangular Arrangement
声称AI存在意识,谷歌工程师遭解雇:违反保密协议
现代企业架构框架1
Carefully organize 16 MySQL usage specifications to reduce problems by 80% and recommend sharing with the team
[Reading Notes -> Data Analysis] 02 Data Analysis Preparation
Application of integrated stepper motor in UAV automatic airport
MYSQL逻辑架构
【密码学/密码分析】基于TMTO的密码分析方法
虹科分享|如何用移动目标防御技术防范未知因素
VPGNet
随机推荐
两院院士直言:不要迷信院士
thymeleaf iterates the map collection
Rainbow share | how to use moving targets defense technology to guard against the unknown
pycaret源码分析:下载数据集\Lib\site-packages\pycaret\datasets.py
微信小程序之小程序页面语法
精心总结十三条建议,帮你创建更合适的MySQL索引
ROS2系列知识(4): 理解【服务】的概念
Classes and Objects: Medium
一体化步进电机在无人机自动机场的应用
Matlab/ArcGIS processing GPM global monthly precipitation data
ECCV2022 Workshop | 复杂环境中的多目标跟踪和分割
如何设计高可用高性能中间件 - 作业
Interview Blitz 69: Is TCP Reliable?Why?
Js replication
Nmap 操作手册 - 完整版
Kyoto University:Masaki Waga | 黑箱环境中强化学习的动态屏蔽
C# Rectangle basic usage and picture cutting
Usage of mysql having
MVCC总结
Carefully organize 16 MySQL usage specifications to reduce problems by 80% and recommend sharing with the team