LeetCode---Bulb Switcher解题分析

本文主要是介绍LeetCode---Bulb Switcher解题分析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意描述：给定n个灯泡，初始化全为off，第一趟全问部on，第二趟将每第二个off，第三趟将每第三个反转……第n趟将第n个反转，最后返回灯泡处于on的数目。给定n=3，则有以下过程：

开始时，3个灯泡[off, off, off]；第一轮，3个灯泡[on, on, on]；第二轮，3个灯泡[on, off, on]；第三轮，3个灯泡[on, off, off]。所以最后返回1

解题思路一：该方法最容易想到，就是依次判断各个灯泡的最终状态，然后返回灯亮的个数。可以发现当n=1,2,3时都返回1；从4开始，依次判断当前灯是否亮，如果亮则计数加1

int bulbSwitcher(int n) {if(n <= 0)return 0;int res = 1;for(int i=4; i<=n; i++){if(isOn(i))res++;}return res;
}
boolean isOn(int k){//判断第k个灯是否亮着//判断的方法就是从2到当前数k，如果出现k的因子，则其状态反转一次boolean flag = true;for(int i=2; i<=k; i++){if(k % i == 0)flag = !flag;}return flag;
}

解题思路二：上面的解题思路没有用到灯泡数n与反转次数的关系，从而导致了当n过大时运行超时，观察上面运行的结果：[1,3]---1;  [4,8]---2;  [9,15]---3;  [16,24]---4;  [25,35]---5；……发现从[i,i*(i+2)]---i

int bulbSwitcher2(int n){if(n <= 0)return 0;elsereturn (int)Math.sqrt(n);
}

这篇关于LeetCode---Bulb Switcher解题分析的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---