3842. 切换打开灯泡

English Version

题目描述

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

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

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

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

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

 

示例 1：

示例 2：

 

提示：

• 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$ 是灯泡的最大编号。

Python3

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]

Java

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;
    }
}

C++

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;
    }
};

Go

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
}

TypeScript

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;
}