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 灯泡开关的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！