LeetCode 319 Bulb Switcher

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

概述

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);
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/