LeetCode 319. 灯泡开关

1、题目

319. 灯泡开关 - 力扣（LeetCode） https://leetcode-cn.com/problems/bulb-switcher/submissions/

2、题解

这道题第一个便是扎扎实实的暴力法，就按照这一步一步的步骤去执行即可。这里的时间复杂度是n^2。超过时间限制。
第二种解法就是找规律，其实对于找规律这种东西，我觉得我是最不擅长的，通常都是枚举之后去观察规律。这道题既然是要求最终还亮几盏灯，那么我们就对灯的状态进行判断即可。如果灯的状态不再变化，我们便记录下来他的最终状态。由此可得：

1号灯，最终亮；
2号灯，最终灭；
3，灭。
4，亮。
5到8，灭。
9，亮。
......

也就是说，n以内的完全平方数的个数就是亮灯的数量，即等于n^0.5,也就是Math.sprt(n)。如此即可。

3、代码

暴力法（超过时间限制）

class Solution {
        public int bulbSwitch(int n) {
            if(n<=0){
                return 0;
            }
            //数组用int类型，0是关闭，1是开启。n是轮数，也是灯数。
            int[] lampArray = new int[n];//初始化全是关闭
            //Round 1.开所有的灯
            for (int i = 0; i < n; i++) {
               lampArray[i]=1;
            }
            int result=n-1;//过了1轮
            if(result<=0){
                return 1;
            }
            //Round 2，每两个灯泡你关闭一次。
            int nowRound2=0;
            while (nowRound2<n){
                if(nowRound2%2!=0){//奇数
                    lampArray[nowRound2]=0;//关闭
                }
                nowRound2++;
            }
            result--;
            if(result<=0){
                return 1;
            }
            //Round 3，每3个灯泡你切换一次。3到n都是如此
            //从i开始,每i个切换一次

            int condition=3;//从3开始
            while (condition<=n){
                //执行内部的循环遍历
                int nowRoundi=0;//最终结果
                while (nowRoundi<n){
                    if((nowRoundi+1)%condition==0){//1/2/3
                        //切换
                        if(lampArray[nowRoundi]==1){
                            //开->关
                            lampArray[nowRoundi]=0;
                        }else{
                            //关-》开
                            lampArray[nowRoundi]=1;
                        }
                    }
                    nowRoundi++;
                }
                //外循环累加
                condition++;
            }
            //遍历去数一数灯有几个亮
            int num=0;
            for (int i = 0; i < n; i++) {
                if(lampArray[i]==1){
                    num++;
                }
            }
            return num;
        }
    }

规律法：

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

4、执行结果

暴力法执行结果：

image.png