灯泡开关
难度:
标签:
题目描述
初始时有 n 个灯泡处于关闭状态。第一轮，你将会打开所有灯泡。接下来的第二轮，你将会每两个灯泡关闭第二个。
第三轮，你每三个灯泡就切换第三个灯泡的开关（即，打开变关闭，关闭变打开）。第 i 轮，你每 i 个灯泡就切换第 i 个灯泡的开关。直到第 n 轮，你只需要切换最后一个灯泡的开关。
找出并返回 n 轮后有多少个亮着的灯泡。
示例 1：
输入：n = 3 输出：1 解释： 初始时, 灯泡状态 [关闭, 关闭, 关闭]. 第一轮后, 灯泡状态 [开启, 开启, 开启]. 第二轮后, 灯泡状态 [开启, 关闭, 开启]. 第三轮后, 灯泡状态 [开启, 关闭, 关闭]. 你应该返回 1，因为只有一个灯泡还亮着。
示例 2：
输入：n = 0 输出：0
示例 3：
输入：n = 1 输出：1
提示：
0 <= n <= 109
代码结果
运行时间: 17 ms, 内存: 16.0 MB
/*
* 思路：
* 与普通Java解法一致，
* 通过Stream来计算小于等于 n 的平方数的个数。
*/
import java.util.stream.IntStream;
public class BulbSwitcher {
public int bulbSwitch(int n) {
return (int) IntStream.rangeClosed(1, n)
.mapToDouble(Math::sqrt)
.filter(d -> d == (int) d)
.count();
}
}解释
方法:
该问题的核心在于观察每个灯泡在n轮后的状态。一个灯泡i在第k轮被操作，当且仅当k是i的除数。因此，灯泡i在n轮后变化的次数等于它的除数的数量。一个数有奇数个因数当且仅当它是完全平方数（例如，4的因数有1, 2, 4）。因此，问题转化为计算1到n之间完全平方数的数量，这可以通过计算sqrt(n)的整数部分得到，因为这表示了最大的数k，使得k*k <= n。
时间复杂度:
O(1)
空间复杂度:
O(1)
代码细节讲解
🦆
在题解中提到，一个灯泡的状态变化次数等于它的除数的数量。能否详细解释为什么一个数有奇数个因数时它是完全平方数？
▷🦆
题解通过计算sqrt(n)来找出完全平方数的数量。这种方法是否总是准确？存在哪些可能的情况会导致结果误差？
▷🦆
题解中使用了math.sqrt函数并取整来得到结果。这里取整有没有可能对最终的灯泡数量计算产生影响？
▷相关问题
灯泡开关 Ⅱ
房间中有 n 只已经打开的灯泡，编号从 1 到 n 。墙上挂着 4 个开关 。
这 4 个开关各自都具有不同的功能，其中：
- 开关 1 ：反转当前所有灯的状态（即开变为关，关变为开）
- 开关 2 ：反转编号为偶数的灯的状态（即
0, 2, 4, ...） - 开关 3 ：反转编号为奇数的灯的状态（即
1, 3, ...） - 开关 4 ：反转编号为
j = 3k + 1的灯的状态，其中k = 0, 1, 2, ...（即1, 4, 7, 10, ...）
你必须 恰好 按压开关 presses 次。每次按压，你都需要从 4 个开关中选出一个来执行按压操作。
给你两个整数 n 和 presses ，执行完所有按压之后，返回 不同可能状态 的数量。
示例 1：
输入：n = 1, presses = 1 输出：2 解释：状态可以是： - 按压开关 1 ，[关] - 按压开关 2 ，[开]
示例 2：
输入：n = 2, presses = 1 输出：3 解释：状态可以是： - 按压开关 1 ，[关, 关] - 按压开关 2 ，[开, 关] - 按压开关 3 ，[关, 开]
示例 3：
输入：n = 3, presses = 1 输出：4 解释：状态可以是： - 按压开关 1 ，[关, 关, 关] - 按压开关 2 ，[关, 开, 关] - 按压开关 3 ，[开, 关, 开] - 按压开关 4 ，[关, 开, 开]
提示：
1 <= n <= 10000 <= presses <= 1000
K 连续位的最小翻转次数
给定一个二进制数组 nums 和一个整数 k 。
k位翻转 就是从 nums 中选择一个长度为 k 的 子数组 ，同时把子数组中的每一个 0 都改成 1 ，把子数组中的每一个 1 都改成 0 。
返回数组中不存在 0 所需的最小 k位翻转 次数。如果不可能，则返回 -1 。
子数组 是数组的 连续 部分。
示例 1：
输入：nums = [0,1,0], K = 1 输出：2 解释：先翻转 A[0]，然后翻转 A[2]。
示例 2：
输入：nums = [1,1,0], K = 2 输出：-1 解释：无论我们怎样翻转大小为 2 的子数组，我们都不能使数组变为 [1,1,1]。
示例 3：
输入：nums = [0,0,0,1,0,1,1,0], K = 3 输出：3 解释： 翻转 A[0],A[1],A[2]: A变成 [1,1,1,1,0,1,1,0] 翻转 A[4],A[5],A[6]: A变成 [1,1,1,1,1,0,0,0] 翻转 A[5],A[6],A[7]: A变成 [1,1,1,1,1,1,1,1]
提示：
1 <= nums.length <= 1051 <= k <= nums.length