成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

leetcode 319. Bulb Switcher

pkhope / 3162人閱讀

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

題目要求 
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個初始狀態(tài)為關(guān)閉的燈泡。第一次打開所有燈泡，第二次每隔一個燈泡關(guān)閉一個燈泡，第三次每隔兩個燈泡按一下開關(guān)。依次類推，問第n次之后開著的燈泡的數(shù)量有幾個？

思路和代碼

首先舉幾個例子來找一下其中的規(guī)律。我們用0代表關(guān)閉的燈泡，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個
...

可以看到，數(shù)量的變化發(fā)生于n為完全平方數(shù)的時候。

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

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


想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號！將會不定期的發(fā)放福利哦~

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/68779.html

相關(guān)文章

  • LeetCode 319 燈泡開關(guān)[數(shù)學(xué)] HERODING的LeetCode之路

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

    liujs 評論0 收藏0

  • 總結(jié)常用偽類與偽元素

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

    anRui 評論0 收藏0

  • 設(shè)計模式--簡化解釋(三)——行為型模式

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

    cangck_X 評論0 收藏0

  • [譯] React.js 模式

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

    mumumu 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<