题意解读+详细题解-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);
    }
};

相关文章

全国计算机一级考试里的发送邮件怎么弄

全国计算机一级考试里的发送邮件怎么弄

1、从电脑上打开“Outlook Express”。 2、单击"工具栏&#...

MimoLive for Mac(视频直播制作软件)兼容big sur

MimoLive for Mac(视频直播制作软件)兼容big sur

如果您是一名博客主,怎能错过这款转为播客们设计的视频制作工具mimoLiv...

变量提升 、隐式全局变量和局部变量

f1(); 调用函数 function f1(){    //自定义函数 var a...

移动端测试

1.uiautomatorviewer定位工具 1.进入sdk目录下的tools目录&...

中央网信办:集中整治网络暴力、网络水军、网络黑公关方面问题

2022-08-23 16:45:10 国务院新闻办公室于8月23日下...

发表评论    

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