2020字节跳动技术编码考核题

朋友面试字节跳动-头条的技术笔试水坑积水的问题。感觉很有趣。试着用自己的javascript知识提供一些解题算法思路。

有一组不同高度的台阶,由一个整数数组表示,数组中每个数是台阶的高度。当开始下雨了(足够多),台阶之间的水坑会积多少水呢?

如下图,可以表示为数组[0,1,0,2,1,0,1,3,2,1,2,1],返回积水量6。

解题思路:

1 什么样的条件才能积水?

  有凹的地方才能积水。

2 怎么判定凹?

  左右凸起中间低即为凹。

3 只有两种状态是否可用二进制表示?

  可以1凸0为凹,左右两边边界为凹时不考虑。

图例

以上图例,凹地分别是A,C,E,凸地分别是B,D

但A,E为边界,不能计为有效凹地

即此例中只有C能积水一个单位

如何计算台阶的高度影响

图例

B为整数3时,计算为1+1+1=3,D为整数2时计算为1+1=2

则可以将深度分别拆开计算

第一层:01010=101统计为一个0

第二层:01010=101统计为一个0

第三层:01000=1统计为没有0

此图例中积水量等于2,

即第一层有效0的数量加第二层有效0的数量加第三层有效0的数量。

JS编码方案

将每一层的数据转成二进制,去掉边界无效的0,统计剩下的每一层0的数量,进行总和即为实际积水量。

<script language="javascript">
var ArrA=[0,1,0,2,1,0,1,3,2,1,2,1];//台阶的描述数组
var N=function (){
	var Result=0,aMax=Math.max.apply(Math,ArrA),ArrB;
	//Result:积水量的统计变量。aMax:台阶的最高值,ArrB:每层台阶转化1,0的临时存放数组。
	for(i=1;i<= aMax;i++)//循环每一层
		{
			ArrB=[];
	        for(x = 0; x < ArrA.length;x++)//循环每层所有的数并将其转化为0,1
			{
				if(ArrA[x] >= i) ArrB.push(1);
				else ArrB.push(0);
			}
			ArrB = ArrB.slice(ArrB.indexOf(1),ArrB.lastIndexOf(1)+1);//去掉左右边界无效的0。
			Result = Result+ArrB.join().split(0).length-1;//累加此层剩余有效0的数量
		}
		alert(Result);
	}();
</script>

发表评论

电子邮件地址不会被公开。