LeetCode：電球スイッチャー-ランプスイッチ

Leetcode Bulb Switcher Lamp Switch

1、タイトル名

バルブスイッチャー（ランプスイッチ）

2、資格のあるアドレス

https://leetcode.com/problems/bulb-switcher/

3、タイトル内容

英語：あります n 最初はオフになっている電球。まず、すべての電球をオンにします。次に、1つおきの電球をオフにします。 3回目のラウンドでは、3つおきの電球を切り替えます（オフの場合はオン、オンの場合はオフ）。のために n 第3ラウンドでは、最後の電球のみを切り替えます。後に電球がいくつあるかを調べます n ラウンド。

中国語：n個の既存の電球は、デフォルトで閉じられています。最初のラウンドはすべてのランプを開き、2番目のラウンドはすべての偶数次の電球をオフにし、3番目のラウンドは最後のn番目のホイールトグルスイッチランプまで、3つの位置の電球すべての倍数の順序を逆にします。 n番目のホイールを決定し、いくつかのライトが明るいことを確認します。

4、問題解決方法1（TLE）

最初は、暴力の問題を解決するために使用されるコードを書き込もうとしていましたが、このコードがTLE（Time Limit Exceeded）になることは間違いありません。

Javaコードは次のとおりです。

/** * Test lamp switch * @ File name Solution.java * @ Author of the file Tsybius2014 * Create a Time @ 2016 11:11:02 PM January 7 */ public class Solution { public int bulbSwitch(int n) { if (n <= 0) { return 0 } boolean[] bulbs = new boolean[n] for (int i = 0 i < n i++) { bulbs[i] = false } for (int i = 0 i <= n / 2 i++) { for (int j = i j < n j = j + i + 1) { bulbs[j] = !bulbs[j] } } for (int i = n / 2 + 1 i < n i++) { bulbs[i] = !bulbs[i] } int counter = 0 for (boolean bulb : bulbs) { if (bulb) { counter++ } } return counter } }

5.2を解く方法

後で、もっと簡単な方法があることに気付きました。戻り値は、実際には、数値のおかげで切り捨てられた平方根nです。

説明させてください。数ごとに、正方形の数に加えて、偶数の要素があります。

6のような4つの要因があります：1×6 = 6,2×3 = 6

60の因数があるので：1×60 = 60,2×30 = 60,3×20 = 60,4×15 = 60,5×12 = 60,6×10 = 60

見てわかるように、非因子の数の二乗は常にペアで発生します。他の因子の数の平方根に加えてペアになっているため、奇数の二乗因子はごくわずかです。ランプの正方形の最後の位置にあるランプ電流スイッチングの問題については、オンにする必要があり、ランプは他の場所でオフにする必要があります。使用されている平方根関数を使用して、その平方数以下の数の下の数を計算します。

Javaコードの解決は次のとおりです。

/** * Test lamp switch * @ File name Solution.java * @ Author of the file Tsybius2014 * Create a Time @ 2016 11:11:02 PM January 7 */ public class Solution { public int bulbSwitch(int n) { return (int) (n >= 0 ? Math.sqrt(n) : 0) } }

終わり

複製：https：//my.oschina.net/Tsybius2014/blog/599157