319. Bulb Switcher

解法一

思路

Brute Force 解法。 对 n 个开关，按步长为 1 ~ n 遍历，改变相应位置开关的值。

代码

class Solution {
    public int bulbSwitch(int n) {
        int[] lights = new int[n];
        for (int i = 1; i <= n; i++) {
            for (int j = i; j <=n; j += i) {
                lights[j - 1] = lights[j - 1] == 1 ? 0 : 1;
            }
        }

        int count  = 0;
        for (int i = 0; i < n; i++) {
            if (lights[i] == 1) {
                count++;
            }
        }
        return count;
    }
}

复杂度分析

这个方法在 n = 1000000 之后会超时。但的确是最直接能想到的办法。

• 时间复杂度 O(n^2)
• 空间复杂度 O(n)

解法二

思路

https://leetcode.com/problems/bulb-switche...

代码

(int)Math.sqrt(n);

Takeaway

本作品采用《CC 协议》，转载必须注明作者和本文链接