LeetCode319. 灯泡开关

1、题目链接

https://leetcode-cn.com/problems/bulb-switcher/

2、解题思路

这道题的意思是有N个灯泡，初始状态是熄灭的，第1次让你每个灯泡都切换一下状态（熄灭的就打开，已经打开的就熄灭），第2次让你每2个灯泡切换一下状态，第N次让你每N个灯泡切换一下状态，最后问N轮之后有多少灯泡还是亮着的。一开始我是想着弄一个数组来记录每个灯泡的状态，然后根据要求来开或者关灯泡，但是到后面发现会超时，既然会超时那么就肯定有规律在里面，我们来模拟一下，假如有9个灯泡：

初状态：0，0，0，0，0，0，0，0，0

第1⃣️轮：1，1，1，1，1，1，1，1，1

第2⃣️轮：1，0，1，0，1，0，1，0，1

第3⃣️轮：1，0，0，0，1，1，1，0，0

第4⃣️轮：1，0，0，1，1，1，1，1，0

第5⃣️轮：1，0，0，1，0，1，1，1，0

第6⃣️轮：1，0，0，1，0，0，1，1，0

第7⃣️轮：1，0，0，1，0，0，0，1，0

第8⃣️轮：1，0，0，1，0，0，0，0，0

第9⃣️轮：1，0，0，1，0，0，0，0，1

当我写完这9轮的时候，我就发现一个规律，第i轮改变状态的灯泡有i本身这个灯泡和能把i整除的灯泡，然后还有一个问题，当某个灯泡改变状态为奇数次时，最后它的状态肯定亮着的，SO？我们可以将问题转化一下，找出因子（整除）个数为奇数的灯泡就是我们最终的答案，然而恰好有一种数他的因子就是奇数的，没错，就是完全平方数（就是能被开方的数），所以这道题换个角度来看就是寻找N以内平方数的个数，再换句话说，也就是求根号N的整数部分，不信你试试

3、代码

    public static int bulbSwitch(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        return (int) Math.sqrt(n);
//        int result = 0;
//
//        int[] array = new int[n+1];
//        Arrays.fill(array, 1);
//        for (int i = 2; i <= n; i++) {
//            for (int j = 2; j < array.length; j++) {
//                if (j % i == 0) {
//                    array[j] = (array[j] == 1 ? 0 : 1);
//                }
//            }
//        }
//        for (int j = 1; j < array.length; j++) {
//            if (array[j] == 1) {
//                result++;
//            }
//        }
//        return result;
    }

4、结果

WX20190828-194748@2x.png