热门标签 | HotTags
当前位置:  开发笔记 > 开放平台 > 正文

JavaScript实现twitterpuddles算法实例_javascript技巧

这篇文章主要介绍了JavaScript实现twitterpuddles算法实例,本文源自twitter的一道面试题,本文使用js解开了这首题,需要的朋友可以参考下
今天发现了一个挺好玩的算法题,下面是它的算法描述,源自twitter的一道面试题。

twitter puddles 算法描述

先看一副图

上图里的数字是根据一个数组内容来描述的,最后会根据每个数字的大小来模拟一道墙的高度,最后生成一面墙,问你,当下雨的时候,这面墙可以装多少水,以1为计数单位。

下面是装完水之后的一面墙的样子

看完上面上幅图,感觉是不是很好玩,确实,下面来简单的分析下它的算法实现

其实这个原理比较简单,总共有下面几个要点:

1.最左边和最右边肯定不能装水
2.装水的高度依赖自身左右两侧内两个最大值其中的最小值

下面我们用js来简单的实现它:

代码如下:


/**
* 计算以数组项为高度的墙能装多少水
* 数组例子 [2,5,1,2,3,4,7,7,6,9]
**/
function getWaterCounts(arg){
var i = 0,
j = 0,
count = 0;
// 第一项和最后一项都得排除
for(i = 1; i var left = Math.max.apply(null, arg.slice(0, i + 1));
var right = Math.max.apply(null, arg.slice(i, arg.length));
var min = left >= right ? right : left;
// 以左右两边最大值内小的为准
// 假如当前值大于或者等于这个值什么都不做
if(arg[i] count += min - arg[i];
}
}
console.log(count);
}
getWaterCounts([2,5,1,2,3,4,7,7,6,9]); // 11

总结

嘿嘿,实现是不是挺简单的,其实只要你愿意思考,用js可以实现很多好玩的东西.

推荐阅读
author-avatar
哚菟菟_336
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有