LeetCode 319 Bulb Switcher

    
        标签：
        
            数学类题目
        
            LeetCode
        
    发布于：2022-03-01 15:16:28
    编辑于：2022-03-01 15:24:14
    浏览量：865

概述

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

暴力法

直接暴力模拟。

时间复杂度 O(n^2)，TLE 了。

class Solution {
public:
    int bulbSwitch(int n) {
        vector<bool> b(n+1);
        for (int i = 1; i <= n; i ++) {
            for (int j = 1; j <= n; j ++) {
                if (j % i == 0) b[j] = !b[j];
            }
        }
        int count = 0;
        for (auto t : b) count += t;
        return count;
    }
};

平方根

https://labuladong.gitee.io/algo/4/30/124/#三电灯开关问题

考虑灯的个数 n，如总是可以被分解为 n = a * b = c * d ，至少有一个 1 * n。

这些因子都是成对的，除非出现 16 = 4 * 4 这种情况。

换句话说，当且仅当第 i 栈灯是某个整数的平方时，其才是亮的。

所以：

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

Links: leetcode-319-bulb-switcher