leetcode 319. Bulb Switcher

pkhope 发布于2019-08-15 14:43 / 3016人阅读

摘要：我们用代表关闭的灯泡，代表开启的灯泡个个个个个个个个个可以看到，数量的变化发生于为完全平方数的时候。那么什么时候会是开启，也就是其因数的个数为奇数呢即该灯泡的位置为完全平方数的时候。因此这道题目最终被转化为求之前一共有多少个完全平方数。

题目要求

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);
    }

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

服务器托管私有云 Bulb Switcher Leetcod LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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