C/C++教程

Leetcode 319 灯泡开关

本文主要是介绍Leetcode 319 灯泡开关,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

废话少说,开刷

今天随机一题随到一个比较好玩的题,以前经常听说这种题目,但都不是编程序解决的,所以看到这个题还是非常感兴趣的。

题目:

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

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

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/bulb-switcher
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

几个testcases:

0 --> 0
1 --> 1
2 --> 1
3 --> 1
100 --> 31

动手刷吧,这个不简单吗,弄个数组,第一轮,1个一个走一遍;第二轮2个2个走一遍;第三轮,3个3个走一遍。。。。。

5分钟,代码就出来了

    public int BulbSwitch(int n)
    {
        bool[] num = new bool[n];
        for (var i = 0; i < n; i++)
        {
            num[i] = true;
        }

        // 先来一个最基本的算法,挨个循环
        for (var i=2; i<=n; i++)
        {
            for(var j=i-1; j<n; j+=i)
            {
                num[j] = !num[j];
            }
        }

        var cnt = 0;
        for (var i = 0; i < n; i++)
        {
            if(num[i] == true)
            {
                cnt++;
            }
        }

        return cnt;
    }

 做了几个UT,上面几个case跑出来了,完美。

最后看到题目上一行小字,0<=n<=10e9,最大是10亿,测一下,发现跑不出来了 [哭]

于是回头看一下,跑了一个1万,10万,100万,到1000万,发现到1亿,UT要16秒才能出来。完犊子了。

 别想了,作为一个中等难度的题,不是这么简单的,换算法吧。

于是想到了另一个算法:

第一个灯,只有1的倍数,操作1次,亮;
第二个灯,有1和2的倍数,操作2次,灭;
第三个灯,有1和3的倍数,操作2次,灭;
第四个灯,有1、2、4的倍数,操作3次,亮;

总结:每个数字获取除了1和他自己的因数,奇亮偶灭。

想到以上想法后,再仔细一项,貌似还是行不通啊。这个针对单个数的测试会快很多,但针对所有数字的计算,还是很大的计算量。 

于是就想到了传说中的最不要脸的查表法,给部分关键数字的数据保存下来,然后按照这个关键数字往上查,关键数字以下的就直接加一个数字就完事了。

太晚了,另外除了这个以外,还想再想想有没有其他的思路。

另外发现一个奇怪的现象:

1 - 1
10 - 3
100 - 10
1,000 - 31
10,000 - 100
100,000 - 316
1,000,000 - 1000
10,000,000 - 3162
100,000,000 - 10000
1,000,000,000 - 31622

睡觉,梦里跟周公讨论讨论去。 

这篇关于Leetcode 319 灯泡开关的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!