{"id":1974,"date":"2016-04-15T21:55:38","date_gmt":"2016-04-15T13:55:38","guid":{"rendered":"http:\/\/boweihe.me\/?p=1974"},"modified":"2016-04-15T21:55:38","modified_gmt":"2016-04-15T13:55:38","slug":"leetcode-319-bulb-switcher-%e6%99%ba%e5%95%86%e7%a2%be%e5%8e%8b%e9%a2%98","status":"publish","type":"post","link":"https:\/\/dayandcarrot.space\/?p=1974","title":{"rendered":"LeetCode 319. Bulb Switcher \u667a\u5546\u78be\u538b\u9898"},"content":{"rendered":"

There are n<\/i> bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it’s off or turning off if it’s on). For the i<\/i>th round, you toggle every i<\/i> bulb. For the n<\/i>th round, you only toggle the last bulb. Find how many bulbs are on after n<\/i> rounds.
\nExample:<\/b><\/p>\n

Given n<\/i> = 3.\nAt first, the three bulbs are [off, off, off]<\/b>.\nAfter first round, the three bulbs are [on, on, on]<\/b>.\nAfter second round, the three bulbs are [on, off, on]<\/b>.\nAfter third round, the three bulbs are [on, off, off]<\/b>.\nSo you should return 1, because there is only one bulb is on.<\/pre>\n
\u6211\u7684\u8d85\u65f6\u89e3<\/h3>\n
\u9012\u63a8\u6cd5\uff0c\u5f53\u4ecen-1\u5230n\u65f6\uff0c\u65b0\u52a0\u4e0a\u53bb\u7684\u4e00\u6b21\u64cd\u4f5c\u662f\u5224\u65ad\u4ece[1,n]\u91cc\u9762n\u7684\u56e0\u5b50\u4e2a\u6570\uff0c\u8fd9\u91cc\u8bb0\u4f5cf(n)\u597d\u4e86\uff0c\u5373a[n] = a[n-1] + f(n)
\n\u56e0\u5b50\u4e2a\u6570\u7684\u6c42\u6cd5\u53ef\u4ee5\u7cbe\u7b80\u4e00\u4e0b\u65f6\u95f4\uff0c\u6392\u96640,1,2\u8fd9\u4e09\u4e2a\u7279\u6b8a\u503c\u540e\uff0c\u8ba1\u7b97[2, sqrt(n)]\u91cc\u5934\u80fd\u6574\u9664\u7684\u6570\u7684\u4e2a\u6570\u5c31\u884c\u4e86\uff0c\u5982\u679c\u78b0\u5230\u4e2a\u5e73\u65b9\u6570\u90a3\u4e2a\u6570+1\uff0c\u4e0d\u7136\u4e2a\u6570\u5c31\u662f+2\u7684\uff08i\u80fd\u88abn\u6574\u9664\uff0c\u90a3\u4e48\u5b83\u7684\u8865\u6570n\/i\u4e5f\u884c\uff09\u3002
\n\u8fd9\u4e2a\u65b9\u6cd5\u7684\u590d\u6742\u5ea6\u561b\uff0cO(n^1.5)\u5427<\/p>\n
class Solution {\npublic:\n    int factors(int n){\n        if(n == 0){\n            return 0;\n        } else if(n == 1){\n            return 1;\n        } else if(n == 2){\n            return 2;\n        }\n        int count = 2;  \/\/1\u548c\u81ea\u5df1\n        int sqr = (int)(sqrt(n));\n        for(int i=2; i <= sqr; i++){\n            if(n % i == 0){\n                if(i *i == n)\n                    count += 1; \/\/\u5e73\u65b9\u6570\n                else\n                    count += 2; \/\/\u4e00\u4e2a\u6570\u548c\u5b83\u7684\u8865\u6570\n            }\n        }\n        return count;\n    }\n    int bulbSwitch(int n) {\n        if(n < 1){\n            return 0;\n        }\n        int bCount = 0;\n        for(int i=1; i<=n; i++){\n            if((factors(i)&1) == 1){\n                bCount ++;\n            }\n        }\n        return bCount;\n    }\n};<\/pre>\n
\u667a\u5546\u78be\u538b\uff0cO(1)\u89e3<\/h3>\n
\u771f\u6b63\u7684\u5965\u4e49\u7528\u4e00\u884c\u4ee3\u7801\u5c31\u80fd\u89e3\u91ca<\/p>\n
class Solution {\npublic:\n    int bulbSwitch(int n) {\n        return sqrt(n);\n    }\n};<\/pre>\n
\u5475\u5475\u54d2\uff01\u8fd9\u4e2a\u89c4\u5f8b\u5982\u679c\u591a\u8bd5\u51e0\u6b21\u8bf4\u4e0d\u5b9a\u80fd\u53d1\u73b0\uff0c0,1,1,1,2,2,2,2,2,3\u8fd9\u79cd\u6570\u5217\u561b
\nhttps:\/\/leetcode.com\/discuss\/91371\/share-my-o-1-solution-with-explanation<\/a>
\n\u5927\u6982\u610f\u601d\u662f\uff0c\u8981\u5728[1,n]\u91cc\u5934\u627e\u54ea\u4e9b\u706f\u6ce1\u88ab\u6267\u884c\u4e86\u5947\u6570\u6b21\u64cd\u4f5c<\/p>\n