题目来源
给一个n，有n个灯泡，第一次每个都打开，第二次每隔一个触发开关，第三次每隔两个触发开关，直到第n次，最后还剩多少个开着的。
我一开始想的是n^2的做法，然后超时了。
之后稍微改进一点点，但是还是超时。
class Solution {
public:
int bulbSwitch(int n) {
vector<int> bulbs(n, 0);
int cnt = 0;
for (int i=1; i<=n; i++) {
for (int j=1; i*j<=n; j++)
bulbs[i*j-1]++;
}
for (int i=0; i<n; i++)
cnt += (bulbs[i] % 2 == 1);
return cnt;
}
};
想了想貌似可以用动态规划？想了想也没啥用。
看了下讨论区…代码如下：
class Solution {
public:
int bulbSwitch(int n) {
return sqrt(n);
}
};
因为只有当某个数是平方数的时候，它的因子数目才是奇数个，假如不是平方数，比如12，有1和12，2和6，3和4，一共6个。每一个因子i都有另一个因子n/i，除非两个因子相等。
