头条笔试题:点亮所有灯

今天朋友发了一道头条面试题,如下:

坐标头条，昨天面试官面试算法。面试官出了这样一道题: 一个圆环上有100个灯泡，灯泡有打开关闭两种状态，灯泡的状态随机，按一个灯泡，相邻的两个灯泡的状态也发生一次变化。比如暗-亮-暗，按中间灯泡，变化为亮-暗-亮。问， 设计一道算法，使得所有灯泡最后都亮。

解题思路:

• 依次关闭0到97所有已点亮的灯:如第i盏灯已经点亮,则按i+1盏灯,可将第i盏灯关闭
• 剩下编号为98和99的两盏灯,分三种情况
  1. 只有一盏灯亮,假设为第i盏灯亮则从i + 2开始点,每隔三盏灯点一次直到全部点亮
  2. 两盏灯都亮,则再次点98号灯,此时97号灯亮,其它全灭,余下参考1.
  3. 所有灯全灭,此时依次点0-99号灯,最终所有灯全亮

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

/*
解题思路:

依次关闭0到97所有已点亮的灯:如第i盏灯已经点亮,则按i+1盏灯,可将第i盏灯关闭
剩下编号为98和99的两盏灯,分三种情况
1. 只有一盏灯亮,假设为第i盏灯亮则从i + 2开始点,每隔三盏灯点一次直到全部点亮
2. 两盏灯都亮,则再次点98号灯,此时97号灯亮,其它全灭,余下参考1.
3. 所有灯全灭,此时依次点0-99号灯,最终所有灯全亮
*/
void Check(vector<bool>& lights){
    for (auto i : lights) {
        assert(i == true);
    }
}

void Change(vector<bool>& lights,size_t const i){
    auto size = lights.size();
    auto index = size + i - 1;
    lights[(index % size)] = !lights[(index % size)];
    ++index;
    lights[index % size] = !lights[index % size];
    ++index;
    lights[(index % size)] = !lights[(index % size)];
}

void TurnOnAll(vector<bool>& lights){
    auto const size = lights.size();
    for (size_t i = 0; i < size - 2; ++ i) {
        if (lights[i] == true) {
            Change(lights,i+1);
        }
    }
    if (!lights[size - 1] && !lights[size - 2]) {//所有灯都关闭的情况
        for (size_t i = 0; i < size ; i++) {
            Change(lights,i);
        }
        return;
    }
    
    size_t onIndex = size - 1;
    if (lights[size - 1] == lights[size - 2]) {
        Change(lights, size -2);
        onIndex = size - 3;
    }else if(!lights[size - 1] ){
        onIndex = size - 2;
    }
    size_t end = onIndex + size;
    for (size_t i = onIndex + 2;  i < end; i += 3) {
        Change(lights, i);
    }
    Check(lights);
}

void PrintState(vector<bool> const& lights){
    for (size_t i = 0; i < lights.size(); ++i) {
        cout<<(int)lights[i];
        if (i%10 == 9) {
            cout<<endl;
        }
    }
}

int main(){
    vector<bool> lights(100);
    for (size_t i = 0; i < lights.size(); ++i) {
       lights[i] = (bool)(rand()%3); //注释掉该行可验证"所有灯都关闭的情况"
    }
    PrintState(lights);
    TurnOnAll(lights);
    cout<<endl;
    PrintState(lights);
    return 0;
}