亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

leetcode 319. Bulb Switcher

pkhope / 3208人閱讀

摘要：我們用代表關(guān)閉的燈泡，代表開啟的燈泡個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)可以看到，數(shù)量的變化發(fā)生于為完全平方數(shù)的時(shí)候。那么什么時(shí)候會(huì)是開啟，也就是其因數(shù)的個(gè)數(shù)為奇數(shù)呢即該燈泡的位置為完全平方數(shù)的時(shí)候。因此這道題目最終被轉(zhuǎn)化為求之前一共有多少個(gè)完全平方數(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個(gè)初始狀態(tài)為關(guān)閉的燈泡。第一次打開所有燈泡，第二次每隔一個(gè)燈泡關(guān)閉一個(gè)燈泡，第三次每隔兩個(gè)燈泡按一下開關(guān)。依次類推，問(wèn)第n次之后開著的燈泡的數(shù)量有幾個(gè)？

思路和代碼

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

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

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

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


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

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/68779.html

相關(guān)文章

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

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

    liujs 評(píng)論0 收藏0

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

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

    anRui 評(píng)論0 收藏0

  • 設(shè)計(jì)模式--簡(jiǎn)化解釋(三)——行為型模式

    摘要：創(chuàng)建型設(shè)計(jì)模式結(jié)構(gòu)型設(shè)計(jì)模式行為型設(shè)計(jì)模式行為型設(shè)計(jì)模式簡(jiǎn)而言之行為型設(shè)計(jì)模式關(guān)心的是對(duì)象之間的責(zé)任分配。這種模式被認(rèn)為是一種行為模式，因?yàn)樗梢愿淖兂绦虻倪\(yùn)行行為。 1.創(chuàng)建型設(shè)計(jì)模式2.結(jié)構(gòu)型設(shè)計(jì)模式3.行為型設(shè)計(jì)模式 行為型設(shè)計(jì)模式 簡(jiǎn)而言之 行為型設(shè)計(jì)模式關(guān)心的是對(duì)象之間的責(zé)任分配。它們與結(jié)構(gòu)模式的不同之處在于，它們不僅指定了結(jié)構(gòu)，而且還概述了它們之間消息傳遞/通信的模式。換句...

    cangck_X 評(píng)論0 收藏0

  • [譯] React.js 模式

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

    mumumu 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<