之前在群里有人讨论Twitter的面试题，蓄水池蓄水量计算，于是自己写了个JS版的(PS:主要后台代码还要编译，想想还是JS快，于是就使用了JS了。不过算法主要还是思路嘛，而且JS应该都没问题吧^_^;)
这里是题目：
---------------------------分割线------------------------
蓄水池储水量问题
看图，可以将方块看做砖。题干很简单，问最多能放多少水。例如，图2就是图1可放的最多水（蓝色部分），如果将一块砖看做1的话，图2就是能放10个单位的水。图3可以放17个单位的水。上面每一个图的砖墙用int数组表示，每一个数组元素表示每一列砖墙的砖数（高度）。
(图1)
(图2)
(图3)
---------------------------我又来了------------------------
一开始我觉得挺简单，但是结果用了我一下午。 (╯°Д°)╯︵ ┻━┻坑爹啊这是！！！！
我代码我已经加上了每步的注释，相信各位应该是能很快的看懂的。(｡・`ω´･)
好了，废话我不多说了，上代码。(σ｀・д･)σ
<!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">
<head>
<title></title>
<script src="../Script/jquery-1.9.1.min.js" type="text/javascript"></script>
<script type="text/javascript">
//来自：http://www.cnblogs.com/cielwater
//开始值
var StartMax = 0;
//开始值位置
var StartIndex = 0;
//最小值
var MinNum = 0;
//最小值位置
var MinIndex = 0;
//结束值
var EndMax = 0;
//结束值位置
var EndIndex = 0;
$(document).ready(function () {
//初始值
var List = "12134565548";
$("body").append(List + "<br>");
//调用计算函数
ShuiChi(List);
});
//计算函数
function ShuiChi(Item) {
StartMax = Item[0];
StartIndex = 0;
MinNum = Item[0];
MinIndex = 0;
EndMax = Item[0];
EndIndex = 0;
//循环水池
for (var i = 0; i < Item.length; i++) {
//获取各种条件
if (StartMax <= Item[i] && MinNum == StartMax) {//判断是否为第一次碰到比之前大的值
//记录开始值
StartMax = Item[i];
//记录开始值位置
StartIndex = i;
//保存到结束值，用于之后的判断
MinNum = Item[i];
//保存结束值位置，用于之后的判断
MinIndex = i;
} else if (MinNum > Item[i]) {//判断是否比结束值还小
//将结束值赋予给开始值
StartMax = MinNum;
//将结束值位置赋予给开始值位置
StartIndex = MinIndex;
//保存新的结束值
MinNum = Item[i];
//保存新的结束值位置
MinIndex = i;
} else if (MinNum < Item[i]) {//判断是否比结束值大
//保存结束值
EndMax = Item[i];
//保存结束值位置
EndIndex = i;
}
//判断是否已经包含结束值，并且结束位值和开始位值位置相隔1以上
if (EndIndex > StartIndex + 1) {
//循环替换开始位值与结束位置的值
for (var j = StartIndex; j < EndIndex - 1; j++) {
//三元运算判断开始值与结束值，最小的值替换指定位置
Item = Item.substring(0, j + 1) + (EndMax < StartMax ? EndMax : StartMax) + Item.substring(j + 2, Item.length);
}
//递归
ShuiChi(Item);
//终止当前运算
return false;
}
}
//输出结果
$("body").append(Item + "<br>");
}
</script>
</head>
<body>
</body>
</html>
下面放出一段别人的代码，虽然我没怎么看过不过是给各位去看的。
多看看各种思路嘛(●'ω'●)丿❤
package a;
public class Test {
static int result = ; // 最终结果
static int[] wallHeights = new int[] { , , , , , , , , }; // 表示所有的墙的高度 public static void process(int start, int end) {
// first：start和end之间最高的墙
// second：start和end之间第二高的墙
int first = , second = ;
// firstIndex：第一高的墙在wallHeights中的索引
// secondIndex：第二高的墙在wallHeights中的索引
int firstIndex = , secondIndex = ;
// 两堵墙必须至少有一堵墙的距离
if (end - start <= )
return;
// 开始获取第一高和第二高墙的砖数
for (int i = start; i <= end; i++) {
if (wallHeights[i] > first) {
second = first;
secondIndex = firstIndex;
first = wallHeights[i];
firstIndex = i;
} else if (wallHeights[i] > second) {
second = wallHeights[i];
secondIndex = i;
}
} // 获取左侧墙的索引
int startIndex = Math.min(firstIndex, secondIndex);
// 获取右侧墙的索引
int endIndex = Math.max(firstIndex, secondIndex);
// 计算距离
int distance = endIndex - startIndex;
// 如果第一高的墙和第二高的墙之间至少有一堵墙，那么开始计算这两堵墙之间可以放多少个单位的水
if (distance > ) {
result = result + (distance - ) * second;
// 减去这两堵墙之间的砖数
for (int i = startIndex + ; i < endIndex; i++) {
result -= wallHeights[i];
} }
// 开始递归处理左侧墙距离开始位置能放多少水
process(start, startIndex);
// 开始递归处理右侧墙距离结束位置能放多少水
process(endIndex, end);
}
public static void main(String[] args) {
process(, wallHeights.length - );
System.out.println(result);
}
}
以前没怎么写太多算法，突然想写个结果花了一下午。┬─┬ ノ( ' - 'ノ) 摆好。(╯‵□′)╯︵┴─┴再丢一次！坑爹啊！！！自己都赶脚很坑爹了。看来以后得要多去看看一些算法思路了。
如果各位觉得还要一个C#的话，我以后会补上一个C#的。就到这，各位拜拜。