题意解读+详细题解-Leecode 319. 灯泡开关——Leecode每日一题系列

wuchangjian2021-11-15 23:18:20编程学习

今天是坚持每日一题打卡的第二十天


题目链接:https://leetcode-cn.com/problems/bulb-switcher/


题解汇总:https://zhanglong.blog.csdn.net/article/details/121071779


题目描述

初始时有 n 个灯泡处于关闭状态。第一轮,你将会打开所有灯泡。接下来的第二轮,你将会每两个灯泡关闭一个。

第三轮,你每三个灯泡就切换一个灯泡的开关(即,打开变关闭,关闭变打开)。第 i 轮,你每 i 个灯泡就切换一个灯泡的开关。直到第 n 轮,你只需要切换最后一个灯泡的开关。

找出并返回 n 轮后有多少个亮着的灯泡。

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

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

示例 2:
输入:n = 0
输出:0

示例 3:
输入:n = 1
输出:1

提示:
0 <= n <= 109


分析

题意:若有n盏灯, 第一轮将灯全部打开,第二轮将每两个灯泡关闭一个,在第三轮,每三个灯泡就切换一下灯泡的开关(注意,前三轮每轮的操作都不同)。 持续到第n轮。第三轮到第n轮的操作相同。

举例:假设有六盏灯,第一轮全部打开, 第二轮将第2,4,6盏灯关闭,第三轮将第三盏灯关闭,第六盏灯打开…

思路
第六盏灯的操作次数:分别在第1,2,3,6次操作。 6 = 1 ∗ 6 = 2 ∗ 3 6 = 1*6 = 2*3 6=16=23 我们发现,这恰好是6的全部因子。

类推到所有位置, 如第5盏灯的操作次数:分别在第1,5次操作, 5 = 1 ∗ 5 5 = 1*5 5=15

我们发现,无论是5还是6,都进行了偶数次操作, 也就是说最后的结果一定是关着的。

因此易得:如果进行了奇数次操作,最后的结果一定是开的。

进一步,我们来看4:

第四盏灯的操作次数:分别在1,2,4次操作, 4 = 1 ∗ 4 = 2 ∗ 2 4 = 1*4 = 2*2 4=14=22

易得:可以开平方的数,拥有奇数次操作,最后是开着的。

因此,只需要对n进行开平方,我们就得到了最后的结果。

class Solution {
public:
    int bulbSwitch(int n) {
        return (int)sqrt(n);
    }
};

相关文章

2021-11-14 简单排序

输入格式 共2行: 第1行为N; 第2行为N个正整数&...

4-灵魂存在与否的论证(3):自由意志、濒死体验以及笛卡尔的论证(耶鲁大学公开课-哲学-死亡)

自由意志与决定论 物理主义者认为人和机器人没有区别,人类和机器人都只是物...

发表评论    

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。