leetcode 319. Bulb Switcher | 319. 灯泡开关

àì夳堔傛蜴生んèń 2022-10-19 13:58 162阅读 0赞

## 题目 ##

[https://leetcode.com/problems/bulb-switcher/][https_leetcode.com_problems_bulb-switcher]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]

## 题解 ##

本题将 **对问题抽象的能力** 的考察做到了极致。

#### 思路 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]  
怎么理解`(int)Math.sqrt(n)`就是答案呢？

将n个开关，从`1...n`进行编号(一开始都是处于灯灭的状态)；

**第1轮，切换的开关为`1,2,3...n`  
第2轮，切换的开关为`2,4,6...`  
第3轮，切换的开关为`3,6,9...`  
…  
第n轮，切换的开关为n**

反过来看：

**第1栈灯，会在第1轮被切换状态  
第2盏灯，会在第1,2轮被切换  
第3盏灯，会在第1,3轮被切换  
第4盏灯，会在第1,2,4轮被切换  
第5盏灯，会在第1,5轮被切换  
第6盏灯，会在第1,2,3,6轮被切换  
第7盏灯，会在第1,7轮被切换  
…  
第n盏灯，会在第`n的因数`（包括1和n）轮被切换**

对于输入n，进行n轮切换后，被切换偶数次的灯会处于和最初相同的灯灭状态，被切换奇数次的灯会处于灯亮状态。问题转换为，求`1,2,3,...,n`中，有多少个数有奇数个因数。

由于因数都是成对出现的，因此`只有完全平方数有奇数个因数`。因此，`<=n的数里面，有多少个完全平方数就是答案`。

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

[https_leetcode.com_problems_bulb-switcher]: https://leetcode.com/problems/bulb-switcher/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20221004/594cd4a910e14951accfb09653c16afb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]: /images/20221004/62012000185c4c8d8c2812ef63793608.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20221004/d5f41147d70b4b07b4249fa9c47fd8ec.png