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)]

#占位符相对于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 团队

微信号：算法与编程之美