題目

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

題解

本題將 對問題抽象的能力 的考察做到了極致。

思路

怎么理解(int)Math.sqrt(n)就是答案呢？

將n個開關，從1...n進行編號(一開始都是處于燈滅的狀態)；

第1輪，切換的開關為1,2,3...n
第2輪，切換的開關為2,4,6...
第3輪，切換的開關為3,6,9...
…
第n輪，切換的開關為n

反過來看：

第1棧燈，會在第1輪被切換狀態
第2盞燈，會在第1,2輪被切換
第3盞燈，會在第1,3輪被切換
第4盞燈，會在第1,2,4輪被切換
第5盞燈，會在第1,5輪被切換
第6盞燈，會在第1,2,3,6輪被切換
第7盞燈，會在第1,7輪被切換
…
第n盞燈，會在第n的因數（包括1和n）輪被切換

對于輸入n，進行n輪切換后，被切換偶數次的燈會處于和最初相同的燈滅狀態，被切換奇數次的燈會處于燈亮狀態。問題轉換為，求1,2,3,...,n中，有多少個數有奇數個因數。

由于因數都是成對出現的，因此只有完全平方數有奇數個因數。因此，<=n的數里面，有多少個完全平方數就是答案。

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

總結

以上是生活随笔為你收集整理的leetcode 319. Bulb Switcher | 319. 灯泡开关的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。