有趣的算法题热热身：灯泡开关
计算机基础和算法是能否拿到一个好offer的关键因素，月底牛牛就忙完手上项目了，到时也会多分享相关内容，今天就先整一道leetcode上有趣的算法题热热身：灯泡开关。 01故事起源 初始时有 n 个灯泡，均处于关闭状态。
对某个灯泡切换开关意味着：如果灯泡状态为关闭，那该灯泡就会被开启；而灯泡状态为开启，那该灯泡就会被关闭。
第 1 轮，每个灯泡切换一次开关。即打开所有的灯泡。
第 2 轮，每两个灯泡切换一次开关。即每两个灯泡关闭后一个。
第 3 轮，每三个灯泡切换一次开关。即位于第3、6、9···的灯泡切换开关。
第 i 轮，每 i 个灯泡切换一次开关。而第 n 轮，你只切换最后一个灯泡的开关。
找出 n 轮后有多少个亮着的灯泡。
示例 1：
输入：n = 6 输出：2
02问题分析
通过上面的图例，我们可以很清楚地看到，每一轮都会切换一批灯泡。关键是可能切换到之前已经切换过的灯泡，如果我们通过模拟来暴力解决，那么每一轮就要遍历一次，肯定超时。
那我们换种思路想想，这道题似乎更像一道有数学规律的题，这种类型在面试中也不少见。
不过我们不一定能马上找到规律，那也不要着急，就按部就班：用0表示off, 1表示on，先列出前10个灯泡的答案，看看其中有什么规律可循。
n=1：1
n=2：1 0
n=3：1 0 0
n=4：1 0 0 1
n=5：1 0 0 1 0
n=6：1 0 0 1 0 0
n=7：1 0 0 1 0 0 0
n=8：1 0 0 1 0 0 0 0
n=9：1 0 0 1 0 0 0 0 1
n=10: 1 0 0 1 0 0 0 0 1 0
03发现规律
我们仔细看看上面的数据就会发现，最后亮灯的位置都在第1、4、9位上，这些位置恰好都是某个因子的平方，比如4，就是2的平方，不知道大家还记得不，在数学上这种数字就叫做完全平方数。
那我们就可以大胆猜测：最后亮灯的位置，都是完全平方数。那么每多一个完全平方数，就多一个亮的灯泡。
当然，这只是一个猜测，我们可以用暴力法写一个程序，把前100个的情况打印出来，就能看出，是满足这个规律的。
都已经验证到100轮了，那么基本就是这个规律了。
所以这道题，其实就是寻找n以内有多少个完全平方数，具体做法是从数字1遍历到数字n，对每个数字判断是否是完全平方数，最差也是o(n)可以解决。
04思考缘由
牛牛是个打破砂锅问到底的人，虽然通过规律，解决了问题，但是不搞清楚为什么，总是心里痒痒的。
我们从上面的规律，可以猜测灯泡亮的数量一定和平方根的特性有关系的。
我们先看看一些非完全平方数：
8的因子: 1 2 4 8；
12的因子：1 2 3 4 6 12；
这些因子一定是偶数个，为什么呢？
因为一个因子，一定是和另一个因子，配合起来，才能得到这个数字。
回到我们的灯泡，比如我们拿n=3的情况来说，第一轮打开了第三轮的灯泡，第三轮就会给它关掉，因为1、3是3的成对因子。
但如果是n=4的情况，1、4虽然也会成对抵消，但是第二轮的操作却无法抵消，因为2的成对因子是2，不会再重复出现。
从这里我们就可以看出来，每增加一个完全平方数，就会多一个不会被抵消掉的因子出现，所以个数也就增加了1。
05更进一步
一般的算法题，o(n)就是性能的极致，但这是一道数学规律题，那我们就得多想想还有没有更快的办法。
要找到有多少个完全平方数，是否一定要遍历完1-n？
稍微思考下就可以发现并不是，拿9举个：3是9的完全平方因子，在3以上的数字一定不能构成完全平方因子，因为开平方一定超过最大数字9了。如此一来，我们只用考虑3之前的。
不难发现，3之前的1、2是必然满足完全平方因子的，因为它们做平方，一定小于3的平方，也就一定在数据范围内。
基于上面的分析，我们可以看出，灯泡亮的个数，就是n的平方根向下取整个，代码就一行：
return (int)math.sqrt(n)
06灯泡复盘其实在面试中，遇到这种数学模型的题，是很容易翻车的。如果只是干想，在面试紧张的环境下，很可能大脑一片空白。 不过，这种题的套路也是有的，基本都可以用先实验，再猜测，再论证的方式去解决，这个不仅仅是面试套路，也是一种很优秀的做事情的模式。
增强电动汽车锂电池性能的魔术材料：石墨烯海绵，假石墨烯电池
Windows 10X将明年上线，初期不支持win32应用
人工智能六大领域助力实体经济落地
高通支持捷途汽车和腾讯车企打造数字座舱体验
第一届云帆杯人体感知毫米波雷达应用设计大赛即将启动
有趣的算法题热热身：灯泡开关
Wacom宣布与Magic Leap达成合作,共同开发MR环境中的多人协作系统
Sprint预测5G会为中国手机厂商提高知名度
深圳金融学界积极探索“负责任”的金融创新
宝马集团与华友循环打造动力电池材料闭环回收与梯次利用的创新合作模式
荣耀9什么时候上市？荣耀9最新消息：6月12日发布，配置、渲染图、价格、代言人早知道
高附加值领域保持领先优势 长电科技2022年加速技术升级转型
如何争当区块链的领头羊
IBM下一代LinuxONE服务器可省75%能耗
带有负载管理器的交流发电机充电和配电系统设计实例（一）
MAX4617-MAX4619低电压、CMOS模拟多路复用器/开关
企业并没有意识到它们对物联网的采用给IT和云安全带来了风险
电子白板的复制速度/复印系统
“互联网+”走进新能源汽车行业 解决一车多卡问题
关于 4G/5G 智能手机天线调谐的 4 点须知
对某个灯泡切换开关意味着：如果灯泡状态为关闭，那该灯泡就会被开启；而灯泡状态为开启，那该灯泡就会被关闭。
第 1 轮，每个灯泡切换一次开关。即打开所有的灯泡。
第 2 轮，每两个灯泡切换一次开关。即每两个灯泡关闭后一个。
第 3 轮，每三个灯泡切换一次开关。即位于第3、6、9···的灯泡切换开关。
第 i 轮，每 i 个灯泡切换一次开关。而第 n 轮，你只切换最后一个灯泡的开关。
找出 n 轮后有多少个亮着的灯泡。
示例 1：
输入：n = 6 输出：2
02问题分析
通过上面的图例，我们可以很清楚地看到，每一轮都会切换一批灯泡。关键是可能切换到之前已经切换过的灯泡，如果我们通过模拟来暴力解决，那么每一轮就要遍历一次，肯定超时。
那我们换种思路想想，这道题似乎更像一道有数学规律的题，这种类型在面试中也不少见。
不过我们不一定能马上找到规律，那也不要着急，就按部就班：用0表示off, 1表示on，先列出前10个灯泡的答案，看看其中有什么规律可循。
n=1：1
n=2：1 0
n=3：1 0 0
n=4：1 0 0 1
n=5：1 0 0 1 0
n=6：1 0 0 1 0 0
n=7：1 0 0 1 0 0 0
n=8：1 0 0 1 0 0 0 0
n=9：1 0 0 1 0 0 0 0 1
n=10: 1 0 0 1 0 0 0 0 1 0
03发现规律
我们仔细看看上面的数据就会发现，最后亮灯的位置都在第1、4、9位上，这些位置恰好都是某个因子的平方，比如4，就是2的平方，不知道大家还记得不，在数学上这种数字就叫做完全平方数。
那我们就可以大胆猜测：最后亮灯的位置，都是完全平方数。那么每多一个完全平方数，就多一个亮的灯泡。
当然，这只是一个猜测，我们可以用暴力法写一个程序，把前100个的情况打印出来，就能看出，是满足这个规律的。
都已经验证到100轮了，那么基本就是这个规律了。
所以这道题，其实就是寻找n以内有多少个完全平方数，具体做法是从数字1遍历到数字n，对每个数字判断是否是完全平方数，最差也是o(n)可以解决。
04思考缘由
牛牛是个打破砂锅问到底的人，虽然通过规律，解决了问题，但是不搞清楚为什么，总是心里痒痒的。
我们从上面的规律，可以猜测灯泡亮的数量一定和平方根的特性有关系的。
我们先看看一些非完全平方数：
8的因子: 1 2 4 8；
12的因子：1 2 3 4 6 12；
这些因子一定是偶数个，为什么呢？
因为一个因子，一定是和另一个因子，配合起来，才能得到这个数字。
回到我们的灯泡，比如我们拿n=3的情况来说，第一轮打开了第三轮的灯泡，第三轮就会给它关掉，因为1、3是3的成对因子。
但如果是n=4的情况，1、4虽然也会成对抵消，但是第二轮的操作却无法抵消，因为2的成对因子是2，不会再重复出现。
从这里我们就可以看出来，每增加一个完全平方数，就会多一个不会被抵消掉的因子出现，所以个数也就增加了1。
05更进一步
一般的算法题，o(n)就是性能的极致，但这是一道数学规律题，那我们就得多想想还有没有更快的办法。
要找到有多少个完全平方数，是否一定要遍历完1-n？
稍微思考下就可以发现并不是，拿9举个：3是9的完全平方因子，在3以上的数字一定不能构成完全平方因子，因为开平方一定超过最大数字9了。如此一来，我们只用考虑3之前的。
不难发现，3之前的1、2是必然满足完全平方因子的，因为它们做平方，一定小于3的平方，也就一定在数据范围内。
基于上面的分析，我们可以看出，灯泡亮的个数，就是n的平方根向下取整个，代码就一行：
return (int)math.sqrt(n)
06灯泡复盘其实在面试中，遇到这种数学模型的题，是很容易翻车的。如果只是干想，在面试紧张的环境下，很可能大脑一片空白。 不过，这种题的套路也是有的，基本都可以用先实验，再猜测，再论证的方式去解决，这个不仅仅是面试套路，也是一种很优秀的做事情的模式。
增强电动汽车锂电池性能的魔术材料：石墨烯海绵，假石墨烯电池
Windows 10X将明年上线，初期不支持win32应用
人工智能六大领域助力实体经济落地
高通支持捷途汽车和腾讯车企打造数字座舱体验
第一届云帆杯人体感知毫米波雷达应用设计大赛即将启动
有趣的算法题热热身：灯泡开关
Wacom宣布与Magic Leap达成合作,共同开发MR环境中的多人协作系统
Sprint预测5G会为中国手机厂商提高知名度
深圳金融学界积极探索“负责任”的金融创新
宝马集团与华友循环打造动力电池材料闭环回收与梯次利用的创新合作模式
荣耀9什么时候上市？荣耀9最新消息：6月12日发布，配置、渲染图、价格、代言人早知道
高附加值领域保持领先优势 长电科技2022年加速技术升级转型
如何争当区块链的领头羊
IBM下一代LinuxONE服务器可省75%能耗
带有负载管理器的交流发电机充电和配电系统设计实例（一）
MAX4617-MAX4619低电压、CMOS模拟多路复用器/开关
企业并没有意识到它们对物联网的采用给IT和云安全带来了风险
电子白板的复制速度/复印系统
“互联网+”走进新能源汽车行业 解决一车多卡问题
关于 4G/5G 智能手机天线调谐的 4 点须知