当前位置:网站首页>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
总结
强悍模拟 + 端点记录 + 区间范围合并大法
边栏推荐
- 设计消息队列存储消息数据的MySQL表格
- Keil nRF52832 download failed
- VPGNet
- js 实现复制功能
- cobaltstrike
- 蓝图:杨辉三角排列
- /etc/sysconfig/network-scripts configure the network card
- 南方科技大学:Xiaoying Tang | AADG:视网膜图像分割领域泛化的自动增强
- In 2022, the latest eight Chongqing construction members (electrical construction workers) simulation question bank and answers
- MYSQL事务
猜你喜欢
pycaret source code analysis: download dataset\Lib\site-packages\pycaret\datasets.py
[Reading Notes -> Data Analysis] 02 Data Analysis Preparation
C# Rectangle基本用法和图片切割
如何设计高可用高性能中间件 - 作业
Matlab / Arcgis处理nc数据
MYSQL-批量插入数据
ROS2系列知识(4): 理解【服务】的概念
RTL8762DK UART(二)
How to Design High Availability and High Performance Middleware - Homework
[Cloud Residency Co-Creation] [HCSD Big Celebrity Live Broadcast] Personally teach the secrets of interviews in big factories
随机推荐
2022年最新重庆建筑八大员(电气施工员)模拟题库及答案
Web3.0:构建 NFT 市场(一)
自动化机器学习pycaret: PyCaret Basic Auto Classification LightGBM
mySql data view
Nmap Operation Manual - Full Version
清华大学陈建宇教授团队 | 基于接触丰富机器人操作的接触安全强化学习框架
Pylint检查规则中文版
Luogu P3373: 线段树
MYSQL-批量插入数据
Interview Blitz 69: Is TCP Reliable?Why?
cmake入门学习笔记
The principle of virtual inheritance
NIO programming
从零造键盘的键盘超级喜欢,IT人最爱
简单的vim配置
WindowInsetsControllerCompat is simple to use
Recommendation system: Summary of common evaluation indicators [accuracy rate, precision rate, recall rate, hit rate, (normalized depreciation cumulative gain) NDCG, mean reciprocal ranking (MRR), ROC
mysql having的用法
VPGNet
欧拉系统(euleros):升级Mysql