LeetCode319——灯泡开关

我的LeetCode代码仓：https://github.com/617076674/LeetCode

原题链接：https://leetcode-cn.com/problems/bulb-switcher/

题目描述：

知识点：数学、找规律

思路一：暴力**法（在LeetCode中提交会超时）

提供两种思路的暴力**法，时间复杂度均是O(n ^ 2)，空间复杂度均是O(n)：

（一）开一个大小为n的数组，初始时全部点亮，数组值全是1。按照题目要求，通过乘以-1这一操作切换灯的状态。

JAVA代码：

public class Solution {
    public int bulbSwitch(int n) {
        int[] bulbs = new int[n];
        Arrays.fill(bulbs, 1);
        for (int i = 2; i < n + 1; i++) {
            for (int j = 0; j < n; j++) {
                if (0 == (j + 1) % i) {
                    bulbs[j] *= -1;
                }
            }
        }
        int result = 0;
        for (int i = 0; i < n; i++) {
            if (1 == bulbs[i]) {
                result++;
            }
        }
        return result;
    }
}

（二）记录每盏灯切换的状态次数，根据切换次数的奇偶来确定灯最终的亮与灭。

JAVA代码：

public class Solution {
    public int bulbSwitch(int n) {
        int[] changes = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = 2; j <= n; j++) {
                if (0 == (i + 1) % j) {
                    changes[i]++;
                }
            }
        }
        int result = 0;
        for (int i = 0; i < n; i++) {
            if (0 == changes[i] % 2) {
                result++;
            }
        }
        return result;
    }
}

思路二：找规律

假设n无穷大，那么灯泡i会切换几次状态呢？

灯泡1：第1次。总共1次，最终状态：亮

灯泡2：第1次，第2次。总共2次，最终状态：灭。

灯泡3：第1次，第3次。总共2次，最终状态：灭。

灯泡4：第1次，第2次，第3次。总共3次，最终状态：亮。

灯泡5：第1次，第5次。总共2次，最终状态：灭。

灯泡6：第1次，第2次，第3次，第6次。总共4次，最终状态灭。

灯泡7：第1次，第7次。总共2次，最终状态：灭。

灯泡8：第1次，第2次，第4次，第8次。总共4次，最终状态：灭。

灯泡9：第1次，第3次，第9次。总共3次，最终状态：亮。

……

通过上述规律，我们发现，只有序号是完全平方数的灯泡，最终状态才是亮的。因此问题就转化为了，在[1, n]范围内，有多少个完全平方数呢？我们可以一个个地遍历[1, n]中的数来计算完全平方数的数量，这样的时间复杂度是O(n)的。但实际上，我们还可以进一步转化该问题：

假设n=100，那么在[1, 100]范围内有多少个完全平方数呢？

显然有：1 * 1，2 * 2，……，10 * 10这10个，也就是n ^ 0.5（向下取整）个。

因此，最终问题就变为求n ^ 0.5（向下取整）的值。这个问题在LeetCode069——x的平方根已经有了详细阐述。

JAVA代码：

public class Solution {
    public int bulbSwitch(int n) {
        return (int) Math.sqrt(n);
    }

    private int sqrt1(int n) {
        int left = 0, right = n / 2 + 1;
        while (left <= right) {
            long mid = left + (right - left) / 2;
            if (mid * mid == n) {
                return (int) mid;
            } else if (mid * mid < n) {
                left = (int) (mid + 1);
            } else {
                right = (int) (mid - 1);
            }
        }
        return right;
    }

    private int sqrt2(int n) {
        double pre = 0, cur = 1;
        while (Math.abs(pre - cur) >= 0.000001) {
            pre = cur;
            cur = (n + cur * cur) / (2 * cur);
        }
        return (int) pre;
    }
}

LeetCode解题报告（以直接用Math.sqrt()函数为例）：