🌕🌗 319. 灯泡开关

难度: 🌕🌗

问题描述

---

解法

class Solution {
    public int bulbSwitch(int n) {
        // 思路：
        // 找规律
        // 灯泡 k 什么时候会发生状态切换？
        // 假设 n == 16, k == 15 ∈ [1, 16]
        // 1: off --> on
        // 3: on --> off
        // 5: off --> on
        // 15: on --> off

        // 假设 n == 16, k == 16 ∈ [1, 16]
        // 1: off --> on
        // 2: on --> off
        // 4: off --> on
        // 8: on --> off
        // 16: off --> on

        // 可以看出，k 在 [1, n] 范围内，有多少个约数，就发生多少次切换，当约数为 奇数 时，最终状态为 亮
        // 什么情况下 k 的约数为 奇数 个？
        // k 为完全平方数时
        // ∴题意可以换成：[1, n] 中有多少个 完全平方数？
        // 即 {1*1, 2*2, ..., ?*?} <= n，求 ? 的值
        return (int) Math.sqrt(n);
    }
}

---

输出