Actually it is only square root. C++ 0 ms, O(N^0.5) and O(logn) Binary Search for square root.


  • 0
    W
    class Solution {
    public:
        int bulbSwitch(int n) {return sqx(n,1,n);}
    public: int sqx(int x, int s, int e){
        if (s>e) return e;
        int m=(s+e)/2;
        if(x/m==m) return m;
        else if(x/m<m) return sqx(x,s,m-1);
    else return sqx(x,m+1,e);}};
    
    class Solution {
    public:
        int bulbSwitch(int n) {
            int i=0;
            while(i*i<=n) i++;
            return i-1;   }};

  • 0
    H
    This post is deleted!

  • 1

    解题思路:可以发现当n=1,2,3时返回1;从4开始,依次判断当前灯是否亮,如果亮则计数加1;而判断当前灯是否亮可以自定义一个函数,判断的方法就是从2到当前数k,如果出现k的因子,则其状态反转一次

    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;
    }
    

    结果发现运行超时了……但观察其运行结果,发现以下规律:
    //[1,3]---1;
    //[4,8]---2;
    //[9,15]---3;
    //[16,24]---4;
    //[25,35]---5;
    //发现从[i,i*(i+2)]---i

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

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.