319. 灯泡开关

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

解题思路

解法1：暴力解法，一个数组存储数据，0/1来标志灯泡开关状态，每次遍历，时间复杂度O（n^2），果然超时、超出内存限制
解决2：找规律，通过列举n个答案，发现规律是n的开方，向下取整

// if(n == 1) return 1;
// if(n == 2) return 1;
// if(n == 3) return 1;
// if(n == 4) return 2;
// if(n == 5) return 2;
// if(n == 6) return 2;
// if(n == 7) return 2;
 // if(n == 8) return 2;

解题遇到的问题

无

后续需要总结学习的知识点

无

##解法1--超出内存限制
class Solution {
    public int bulbSwitch(int n) {
        int[] a = new int[n + 1];
        for (int i = 1; i < a.length; i++) {
            a[i] = 1;
        }
        for (int i = 2; i < a.length; i++) {
            for (int j = i; j < a.length; j = j + j) {
                if (a[j] == 0) {
                    a[j] = 1;
                } else {
                    a[j] = 0;
                }
            }
        }

        int ans = 0;
        for (int i = 1; i < a.length; i++) {
            if (a[i] == 1) {
                ans++;
            }
        }
        return ans;
    }
}

##解法2
class Solution {
    public int bulbSwitch(int n) {
            return (int) Math.floor(Math.sqrt(n));
    }
}