真题练习[0]: Toggle Bulbs | 形&影

真题练习[0]: Toggle Bulbs | 形&影

有n个灯泡。每个灯泡有on 和off两个状态。
实现 bool isOn(int pos)来查询index为pos的灯泡的状态，void toggle(int begin, int end)来改变 begin 到end范围内所有灯泡的状态。
Follow up: 如果toggle很常用如何优化？

Notes: 自然而然可以想到用一个bool数组来表示灯泡序列。再一想，可以bit manipulation，用一个int存储32个灯泡，一个vector<int>来表示所有灯泡。如果begin和end在同一区间时间复杂度是O(1)，否则是O(n)，空间是O(1)。只想到用vector<int>，没有想到记录toggle的历史。
对于toggle的优化可以这样：首先有一个vector来记录toggle历史，然后isOn的时候遍历容器，看pos有多少次落在记录的区间里，统计次数之后对2求余，但查询次数越多统计就会越慢。再接着优化可以用set，插入前查询，是否有同样区间被toggle过，有就删除记录并停止插入，没有就插入。
Tips：当一个算法性能上已经足够优化时，进一步优化应该考虑用空间换时间。

vector<int> init( int n ){

    int sectionNum = n/32;

    if( n % 32 != 0 ) ++sectionNum;

    return vector<int> bulbs( sectionNum, 0 );

}

bool isOn(int pos){

    int section = pos/32;

    pos  = pos%32;

    return( bulbs[section] & (1 << pos) );

}

void toggleInSec(int begin, int end, int &bulbSec){

    // when in the same section

    int mask = 0 ^ ( ( 1 << (begin-end+1)) - 1  ); // set the last begin-end+1 bit to 1

    mask = mask << (begin%32-1);

    bulbSec ^= mask;

}

void toggle(int begin, int end, vector<int> &bulbs){

    int section_bg = begin/32, section_ed = end/32;

    if(section_bg == section_ed )

        toggleInSec(begin, end, bulbs[section_bg]);

    else{

        for(int i = section_bg + 1 ; i < section_ed; ++i ){

            bulbs[i]  = ~bulbs[i];

        }

        toggleInSec(begin%32,31,bulbs[section_bg]);

        toggleInSec(0,end%32, bulbs[section_ed]);

    }      

}

Read full article from 真题练习[0]: Toggle Bulbs | 形&影