java - 找到打开所有灯泡的最少开关数

Question

我正在尝试理解给出的问题 here及其解决方案:

问题说明:

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(关闭)，因为之前的翻转。