问题描述
房间中有 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)]
#占位符相对于i,j不会向系统内存申请储存,相对于会用更少的时间和空间,虽然很少,但用python写力扣的大家来说,一点点时间都很宝贵。
a[0] = True
cnt = 0
ans = 0
for l in light:
cnt += not a[l - 1]
#布尔值和数值发生计算时,Ture默认为1,False默认为0,我们借这其中的关系来进行找关系
cnt -= a[l + 1]
a[l] = True
if cnt == 0:
ans += 1
return ans
在比赛时这道题最大的问题就是超时,遇到这种情况不要慌,从代码各方面入手进行简化,想办法把一些内置函数给替换成一些基本运算。
END主 编 | 张祯悦
责 编 | 刘仕豪
where2go 团队
微信号:算法与编程之美
本站仅提供存储服务,所有内容均由用户发布,如发现有害或侵权内容,请
点击举报。