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

  •   
  • 1083
  • php
  • 40
  • 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

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

  1. 这种东西不用害怕 我知道 一般白天不会出来的 晚上喜欢去别人家里 在你睡着的时候压人,如果发现要把它打死 不过很难抓到

  2. 这种东西不用害怕 我知道 一般白天不会出来的 晚上喜欢去别人家里 在你睡着的时候压人,如果发现要把它打死 不过很难抓到

  3. 这种东西不用害怕 我知道 一般白天不会出来的 晚上喜欢去别人家里 在你睡着的时候压人,如果发现要把它打死 不过很难抓到

  4. 这种东西不用害怕 我知道 一般白天不会出来的 晚上喜欢去别人家里 在你睡着的时候压人,如果发现要把它打死 不过很难抓到

  5. 这种东西不用害怕 我知道 一般白天不会出来的 晚上喜欢去别人家里 在你睡着的时候压人,如果发现要把它打死 不过很难抓到

  6. @sein 当年年少无知,在G点上用邮箱注册了无聊图这个帐号,得瑟不到两天就被封了。能帮我改个昵称不,G点登不上了。。 邮箱lambertxlc@gmail.com 能看到不?

  7. @sein 当年年少无知,在G点上用邮箱注册了无聊图这个帐号,得瑟不到两天就被封了。能帮我改个昵称不,G点登不上了。。 邮箱lambertxlc@gmail.com 能看到不?

  8. @sein 当年年少无知,在G点上用邮箱注册了无聊图这个帐号,得瑟不到两天就被封了。能帮我改个昵称不,G点登不上了。。 邮箱lambertxlc@gmail.com 能看到不?

  9. @sein 当年年少无知,在G点上用邮箱注册了无聊图这个帐号,得瑟不到两天就被封了。能帮我改个昵称不,G点登不上了。。 邮箱lambertxlc@gmail.com 能看到不?