leetcode 319. Bulb Switcher

pkhope 發布于2019-08-15 14:43 / 3153人閱讀

摘要：我們用代表關閉的燈泡，代表開啟的燈泡個個個個個個個個個可以看到，數量的變化發生于為完全平方數的時候。那么什么時候會是開啟，也就是其因數的個數為奇數呢即該燈泡的位置為完全平方數的時候。因此這道題目最終被轉化為求之前一共有多少個完全平方數。

題目要求

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 ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb. Find how many bulbs are on after n rounds.

Example:

Given n = 3. 

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個初始狀態為關閉的燈泡。第一次打開所有燈泡，第二次每隔一個燈泡關閉一個燈泡，第三次每隔兩個燈泡按一下開關。依次類推，問第n次之后開著的燈泡的數量有幾個？

思路和代碼

首先舉幾個例子來找一下其中的規律。我們用0代表關閉的燈泡，1代表開啟的燈泡：
n=1 1 1個
n=2 10 1個
n=3 100 1個
n=4 1001 2個
n=5 10010 2個
n=6 100100 2個
n=7 1001000 2個
n=8 10010000 2個
n=9 100100001 3個
...

可以看到，數量的變化發生于n為完全平方數的時候。

我們繼續尋找為什么會出現這樣的情況。
一個燈泡最后的狀態，其實取決于它的因數的個數，比如2=1*2則第二個燈泡將在第一輪是被開啟，在第二輪時被關閉。在比如8=1*8=2*4 則該燈泡會在第一輪時被開啟，第二輪關閉，第四輪開啟，第八輪關閉。因此8最后的狀態也是關閉的。可見當其因數的個數為偶數時，該燈泡最終的狀態必然是關閉的。那么什么時候會是開啟，也就是其因數的個數為奇數呢？即該燈泡的位置為完全平方數的時候4=1*4=2*2,9=1*9=3*3。因此這道題目最終被轉化為求n之前一共有多少個完全平方數。

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

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

云服務器 GPU云服務器 Bulb Switcher Leetcod LeetCode

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/68779.html

LeetCode 319 燈泡開關[數學] HERODING的LeetCode之路

摘要：解題思路這題本質就是數學，需要分析，每個燈泡會被翻轉的時機正好是他的約數次遍歷的時候，那么我們其實知道，對于每個數的約數都是成對出現的，除非是完全平方數，會有奇數個約數，所以，最后完全平方數的燈泡會亮，題目也就變成了找 ...

liujs 2021-11-16 11:45 評論0 收藏0
總結常用偽類與偽元素

摘要：總結常用偽類與偽元素偽類和偽元素是為了格式化樹以外的信息而被引入的。偽類一個偽類是以一個冒號作為前綴，被添加到一個選擇器末尾的關鍵字，可以讓指定的元素在特定的狀態呈現指定的樣式。總結常用偽類與偽元素偽類和偽元素是為了格式化 DOM 樹以外的信息而被引入的。偽類一個 CSS 偽類是以一個冒號(:)作為前綴，被添加到一個選擇器末尾的關鍵字，可以讓指定的元素在特定的狀態呈現指定的樣式...

anRui 2019-08-30 10:50 評論0 收藏0
設計模式--簡化解釋(三)——行為型模式

摘要：創建型設計模式結構型設計模式行為型設計模式行為型設計模式簡而言之行為型設計模式關心的是對象之間的責任分配。這種模式被認為是一種行為模式，因為它可以改變程序的運行行為。 1.創建型設計模式2.結構型設計模式3.行為型設計模式行為型設計模式簡而言之行為型設計模式關心的是對象之間的責任分配。它們與結構模式的不同之處在于，它們不僅指定了結構，而且還概述了它們之間消息傳遞/通信的模式。換句...

cangck_X 2019-08-16 11:10 評論0 收藏0
[譯] React.js 模式

摘要：此時，我將它寫下來討論和分享這些我發現的模式。正確的姿勢應該是通過的方式獲取子組件的一些信息。高階組件是需要另外一個有用的模式依賴注入。也有部分人稱它是一種模式。最直接的方式是通過每一層通過來傳遞。原文出自：http://krasimirtsonev.com/blog/article/react-js-in-design-patterns 前言我想找一個好的前端前端框架，找了很久。...

mumumu 2019-08-20 10:50 評論0 收藏0