最近对算法产生了兴趣，由于读书的时候并没有怎么参与编程比赛，不免觉得有点缺憾，但是做为一个程序员，生活本来就是一场修行，需要不断提高自己的专业能力，这种缺憾还是不要留的好。leecode是个不错的平台，它对找工作比较有用，但是对于满足这种写算法题的需求也很是适合。
下面是一道计算积累多少雨水的题目；输入一个数组，输出一个值；从模型上看，问题简直简单明了，用程序来解决这个问题，不免让人跃跃欲试。
rainwatertrap
输入数组为[1,0,2,1,0,1,3,2,1,2,1];输入代表的是上图中的黑色方块；
输出为蓝色方块的数目为6；
第一眼看到这个问题，很直观的思路就是从左到右进行遍历，记录数字上升的趋势。当遇到一个下降的值的时候，表示找到一个凹点，进行结算；于是写下代码：
func trapRain(_ height:[Int]) -> Int {
if(height.count < 2) {
return 0
}
var tempHeight = height
tempHeight.append(0)
var rainWeight = 0
var index = 1
var isAsendTrend = true
var subValue:Array<Int> = Array.init()
subValue.append(tempHeight[0])
/*
几种需要进行结算的情况
1、上升趋势转变成下降趋势（相等视为不改变趋势）
2、上升趋势到最后一个元素
3、在每一个凹点的第一个和最后一个元素中取一个小值做为平均高度
eg:[0,1,0,2,1,0,1,3,2,1,2,1]
[0,1,0,1] => [0,1,0,1,0]
*/
while index < tempHeight.count {
if tempHeight[index] < tempHeight[index-1] {
if isAsendTrend {
rainWeight = rainWeight + calculateSubValue(subValue, min(subValue[0], tempHeight[index-1]))
subValue.removeAll()
subValue.append(tempHeight[index-1])
subValue.append(tempHeight[index])
}
else {
subValue.append(tempHeight[index])
}
isAsendTrend = false
}
else {
isAsendTrend = true
subValue.append(tempHeight[index])
}
index = index + 1
}
return rainWeight
}
用于结算每一个凹点的函数:
func calculateSubValue(_ subvalues:Array<Int>, _ height:Int) -> Int {
var result = 0
var index = 0
while index < subvalues.count {
if height > subvalues[index] {
result = result + height - subvalues[index]
}
index = index + 1
}
return result
}
输入测试用例[0,1,0,1],输出1，正确
再输入[0,1,0,2,1,0,1,3,2,1,2,1],输出6，正确
感觉信心满满，以为找到来正确的解法，一提交，直接显示wrong answer！！感觉被当头一棒;
研究一下导致出错的用例[3,1,2,1,2,3],
这种用上面的方法，第一次2到1的时候下降，以为找到了一个凹点[3,1,2]，实际上这个凹点只是一个局部凹点，它包含在一个更大的凹点之内。对于这样一种情况，上述算法并不能cover到！看样子要找到一种能够计算更大范围凹点的方式。
仔细想想，其实数值由上升到下降只能说找到了一个局部凹点，如果找到一个新值比之前凹点起始值还大的话，那就必然找到了一个不属于任何凹点的独立凹点。另外，可以从两头开始向中间搜索，每次递减较小的索引。写出代码：
func trapRainV2(_ height:[Int]) -> Int {
if(height.count < 2) {
return 0
}
var rainWeight = 0
var leftIndex = 0
var rightIndex = height.count - 1
var subValueLeft:Array<Int> = Array.init()
var subValueRight:Array<Int> = Array.init()
var rightStart = height[rightIndex]
var leftStart = height[leftIndex]
var isChangeLeft = true
subValueLeft.append(leftStart)
subValueRight.append(rightStart)
while(leftIndex < rightIndex) {
//左边找到第一个比起始位置大的值，结算
if height[leftIndex] >= leftStart && subValueLeft.count > 0 && isChangeLeft {
rainWeight = rainWeight + calculateSubValue(subValueLeft, min(leftStart, height[leftIndex]))
subValueLeft.removeAll()
leftStart = height[leftIndex]
subValueLeft.append(height[leftIndex])
}
//右边找到第一个比起始位置大的值，结算
if height[rightIndex] >= rightStart && subValueRight.count > 0 && !isChangeLeft {
rainWeight = rainWeight + calculateSubValue(subValueRight, min(rightStart, height[rightIndex]))
subValueRight.removeAll()
rightStart = height[rightIndex]
subValueRight.append(height[rightIndex])
}
//更新索引，每次较小的值向中间聚拢一个单位
if(height[leftIndex] < height[rightIndex]) {
//储存凹点的值
if height[leftIndex] < leftStart {
subValueLeft.append(height[leftIndex])
}
leftIndex = leftIndex + 1
isChangeLeft = true
}
else {
if height[rightIndex] < rightStart {
subValueRight.append(height[rightIndex])
}
rightIndex = rightIndex - 1
isChangeLeft = false
}
}
if subValueRight.count>1 || subValueLeft.count > 1 {
let lowHeight = min(leftStart, rightStart)
rainWeight = rainWeight + calculateSubValue(subValueLeft, lowHeight)
rainWeight = rainWeight + calculateSubValue(subValueRight, lowHeight)
}
return rainWeight
}
其实思路倒是很快就有了，但是要形成上述可以通过的代码，过程还是有点纠结的。其中一些比较的边际值调整了好几次，例如，count该大于1还是0？这种地方比较细节，但是却会影响到最终的结果。整个过程并不顺利，想想那些看到题目一遍就可以把代码写对的人，实在差距有些大，这方面还要好好磨砺啊！
网友评论