题目来源

• leetcode：319. 灯泡开关

题目描述

题目解析

分析数据量

• 遍历不行

找规律

• 首先，对于第x个灯泡，它经过n轮，什么情况下它还亮着呢？
  • 显然，对x做了奇数次的切换才能保证x是亮着的
  • 所以，我们要做的是找到第几个位置的灯泡会做奇数次切换
• 那么，下一个问题：什么情况下会切换第x个灯泡的开关？
  • 显然，当轮数k是x的约数时才会切换第x个灯泡的开关
  • 比如，给定n为9，x为6。很明显，只有第1、2、3、6轮会切换第6个灯泡的开关，所以第6个灯泡是灭的，因为它做了偶数次切换。
  • 而我们要找的是做了奇数次切换的灯泡，也就是约数个数为奇数的灯泡
• 于是问题转换为：在[1, n]内有多少个数，其约数的个数为奇数个。
  • 结论：完全平方数的因数个数是奇数，非完全平方数因数个数为偶数。
  • 比如当n为 36 时，它的因数有 (1,36), (2,18), (3,12), (4,9), (6,6), 可以看到前四个括号里成对出现的因数各不相同，括号中前面的数改变了灯泡状态，后面的数又变回去了，等于灯泡的状态没有发生变化，只有最后那个 (6,6)，在次数6的时候改变了一次状态，没有对应其它的状态能将其变回去了，所以灯泡就一直是点亮状态的。所以所有平方数都有这么一个相等的因数对，即所有平方数的灯泡都将会是点亮的状态。
  • 问题最终转换为：在 [1,n]中完全平方数的个数为多少。

class Solution {
    
public:
    int bulbSwitch(int n) {
    
        int res = 1;
        while (res * res <= n) ++res;
        return res - 1;
    }
};

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