signed

QiShunwang

“诚信为本、客户至上”

Leetcode 1375. Bulb Switcher III (python+cpp)

2020/12/27 7:26:12   来源:

题目

在这里插入图片描述

解法:

这道题目想清楚了关键就非常的简单。当一个灯被点亮时,这个灯变量的条件是,他的左边的所有灯都是亮的。意味着从这个等开始到1的灯都必须全部点亮,换句话说,他左边包括他自己一共被点亮的灯数必须等于他的编号。而要满足所有的灯都是蓝色,显然由最右边的点亮的等来决定,只要最右边此时被点亮的灯满足变蓝条件,那么自然所有的灯都是蓝色的,所以只需要简单操作如下:

  • 保存并更新此刻及之前所有状态中被点亮灯的最右边那盏
  • 每一次判断最右边那盏是否符合变蓝的条件
class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        max_bulb_ind = 0
        count = 0
        turnedon_bulb = 0
        
        for bulb in light:
            max_bulb_ind = max(max_bulb_ind,bulb)
            turnedon_bulb += 1
            if turnedon_bulb == max_bulb_ind:
                count += 1
        
        return count

C++版本

class Solution {
public:
    int numTimesAllBlue(vector<int>& light) {
        int count = 0;
        int max_bulb_ind = 0;
        int turnedon_bulbs = 0;
        for(int i=0;i<light.size();i++){
            max_bulb_ind = max(max_bulb_ind,light[i]);
            turnedon_bulbs++;
            if(max_bulb_ind == turnedon_bulbs) count++;
        }
        return count;
    }
    
};