題目來源
給一個n衅金，有n個燈泡，第一次每個都打開簿煌，第二次每隔一個觸發(fā)開關(guān)氮唯，第三次每隔兩個觸發(fā)開關(guān)，直到第n次姨伟，最后還剩多少個開著的惩琉。
我一開始想的是n^2的做法，然后超時了夺荒。
之后稍微改進(jìn)一點(diǎn)點(diǎn)瞒渠，但是還是超時。
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;
}
};
想了想貌似可以用動態(tài)規(guī)劃技扼？想了想也沒啥用伍玖。
看了下討論區(qū)…代碼如下：
class Solution {
public:
int bulbSwitch(int n) {
return sqrt(n);
}
};
因?yàn)橹挥挟?dāng)某個數(shù)是平方數(shù)的時候，它的因子數(shù)目才是奇數(shù)個剿吻，假如不是平方數(shù)窍箍，比如12，有1和12丽旅，2和6椰棘，3和4，一共6個榄笙。每一個因子i都有另一個因子n/i邪狞，除非兩個因子相等。
