LeetCode319——灯泡开关

深碍√TFBOYSˉ_ 2022-01-26 08:39 286阅读 0赞

我的LeetCode代码仓：[https://github.com/617076674/LeetCode][https_github.com_617076674_LeetCode]

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

题目描述：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjMxOTI2_size_16_color_FFFFFF_t_70][]

知识点：数学、找规律

### 思路一：暴力破解法（在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的平方根][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()函数为例）：

![20190528165504326.jpg][]

[https_github.com_617076674_LeetCode]: https://github.com/617076674/LeetCode
[https_leetcode-cn.com_problems_bulb-switcher]: https://leetcode-cn.com/problems/bulb-switcher/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjMxOTI2_size_16_color_FFFFFF_t_70]: /images/20220126/f9c5a1bf3b9d46e89e46274c267583c9.png
[LeetCode069_x]: https://blog.csdn.net/qq_41231926/article/details/82861877
[20190528165504326.jpg]: /images/20220126/118ed869128d452a94e82e0f857b3f8f.png