一、题目

2015盏灯，一开始全部熄灭，序号分别是1-2015，先把1的倍数序号的灯的开关全部按一次，然后把2的倍数的灯的开关全部按一次，然后把3的倍数的开关按一次，以此类推，最后把2015的倍数灯的开关按一次。问最后亮着的灯有多少盏？

A. 43       B. 44         C. 45      D. 46

二、解题

咋一看，这不是数学问题吗？干脆用数学解了。

先来分析一下，因为一开始的时候 2015 盏灯都是熄灭的，按一次灯就开了， 按两次灯就熄灭了，由此可以知道只有按过奇数次的灯才可能是亮着的，题目中还有一个信息，就是把 1 的倍数的灯按一次，把 2 倍数的灯按一次，把 3 倍数的灯按一次，如此类推，这不就是求每个数的公约数吗？因此结合第一第二个条件，我们就可以把题目演化成求1-2015中有哪些数的公约数是奇数个的。如：1 ， 4， 9 ， 16..... (注：一个数的约数必然包括1及其本身) 这样算还是比较麻烦，我们可以继续把题目演化，求哪些数的公约数是奇数个其实也就是求哪些数是平方数，为什么呢？因为约数都是成对出现的,平方数是由两个相同的约数得到的,但是算个数是只算一个。偶数加奇数是奇数。所以只有平方数才有奇数个约数。最后，问题就变得很简单了，其实就是求1-2015中有多少个平方数，换个角度就是：44^2<2015<45^2,最后的答案就是 44 个，选 B 来看看PHP的实现方法如下（有优化的方案-欢迎各位拍砖） [php] /** * 开关灯的方法 */ class LightSwitch{ /* * 打开灯的编号的列表 */ public static function openList($num){ for ($i=1; $i < $num; $i++) { //循环遍历 $sqrtVal = sqrt($i); //开平方 if(intval($sqrtVal) == $sqrtVal ){ //是整数 $arr[$i] = sqrt($i); } } return $arr ?? []; //默认为空 } } $list = LightSwitch::openList(2016); echo count($list); //开灯的数量 44 echo '

';
echo '

';

print_r($list);			//打印出来符合的数组

echo '


';
//结果值如下

44
Array

(

    [1] => 1

    [4] => 2

    [9] => 3

    [16] => 4

    [25] => 5

    [36] => 6

    //......

    [1936] => 44

)

[/php]

其实这道题也就是leetcode原题【319. Bulb Switcher】，其实看看我以往发的面试题可以知道，大公司的面试题基本都是算法题，而且都是根据一些经典的算法题更改或原封不动地出的。
最后用 java 来解一下，其实就是一句话的问题。

文／fuck两点水（简书）原文链接：http://www.jianshu.com//p/d83a436a76e4
技术差并不是最悲剧的，最悲剧的是压根就不知道啥叫好技术～