[Leetcode] 第319题 灯泡开关

一、题目描述

初始时有 n 个灯泡关闭。 第 1 轮，你打开所有的灯泡。 第 2 轮，每两个灯泡你关闭一次。 第 3 轮，每三个灯泡切换一次开关（如果关闭则开启，如果开启则关闭）。第 i 轮，每 i 个灯泡切换一次开关。 对于第 n 轮，你只切换最后一个灯泡的开关。 找出 n 轮后有多少个亮着的灯泡。

示例:

输入: 3

输出: 1

解释:

初始时, 灯泡状态 [关闭, 关闭, 关闭].

第一轮后, 灯泡状态 [开启, 开启, 开启].

第二轮后, 灯泡状态 [开启, 关闭, 开启].

第三轮后, 灯泡状态 [开启, 关闭, 关闭].

你应该返回 1，因为只有一个灯泡还亮着。

二、题目解析

1）这个问题关键在于理解题意和找出规律

2）其实就是每i个灯泡切换一次；用一个大小为n的数组，把所有过程跑一遍；这样会超时

3）发现规律，i*i~(i+1)*(i+1)有i个

三、代码

class Solution {

public:

    int bulbSwitch(int n) {

        /*if (!n)return 0;

        vector<int>v(n, 1);

        for (int i = 2; i <= n; ++i) {

            for (int j = 1; i*j <= n; ++j) {

                if (v[i*j-1] == 1)

                    v[i*j - 1] = 0;

                else v[i*j - 1] = 1;

            }

        }

        int res = 0;

        for (int i = 0; i < n; ++i)

            res += v[i];*/

        int res = sqrt(n);

        return res;

    }

};