3842. 切换打开灯泡

题目描述

给你一个整数数组 bulbs，其中每个元素的取值范围为 1 到 100。

有 100 个电灯泡，按从 1 到 100 编号，初始时所有灯泡均为关闭状态。

对于数组 bulbs 中的每一个元素 bulbs[i]，执行以下操作：

如果第 bulbs[i] 个灯泡当前是关闭状态，将其打开。
如果第 bulbs[i] 个灯泡当前是打开状态，将其关闭。

返回一个整数列表，表示最终处于打开状态的灯泡编号，按升序排列。如果没有灯泡是打开的，返回一个空列表。

示例 1：

输入： bulbs = [10,30,20,10]

输出： [20,30]

解释：

第 bulbs[0] = 10 个灯泡当前是关闭状态，将其打开。
第 bulbs[1] = 30 个灯泡当前是关闭状态，将其打开。
第 bulbs[2] = 20 个灯泡当前是关闭状态，将其打开。
第 bulbs[3] = 10 个灯泡当前是打开状态，将其关闭。
最终，第 20 个和第 30 个灯泡处于打开状态。

示例 2：

输入： bulbs = [100,100]

输出： []

解释：

第 bulbs[0] = 100 个灯泡当前是关闭状态，将其打开。
第 bulbs[1] = 100 个灯泡当前是打开状态，将其关闭。
最终，没有灯泡处于打开状态。

提示：

1 <= bulbs.length <= 100
1 <= bulbs[i] <= 100

解法

方法一：模拟

我们用一个长度为 \(101\) 的数组 \(\textit{st}\) 来记录每个灯泡的状态，初始时所有元素为 \(0\)，表示所有灯泡均为关闭状态。对于数组 \(\textit{bulbs}\) 中的每一个元素 \(\textit{bulbs}[i]\)，我们将 \(\textit{st}[\textit{bulbs}[i]]\) 的值取反（即 \(0\) 变为 \(1\)，\(1\) 变为 \(0\)）。最后，我们遍历 \(\textit{st}\) 数组，将值为 \(1\) 的索引加入结果列表中，并返回结果。

时间复杂度 \(O(n)\)，其中 \(n\) 是数组 \(\textit{bulbs}\) 的长度。空间复杂度 \(O(M)\)，其中 \(M\) 是灯泡的最大编号。

Python3JavaC++GoTypeScript

class Solution:
    def toggleLightBulbs(self, bulbs: list[int]) -> list[int]:
        st = [0] * 101
        for x in bulbs:
            st[x] ^= 1
        return [i for i, x in enumerate(st) if x]

class Solution {
    public List<Integer> toggleLightBulbs(List<Integer> bulbs) {
        int[] st = new int[101];
        for (int x : bulbs) {
            st[x] ^= 1;
        }
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < st.length; ++i) {
            if (st[i] == 1) {
                ans.add(i);
            }
        }
        return ans;
    }
}

class Solution {
public:
    vector<int> toggleLightBulbs(vector<int>& bulbs) {
        vector<int> st(101, 0);
        for (int x : bulbs) {
            st[x] ^= 1;
        }
        vector<int> ans;
        for (int i = 0; i < 101; ++i) {
            if (st[i]) {
                ans.push_back(i);
            }
        }
        return ans;
    }
};

func toggleLightBulbs(bulbs []int) []int {
    st := make([]int, 101)
    for _, x := range bulbs {
        st[x] ^= 1
    }
    ans := make([]int, 0)
    for i := 0; i < 101; i++ {
        if st[i] == 1 {
            ans = append(ans, i)
        }
    }
    return ans
}

function toggleLightBulbs(bulbs: number[]): number[] {
    const st: number[] = new Array(101).fill(0);
    for (const x of bulbs) {
        st[x] ^= 1;
    }
    const ans: number[] = [];
    for (let i = 0; i < 101; i++) {
        if (st[i] === 1) {
            ans.push(i);
        }
    }
    return ans;
}

3842. 切换打开灯泡

题目描述

解法

方法一：模拟

评论