一行代码就能解决的智力算法题

妖狐艹你老母 2021-11-17 15:01 259阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，一起学算法

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

作者 | labuladong

来源 | labuladong

今天分享一道 LeetCode 上很有意思的题目，如果理解清楚了题意，只需要一行代码就能解决。

题目来源于 LeetCode 上第 319 号问题：灯泡开关。题目难度为 Easy，目前通过率为 55.8% 。

### 题目描述 ###

初始时有 *n* 个灯泡关闭。第 1 轮，你打开所有的灯泡。第 2 轮，每两个灯泡你关闭一次。第 3 轮，每三个灯泡切换一次开关。第 *i* 轮，每 *i* 个灯泡切换一次开关。对于第 *n* 轮，你只切换最后一个灯泡的开关。找出 *n* 轮后有多少个亮着的灯泡。

**示例:**

输入: 3输出: 1 
    输出: 1

**解释:**

初始时, 灯泡状态 [关闭, 关闭, 关闭].第一轮后, 灯泡状态 [开启, 开启, 开启].第二轮后, 灯泡状态 [开启, 关闭, 开启].第三轮后, 灯泡状态 [开启, 关闭, 关闭]. 
    第一轮后, 灯泡状态 [开启, 开启, 开启].
    第二轮后, 灯泡状态 [开启, 关闭, 开启].
    第三轮后, 灯泡状态 [开启, 关闭, 关闭].

### 题目分析 ###

如果你不是很明白题目中开关的规则，可以点击下方的视频，小吴做了一组动画帮助理解题意。

首先，因为电灯一开始都是关闭的，所以某一盏灯最后如果是点亮的，必然要被按奇数次开关。

我们假设只有 6 盏灯，而且我们只看第 6 盏灯。需要进行 6 轮操作对吧，请问对于第 6 盏灯，会被按下几次开关呢？这不难得出，第 1 轮会被按，第 2 轮，第 3 轮，第 6 轮都会被按。

为什么第 1、2、3、6 轮会被按呢？因为 6 = 1×6 = 2×3。一般情况下，因子都是成对出现的，也就是说开关被按的次数一般是偶数次。但是有特殊情况，比如说总共有 16 盏灯，那么第 16 盏灯会被按几次?

16 = 1 × 16 = 2 × 8 = 4 × 4 1 × 16 = 2 × 8 = 4 × 4

其中因子 4 重复出现，所以第 16 盏灯会被按 5 次，奇数次。现在你应该理解这个问题为什么和平方根有关了吧？

不过，我们不是要算最后有几盏灯亮着吗，这样直接平方根一下是啥意思呢？稍微思考一下就能理解了。

就假设现在总共有 16 盏灯，我们求 16 的平方根，等于 4，这就说明最后会有 4 盏灯亮着，它们分别是第 1 × 1 = 1 盏、第 2 × 2=4 盏、第 3 × 3 = 9 盏和第 4 × 4 = 16盏。

我们不是想求有多少个可开方的数吗，4 是最大的平方根，那么小于 4 的正整数的平方都是在 1~16 内的，是会被按奇数次开关，最终亮着的灯。

就算有的 n 平方根结果是小数，强转成 int 型，也相当于一个最大整数上界，比这个上界小的所有整数，平方后的索引都是最后亮着的灯的索引。

所以说我们直接把平方根转成整数，就是这个问题的答案。

### 代码实现 ###

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

--------------------

**本文相关阅读推荐：**

[毕业十年后，我忍不住出了一份程序员的高考试卷][Link 1]

[一道腾讯面试题：厉害了我的杯][Link 2]

[十大经典排序算法动画与解析，看我就够了][Link 3]

[这或许是东半球分析十大排序算法最好的一篇文章][Link 4]

[面试官，我会写二分查找法！对，没有 bug 的那种！][bug]

[看《长安十二时辰》可以了解哪些算法知识][Link 5]

GitHub 标星 3w+，很全面的算法和数据结构知识

![640?wx\_fmt=png][640_wx_fmt_png]

[640_wx_fmt_jpeg]: /images/20211116/c705bcad5caf41888ac28966f7e733ce.png
[Link 1]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/91488249
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484557&idx=1&sn=739d80488fe1169a9c9ca26ecfcdfba6&chksm=fa0e6b0ccd79e21a1c2b0d99db69f6206cddddfe2367742e9de1d7d17ec35a5ce29fa4e30d63&scene=21#wechat_redirect
[Link 3]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/87910210
[Link 4]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/92825279
[bug]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485240&idx=1&sn=fbccc747b2e8558c6478171709005ff9&chksm=fa0e68b9cd79e1af5ab68d42adea0b24c7d4867069091df9e95b6f20ab57b69c4e38994a36be&scene=21#wechat_redirect
[Link 5]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485904&idx=1&sn=0eae783ce1b7c0383f41d76a269f511e&chksm=fa0e6651cd79ef47d31a0dba6909873974a964e81654cf702e3868da51fa9a695e7b9a383c1a&scene=21#wechat_redirect
[640_wx_fmt_png]: /images/20211116/2653ebc02de240288277db4cfb43101b.png