LeetCode 319. Bulb Switcher.jpg
LeetCode 319. Bulb Switcher
Description
There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the i-th round, you toggle every i bulb. For the n-th round, you only toggle the last bulb. Find how many bulbs are on after n rounds.
Example:
Input: 3
Output: 1
Explanation:
At first, the three bulbs are [off, off, off].
After first round, the three bulbs are [on, on, on].
After second round, the three bulbs are [on, off, on].
After third round, the three bulbs are [on, off, off].
So you should return 1, because there is only one bulb is on.
描述
初始時有 n 個燈泡關(guān)閉膳凝。 第 1 輪辛辨，你打開所有的燈泡。 第 2 輪彻坛，每兩個燈泡你關(guān)閉一次。 第 3 輪，每三個燈泡切換一次開關(guān)（如果關(guān)閉則開啟亮瓷，如果開啟則關(guān)閉）琴锭。第 i 輪晰甚，每 i 個燈泡切換一次開關(guān)。 對于第 n 輪决帖，你只切換最后一個燈泡的開關(guān)厕九。 找出 n 輪后有多少個亮著的燈泡。
示例:
輸入: 3
輸出: 1
解釋:
初始時, 燈泡狀態(tài) [關(guān)閉, 關(guān)閉, 關(guān)閉].
第一輪后, 燈泡狀態(tài) [開啟, 開啟, 開啟].
第二輪后, 燈泡狀態(tài) [開啟, 關(guān)閉, 開啟].
第三輪后, 燈泡狀態(tài) [開啟, 關(guān)閉, 關(guān)閉].
你應(yīng)該返回 1地回，因?yàn)橹挥幸粋€燈泡還亮著扁远。
思路
- 數(shù)學(xué)題，對給定的數(shù)字開平方向下取整即是答案刻像。
- 暴力求解（會超時）畅买，但是通過暴力解法可以發(fā)現(xiàn)規(guī)律。我們聲明一個長度為 n 的數(shù)組细睡，數(shù)組初始值為 0 谷羞。然后我們按照題目要求對其進(jìn)行改變狀態(tài)的操作，0 表示關(guān)溜徙，1 表示開湃缎。我們通過這個會發(fā)現(xiàn)如果給定的 n 為前三個數(shù)（1~3）會有 1 盞燈亮著，如果給定的 n 為接下來的 5 個數(shù) （4~8）蠢壹，會有 2 盞燈亮著嗓违，接下來的 7 個數(shù)（9~15）會有3 盞燈兩者，我們稱給定的所有可能的 n 中图贸，最后剩下相同的燈亮著的情況的 n 為一組蹂季，于是可以發(fā)現(xiàn)每組 n 的個數(shù)是一個首項(xiàng)為 3 公差為 2 的等差數(shù)列。
- 于是有了第一個解法：我們不斷的從 n 中減去疏日，3偿洁，5，7 ... （n 小于零就停止）沟优，能減少多少次就有多少盞燈亮著父能。
- 我們可以發(fā)現(xiàn) 13：1；48：2净神；915：3，1625：4溉委，不難發(fā)現(xiàn)我們對 n 開放取整就可以得到答案鹃唯，關(guān)于嚴(yán)格的數(shù)學(xué)證明請參考 這里 。
# -*- coding: utf-8 -*-
# @Author: 何睿
# @Create Date: 2019-02-23 18:46:36
# @Last Modified by: 何睿
# @Last Modified time: 2019-02-23 19:46:07
class Solution:
def bulbSwitch(self, n: int) -> int:
return int(n**0.5)
def bulbSwitch2(self, n: int) -> int:
count, i = 0, 3
# 首項(xiàng)為3瓣喊，公差為 2 的等差數(shù)列
# n 為這些數(shù)字的和
while n > 0:
# 每次從 n 中去掉一項(xiàng)
n -= i
i += 2
# 記錄去掉的次數(shù)
count += 1
# 次數(shù)就是剩下的晾著的燈泡個數(shù)
return count
def bulbSwitch3(self, n: int) -> int:
# 最直觀的思路坡慌，用一個數(shù)組表示燈泡的開關(guān)情況，0 表示關(guān)藻三，1 表示開
# !!! 此方法會超時
bulbs = [0 for i in range(n)]
for i in range(n):
j = i
# 每輪調(diào)整 i 整數(shù)倍的位置
while j < n:
bulbs[j] ^= 1
j += i + 1
# 統(tǒng)計(jì)最后剩下的 1 的個數(shù)
return bulbs.count(1)
源代碼文件在 這里 洪橘。
?本文首發(fā)于 何睿的博客 跪者，歡迎轉(zhuǎn)載，轉(zhuǎn)載需保留 文章來源 熄求，作者信息和本聲明.
