JavaScript实现twitter puddles算法实例

2024-12-19 09:03:51

今天发现了一个挺好玩的算法题,下面是它的算法描述,源自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 < arg.length - 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] < min){
            count += min - arg[i];
        }
    }
    console.log(count);
}
getWaterCounts([2,5,1,2,3,4,7,7,6,9]); // 11

总结

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

javascript实现playfair和hill密码算法

时至期末,补习信息安全概论作业.恰巧遇古典密码学算法中的playfair算法和hill算法,用javascript语言实现起来是在有趣,边查百度边编码,顺便好好补习一下javascript基础. playfair Playfair密码(英文:Playfair cipher 或 Playfair square)是一种替换密码.依据一个5*5的正方形组成的密码表来编写,表中排列有25个字母.对于英语中的26个字母,去掉最常用的Z,构成密码表. 实现思路: 1,编制密码表密钥是一个单词或词组,密码表
Javascript中的常见排序算法

具体代码及比较如下所示: 复制代码代码如下: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml" lang="gb2312">
JavaScript blog式日历控件新算法

使用说明: 程序比较简单,代码中都有说明,这里说说怎么使用. 首先是实例化一个Calendar,并设置参数. 参数说明: Year:要显示的年份 Month:要显示的月份 SelectDay:选择日期 onSelectDay:在选择日期触发 onToday:在当天日期触发 onFinish:日历画完后触发一般SelectDay设置成选择了的日期,并在onSelectDay中设置一个函数用来设置这个日期的样式, 例如实例里SelectDay设置成今个月10号并在那天样式设为onSelect: 复
js交换排序冒泡排序算法（Javascript版）

比较相邻的元素.如果第一个比第二个大,就交换他们两个. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对.在这一点,最后的元素应该会是最大的数. 针对所有的元素重复以上的步骤,除了最后一个. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较. function sort(elements){ for(var i=0;i<elements.length-1;i++){ for(var j=0;j<elements.length-i-1;j++){ if(elemen
JavaScript生成GUID的多种算法小结

全局唯一标识符(GUID,Globally Unique Identifier)也称作 UUID(Universally Unique IDentifier) . GUID是一种由算法生成的二进制长度为128位的数字标识符.GUID 的格式为"xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx",其中的 x 是 0-9 或 a-f 范围内的一个32位十六进制数.在理想情况下,任何计算机和计算机集群都不会生成两个相同的GUID. GUID 的总数达到了2^128(3
javascript &&和||运算法的另类使用技巧

&&和||在JQuery源代码内尤为使用广泛,由于本人没有系统的学习js,所以只能粗略的自我理解出来,希望大家指点下. 粗略理解如下: a() && b() :如果执行a()后返回true,则执行b()并返回b的值:如果执行a()后返回false,则整个表达式返回a()的值,b()不执行: a() || b() :如果执行a()后返回true,则整个表达式返回a()的值,b()不执行:如果执行a()后返回false,则执行b()并返回b()的值: && 优先
javascript算法题求任意一个1-9位不重复的N位数在该组合中的大小排列序号

具体题目是这样的: 从1--9中选取N个数字,组成不重复的N位数,从小到大进行编号,当输入其中任何一个数M时,能找出该数字对应的编号.如 N=3,M=213. 输出:[123(1) , 132(2) , 213(3) , 231(4) , 312(5) , 321(6)]--->X=2 首先看到题目想到的是生成一个从少到大的全排列的数组,然后再遍历数组得到对应的序号(数组下标加1),又或者想到一个个从小到大的生成push进数组,然后判断该数是不是当前题目给的数,如果是的话要求的序号就是当前数组
Javascript和HTML5利用canvas构建Web五子棋游戏实现算法

这只是一个简单的JAVAscript和HTML5小程序,没有实现人机对战. 五子棋棋盘落子点对应的二维数组.数组的元素对应落子点.比如数组元素值为0表示该元素对应的落子点没有棋子,数组元素值为1表示该元素对应的落子点有白棋子,数组元素值为2表示该元素对应的落子点有黑棋子: 判断五子棋赢棋的算法是通过对五子棋棋盘落子点对应的二维数组的操作来实现的. 判断五子棋赢棋算法下边的函数可以实现判断五子棋赢棋的算法,也可以按照教材中相应的算法实现. 其中函数的参数xx.yy为数组下标,chess数组实现五
javascript图片相似度算法实现 js实现直方图和向量算法

复制代码代码如下: function getHistogram(imageData) { var arr = []; for (var i = 0; i < 64; i++) { arr[i] = 0; } var data = imageData.data; var pow4 = Math.pow(4, 2); for (var i = 0, len = data.length; i < len; i += 4) { var
一个简单的JavaScript 日期计算算法

复制代码代码如下: <script type="text/javascript"> var today=new Date(); //定义当天日期对象 var year = today.getYear(); //获取年份 var month = today.getMonth(); //获取月份 var date = today.getDate(); //获取日期值 try{ //定义下个日期对象,日期值加上30天 var nextDay = new Date(year,mo

JavaScript实现twitter puddles算法实例

相关推荐

随机推荐