【每日刷题】灯泡开关

本文主要是介绍【每日刷题】灯泡开关，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

day19, 灯泡开关

题目来源：leetcode
初始时有 n 个灯泡关闭。第 1 轮，你打开所有的灯泡。第 2 轮，每两个灯泡你关闭一次。第 3 轮，每三个灯泡切换一次开关（如果关闭则开启，如果开启则关闭）。第 i 轮，每 i 个灯泡切换一次开关。对于第 n 轮，你只切换最后一个灯泡的开关。找出 n 轮后有多少个亮着的灯泡。

示例:
输入: 3
输出: 1
解释:
初始时, 灯泡状态 [关闭, 关闭, 关闭].
第一轮后, 灯泡状态 [开启, 开启, 开启].
第二轮后, 灯泡状态 [开启, 关闭, 开启].
第三轮后, 灯泡状态 [开启, 关闭, 关闭].
你应该返回 1，因为只有一个灯泡还亮着。

解答：首先给一种枚举的解法：开辟大小为n的数组，分别针对第i = 0,1,2,3…n 轮进行操作。

代码：

int bulbSwitch(int n) {int* state = ( int *)malloc( sizeof(int) * n);for( int i = 0; i < n; i++)state[i] = -1;int k = 1;while( k <= n){if( k != n){for( int i = k - 1; i < n; i+=k)state[i] *=-1;k++;}elsestate[n-1]*=-1, k++;}int sum = 0;for( int i = 0; i < n; i++)if( state[i] == 1)sum++;return sum;}

运行结果：emmm…当n = 99999999时候超时。
image.png-10kB

优化：既然暴力枚举无法解决问题，那么肯定有简单的方法。老方法：找规律。用上述代码运行n = 1~100的情况，发现规律如下：n = 0 时, 结果为0；n = 1~3 时，结果为1；n = 4~8 时，结果为2；n = 9~15 时，结果为3；n = 16~24 时，结果为4…OK，结论已经很明显了。

代码：

int bulbSwitch(int n) {return sqrt(n);
}

运行结果： image.png-23kB

讨论：为什么会等于sqrt(n)这样的结果？
初始时灯泡全部关闭，对于除最后一个之外的每一个灯泡，如果最终结果为亮，那么需要进行奇数次开关操作，所以只有因子个数为奇数的灯泡序号才会结果为亮，而只有平方数的因子数为奇数，例如4 = 1 * 2 = 2 * 2, 而12 = 1 * 12 = 2 * 6 = 3 * 4。
对于最后一个灯泡，如果不是平方数，一定是暗着的；反之是亮着的。