Leetcode|灯泡开关

简介: Leetcode|灯泡开关

问题描述

房间中有 n 枚灯泡,编号从 1 到 n,自左向右排成一排。最初,所有的灯都是关着的。

在 k  时刻( k 的取值范围是 0 到 n - 1),我们打开 light[k] 这个灯。

灯的颜色要想 变成蓝色 就必须同时满足下面两个条件:

1.灯处于打开状态。

2.排在它之前(左侧)的所有灯也都处于打开状态。

请返回能够让所有开着的灯都变成蓝色的时刻数目 。

示例 1:

输入:light = [2,1,3,5,4]

输出:3

解释:所有开着的灯都变蓝的时刻分别是 1,2 和 4 。

示例 2:


输入:light = [3,2,4,1,5]

输出:2

解释:所有开着的灯都变蓝的时刻分别是 3 和 4(index-0)。

解决方案

思路分析

由上图Moment 1、Moment 2、Moment 4可以得知灯泡全部变蓝的条件:所有点亮的灯泡都连续排列在队列的最左边且无任何断点,每点亮一次都进行一次判定,最后返回满足条件的总数。

先用布尔型来初始化一个列表,用来表示灯泡的开关状态,在列表首位各加上一个元素,首加True,末尾加False,为了节约运行时间,引入一个判断变量。在刚刚开始灯泡全熄灭的时候,判断到light的元素在对应的列表里发生了改变,如果前为Ture,后为False,那么肯定满足条件。

python代码

def numTimesAllBlue(light):
    n = 
len(light)
    a = [
False for in range(n + 2)]

#占位符相对于ij不会向系统内存申请储存,相对于会用更少的时间和空间,虽然很少,但用python写力扣的大家来说,一点点时间都很宝贵。
    a[
0] = True
    
cnt = 0
    
ans = 0
    
for in light:
        cnt += 
not a[l - 1]

#布尔值和数值发生计算时,Ture默认为1False默认为0,我们借这其中的关系来进行找关系
        cnt -= a[l + 
1]
        a[l] = 
True
        if 
cnt == 0:
            ans += 
1
    
return ans

 

在比赛时这道题最大的问题就是超时,遇到这种情况不要慌,从代码各方面入手进行简化,想办法把一些内置函数给替换成一些基本运算。

目录
相关文章
|
算法 C++ Python
【每日算法Day 61】LeetCode 672. 灯泡开关 Ⅱ
【每日算法Day 61】LeetCode 672. 灯泡开关 Ⅱ
104 0
|
算法 C++
每日算法系列【LeetCode 319】灯泡开关
每日算法系列【LeetCode 319】灯泡开关
138 0
LeetCode 1375. 灯泡开关 III
LeetCode 1375. 灯泡开关 III
LeetCode contest 199 灯泡开关 IV Bulb Switcher IV
LeetCode contest 199 灯泡开关 IV Bulb Switcher IV
|
机器学习/深度学习
LeetCode每日一题——672. 灯泡开关 Ⅱ
房间中有 n 只已经打开的灯泡,编号从 1 到 n 。墙上挂着 4 个开关 。
94 0
|
机器学习/深度学习 自然语言处理 算法
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
55 6
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
108 2
|
11天前
|
机器学习/深度学习 人工智能 自然语言处理
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
14 1