使用最少数量的开关打开所有灯泡

Question

我想了解这里给出的问题及其解决方案:

问题是:

N个灯泡通过电线连接.每个灯泡都有一个与之相关的开关,但由于接线错误,开关也会将所有灯泡的状态改变为电流灯泡的右侧.给定所有灯泡的初始状态,找到您必须按下以打开所有灯泡的最小开关数.您可以多次按下同一个开关.

注意:0代表灯泡关闭,1代表灯泡开启.

Example:

Input : [0 1 0 1]
Return : 4

Explanation :

press switch 0 : [1 0 1 0]
press switch 1 : [1 1 0 1]
press switch 2 : [1 1 1 0]
press switch 3 : [1 1 1 1]

给出的答案之一是:

int solve(int A[], int N) {

    int state= 0, ans = 0;
    for (int i = 0; i < N;i++) {
        if (A[i] == state) {
            ans++;
            state = 1 - state;
        }
    }

    return ans;
}

我似乎无法理解if语句如何做正确的事情.

Answer 1

每当我们翻转一个开关时,我们将所有开关向右翻转,所以如果我们现在搜索0(关闭开关),我们需要搜索1(在开关上),因为我们已经将所有开关向右翻转,让我们看看一个例子:0 1 1 0,现在最初状态= 0,当我们遇到第一个灯泡时我们翻转所有开关,即1 0 0 1但是在数组中值仍然是0 1 1 0,所以我们需要能够认识到第二个索引处的灯泡由于前一次翻转而关闭,所以我们将状态更改为1状态,这使得我们正在寻找的状态为1,同样翻转开关会改变下一个的标准声明我们会搜索.

我在下面写了一段代码片段,这样更容易理解

bool flipped = false;
int ans = 0;
for(int i = 0;i < N;i++){
    if(flipped == false){
        if(A[i] == 0){
            ans++;
            flipped = true;
        }
    }else if(flipped == true){
        if(A[i] == 1){
            ans++;
            flipped = false;
        }
    }
}

在这里,我使用翻转变量来判断灯泡是否已被翻转,如果它们已被翻转,那么我们将搜索1(在开关上),因为实际上它们是0(关闭),因为之前的翻转.

Answer 2

只需要理解两点：

1. 由于右侧的灯泡会在翻转特定开关时翻转，因此从左到右迭代灯泡是有意义的，即索引0到bulbs.length; 和，

2. 因为右边灯泡的状态可以反转，所以我们需要知道是将灯泡的状态视为反转还是按原样对待。

这是实现上述两点的简短而有趣的代码。阅读评论，就会非常容易理解：

int count = 0;
boolean flip = false; //Initially we don't flip the states, so flip is false

for(int i = 0; i < bulb.length; i++) {
    //A bulb is ON when:
    //1. The bulb is ON and it is not supposed to be flipped.
    if (bulb[i] == 1 && !flip) continue;

    //2. The bulb is OFF but it is supposed to be flipped.
    if (bulb[i] == 0 && flip) continue;

    //Now the bulb is OFF, so we turn it ON i.e. increment count and
    //invert the flipping condition for the rest of the bulbs on the right.
    count++;
    flip = !flip;
}

return count;