2016滴滴出行研发工程师笔试题(亮灯问题)

  •   
  • 1001
  • php
  • 0
  • dodobook
  • 2016/12/22

一、题目

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的实现方法如下(有优化的方案-欢迎各位拍砖)

/**
* 开关灯的方法
*/
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 '<hr>';
echo '<pre>';
print_r($list);			//打印出来符合的数组
echo '<hr>';

//结果值如下
44

Array
(
    [1] => 1
    [4] => 2
    [9] => 3
    [16] => 4
    [25] => 5
    [36] => 6
    //......
    [1936] => 44
)

light_on_off

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

最后用 java 来解一下,其实就是一句话的问题。

bulb_switcher

文/fuck两点水(简书)原文链接:http://www.jianshu.com//p/d83a436a76e4

技术差并不是最悲剧的,最悲剧的是压根就不知道啥叫好技术~