[Leetcode 319] Bulb Switcher

作者 Shilei Tian 日期 2016-09-03
[Leetcode 319] Bulb Switcher

这是一道非常有意思的题,题目的要求如下:

There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it’s off or turning off if it’s on). For the ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb. Find how many bulbs are on after n rounds.

另外它给出了一个当 n = 3 时的例子:

1
2
3
4
5
6
7
8
Given n = 3. 

At first, the three bulbs are [off, off, off].
After first round, the three bulbs are [on, on, on].
After second round, the three bulbs are [on, off, on].
After third round, the three bulbs are [on, off, off].

So you should return 1, because there is only one bulb is on.

题目的意思其实很简单,通过读题我们就可以想到一个非常耿直的做法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
int bulbSwitch(int n) {
if (n == 1) {
return 1;
}
vector<bool> bulbs(n, true);
int cnt = n;
for (auto i = 2; i <= n; ++i) {
for (auto j = i - 1; j < n; j += i) {
bulbs[j] = !bulbs[j];
if (!bulbs[j]) {
--cnt;
} else {
++cnt;
}
}
}
return cnt;
}
};

但是非常不幸的是,如果 n 非常大的话,在定义 vector 的时候会超时,它的时间复杂度也是 O(nlogn)。那么我们就必须来仔细的研究一下这道题了。首先考虑,一盏灯在什么情况下最后会保持点亮?就是当它被操作(toggle)了奇数次之后。那什么时候我们会去操作一盏灯呢?就是当它是 i 的倍数的时候(这里 i 指的是轮数)。那么我们举个例子,假设我们的 n >= 12,那么第 12 栈灯会在第 1 轮打开,然后第 2 轮灭掉,第 3 轮打开,第 4 轮灭掉,第 6 轮打开,第 12 轮灭掉。这里的 1, 2, 3, 4, 6, 12 实际上就是 12 的约数,观察可以发现,它们似乎是成对出现的:1, 122, 63, 4。实际上,大部分情况下,它确实是成对出现的,因此这些灯在最终必然会是关闭的。那么什么情况下不适成对出现的呢?当它是一个平方数的时候!比如,16 的约数有 1, 2, 4, 8, 16。为什么会少了一个呢?是因为,4, 4 本来是一对的…但是它俩是一个数呀!所以,通过这个观察,我们就可以得出结论,只有当一盏灯的编号是一个平方数的时候,它最后才是亮的。那么接下来的工作,就是看看在 n 的范围内有几个平方数就可以了,显然,有 sqrt(n) 个,所以我们的程序就变成了下面的这个样子:

1
2
3
4
5
6
class Solution {
public:
int bulbSwitch(int n) {
return sqrt(n);
}
};

仅仅一行代码而已…这个时间复杂度就不需要说了,O(1)

其实很多其他的代码也和这道题相似,表面上看逻辑是这样的,但实际上仔细思考过后,能发现逻辑很简单,用比较“红”的话讲,就是“要抓住问题的本质”。