319. 灯泡开关(java)

本文主要是介绍319. 灯泡开关(java)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

解法一(超时)

解法一会超时，但是这里要讲一下思路为正确的解法做铺垫。

思路

当我们自己写几个测试用例会发现每次需要判断只有最后一个值，也就是n的值，这个位上的灯泡到底有没有转换。
然而判断这个灯泡有没有转换我们要看看什么会导致他的值发生改变。
我们单纯考虑一个点拿n = 9来做例子，首先第1次，第9次都会改变，然后是第3次的时候会改变。总共改变了3次所以状态变了。
再考虑点n = 8，首先第1,8次都会改变；然后第2,4次会改变，总共改变了4次所以还是不变。
这时候考虑9以前已经改变了的值(1,4)进行累加就可以得到结果3。
下面的代码实现是一个时间复杂度为O(n²)的算法。

class Solution {public int bulbSwitch(int n) {if(n == 0) return 0;int res = 0;for(int i = 1;i <= n;i++){if(isSwitch(i)) res++;}return res;}public boolean isSwitch(int n){int size = 0;for(int i = 1;i <= n;i++){if(n % i == 0) size++;}if(size % 2 == 1) {return true;}return false;}
}

解法二

通过上面的分析我们可以发现，对于n只有当 n = k²的时候才可能有奇数次转换，否则都是偶数次。所以这时候我们对代码进行一点修改：时间复杂度瞬间降到O(logN)

class Solution {public int bulbSwitch(int n) {//确认 n 接近 哪个值k的平方if(n == 0) return 0;int k = 0;while(Math.pow(k+1,2) <= n){k++;}return k;}
}

解法三

通过调用jdk的方法我们可以简化为：

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

这篇关于319. 灯泡开关(java)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---