返回

[Leetcode]319. Bulb Switcher(C++)

题目描述

题目链接:319. Bulb Switcher

There are n bulbs that are initially off. You first turn on all the bulbs, then you turn off every second bulb.

On the third round, you toggle every third bulb (turning on if it’s off or turning off if it’s on). For the ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb.

Return the number of bulbs that are on after n rounds.

例子

见官网例子。

Constraints

  • 0 <= n <= 10^9

解题思路

首先看数据规模基本可以判断不能使用常规迭代方法求解。因此转为观察每个灯泡状态变化的规律。题目要求求出最后亮着灯泡的个数,而要求灯泡最后是亮的,需要被转换状态奇数次。每个灯泡的状态转换次数和它的因子数相等。比如 2 的因子是 (1, 2),表示在第 1 轮和第 2 轮会转换状态。大部分数的因子是成对的,因此可以抵消掉。只有平方数的独特因子个数的奇数的,比如 4 只有 2 这一个因子。36 的因子有:(1, 36, 2, 18, 3, 12, 4, 9, *6),从这个规律我们看到只有完全平方数才会得到奇数个因子,因此最后是亮着的。因此问题转换为求 n 范围内的完全平方数的个数。一个方法是直接遍历,另一个方法是对 n 开根号向下取整,表示 sqrt(n) 以下的数字的平方都比 n 小,因此可以作为 n 以内的完全平方数的个数。

#include<cmath>

class Solution {
public:
    int bulbSwitch(int n) {
        return static_cast<int>(sqrt(n));
    }
};
  • 时间复杂度: O(1)
  • 空间复杂度: O(1)

GitHub 代码同步地址: 319.BulbSwitcher.cpp

其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions

Built with Hugo
Theme Stack designed by Jimmy