首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX  ›  程序员

LeetCode 319 - 灯泡开关

  •  
  •   Northxw · 53 天前 · 888 次点击
    这是一个创建于 53 天前的主题,其中的信息可能已经有所发展或是发生改变。

    题目描述: 初始时有 n 个灯泡关闭。 第 1 轮,你打开所有的灯泡。 第 2 轮,每两个灯泡你关闭一次。 第 3 轮,每三个灯泡切换一次开关(如果关闭则开启,如果开启则关闭)。第 i 轮,每 i 个灯泡切换一次开关。 对于第 n 轮,你只切换最后一个灯泡的开关。 找出 n 轮后有多少个亮着的灯泡。示例:

    输入: 3
    输出: 1 
    解释: 
    初始时, 灯泡状态 [关闭, 关闭, 关闭].
    第一轮后, 灯泡状态 [开启, 开启, 开启].
    第二轮后, 灯泡状态 [开启, 关闭, 开启].
    第三轮后, 灯泡状态 [开启, 关闭, 关闭].
    

      你应该返回 1,因为只有一个灯泡还亮着。

    我的疑惑

      谷歌百度一大堆解题思路,只有两个让我比较心仪的答案。一个时 CSDN 某博主在 2015 年写的,跳跃太大,我一时半会理解不了; 一个是力扣英文区本题评论区的精选评价,奈何谷歌翻译也会出现牛头不对马尾的语法,搞的我不知道该怎么去理解。

      虽然在整体上对本题已经有了自己的认识,但是总感觉心里有疑惑点,好像差点什么,我自认为自己还没有搞懂这道题。 希望大家能帮我解答疑惑,分析的时候麻烦尽量详细点。

    最后

      我贴出力扣英文区该题的链接: https://leetcode.com/problems/bulb-switcher/discuss/77112/Share-my-o(1 小弟愚钝,恳请解惑。

    9 回复  |  直到 2019-03-29 17:45:38 +08:00
        1
    qwertyegg   53 天前   ♥ 1
    对于一个整数 i,如果不是 perfect square(4, 9, 16...),那么他的因子一定是成对(偶数个)出现的,比如 6 的因子是 1,2,3,6

    而 perfect square 的因子是奇数个,比如 16 的因子是 1, 2, 4, 8, 16

    实际上就是数[1, n]之间有多少个 perfect square number,数量是 floor(log(n))
        2
    Northxw   53 天前
    @qwertyegg emmm... 这算是翻译了一遍重要部分吗?
        3
    petelin   53 天前 via iPhone
    这题最后有一个地方很有意思 比 n 小的所有完美平方数的个数就是 n 的平方
        4
    petelin   53 天前 via iPhone
    感谢一楼 很简洁 其实就是 任何一个数 都能被拆开成 n 对数相乘 这个题正好一对是一开一关结果为关
    但是为什么最后还有开着的?因为有完全平方数比如 2×2 只开了一次对应的关不会操作 所以只有完全平方数是开着的
        5
    yippees   53 天前
    大概查了下
    https://blog.csdn.net/camellhf/article/details/52819154
    首先观察题目给的例子,结合题意,很自然就能想到,一个开关 i 被拨动的次数就是 i 的约数的个数,比如第 8 个开关,它被拨动了 4 次,分别在轮数=1,2,4,8 时,而 1,2,4,8 就是 8 的约数。
    所以题目就变成了求 1-n 中每个数 i 的约数个数,统计约数个数是奇数的数目,因为如果约数个数是奇数,则开关是开的。
    那么下一步就是求 i(i≤n)的约数个数,想到这里,要发现一点,约数是成对存在的,即 2 是 8 的约数,那么 8÷2=4

    也是 8 的约数,其中有一种特殊情况,就是 i 为完全平方数,比如 9 跟它的约数 3,因此,
    如果 i 是完全平方数,那么 i 的约数个数肯定是奇数,如果 i 不是完全平方数,由于约数成对出现,所以约数个数肯定是偶数。
    想出了这一点,这道题就变成了更简单的题目:计算 1-n 中完全平方数的数目,到这里就不用我继续讲了吧。

    ——————华丽的分割线————————–
    以上是我 10 分钟前的想法,然而在这洗澡的 10 分钟里,我突然想到了小于等于 n 的平方数的数目就是直接对 n 的平方根取整数,所以最佳的答案只需一行,直接返回对 n 的平方根的取整。

    //我也只是大约想到约数 完全平方数··
        6
    Northxw   53 天前
    @petelin 谢谢啦
    @yippees 谢谢啦
        7
    widewing   52 天前 via Android
    等等。。这难道不是求小于 n 的质数个数吗?
        8
    Northxw   52 天前
    @widewing 不是的
        9
    smdbh   52 天前
    从暴力双循环慢慢优化,就有了 1 楼的答案
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   909 人在线   最高记录 5043   ·  
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 18ms · UTC 19:18 · PVG 03:18 · LAX 12:18 · JFK 15:18
    ♥ Do have faith in what you're doing.
    沪ICP备16043287号-1