鱼C论坛Python精英挑战赛（第四季02期）

jerryxjr1220

第四届鱼C论坛精英挑战赛即将回归咯！为了增加趣味性，本届仍然延续“新玩法”-- “押宝玩法”，“竞猜玩法”和“擂主玩法”。

同时，根据以往鱼油的反馈，精英赛题目普遍偏难，所以参与的鱼油相对较少。为了提高大家的参与度，本届挑战赛会大幅降低难度，使大部分鱼油都能参赛。同时，会增设一、二、三名奖励，第一名奖励50鱼币，第二名30鱼币，第三名20鱼币。

新玩法规则：

1. 押宝玩法：由于押宝玩法参与人数很少，故暂停押宝。后续有改进玩法，会再公布。

2. 竞猜玩法：直接在比赛帖的下方进行投票，凡事“竞赛”获胜者，将奖励5鱼币。竞猜无门槛，人人都可以参与。竞猜以后，请在本帖留个言，方便领取奖励。

3. 擂主玩法：上一期挑战成功的鱼油成为挑战赛的擂主，擂主有优先权提议下一期的赛题，一届挑战赛共分5期，同一届中当擂主最长的鱼油有额外奖励。

本期题目： 可收集的最大雨水量

有一片高低起伏的洼地，洼地的海拔高度用一个列表表示，例如：[0,1,0,2,1,0,1,3,2,1,2,1]，其中每个数值代表一小块洼地的高度，每一小块洼地的宽度都是1，在洼地的凹槽处可以储存雨水，如图中蓝色部分表示可收集的雨水，黑色部分为洼地的泥土。

在这样一片洼地中，最大可收集的雨水量是6，所以程序应当返回6，若无法收集雨水，则返回0.

求给定列表中可收集的最大雨水量。

1. def max_rainwater(list_of_number):
   
2.     '''your code here'''
   
3.     return result_of_max_rainwater

复制代码

要求： 结果正确，程序效率高，代码简洁

注：给定的列表长度可能会达到1000或以上，请注意运算效率

截止日期： 12月4日24时

本期擂主： gunjang  由于本期只有算法题，所以就不给选择了

@小甲鱼 @冬雪雪冬 @～风介～ @SixPy

我用Excel写了个算法，画了张图表，希望给大家一些思路。


提供几组测试数据及答案，可以自行对照：
11        20        62        6        15        87        27        50        98        52        55        16        48        38        80        80        85        80        7        58        52        4        68        99        29        42        2        1        61        88          #答案1154
82        64        94        44        8        56        31        29        37        34        54        66        14        43        82        96        44        60        62        70        26        56        60        61        4        74        32        6        77        51        #答案1017
6        53        57        39        90        87        28        95        15        6        63        8        28        93        86        56        28        93        34        71        87        31        67        87        70        2        34        27        6        76        #答案923

竞猜：回答正确的参赛者的人数

蓝色王魂

目前只能想出这个方法，效率还行，但是代码丑。是分别计算每层的水洼面积再累加的。

1. def max_rainwater(list_of_number):
   
2.     result_of_max_rainwater = 0
   
3.     length = len(list_of_number)
   
4.     max_of_list = max(list_of_number)
   
5.     for times in range(max_of_list):
   
6.         for i in range(length):
   
7.             if list_of_number[i]>0:
   
8.                 list_of_number[i] -= 1
   
9.                 start = i
   
10.                 break
    
11.         for i in range(start+1,length):
    
12.             if list_of_number[i] > 0:
    
13.                 list_of_number[i] -= 1
    
14.                 distance = i-start-1
    
15.                 start = i
    
16.                 if distance>0:
    
17.                     result_of_max_rainwater += distance
    
18.     return result_of_max_rainwater

复制代码

SylarPu

def max_rainwater(l):
    mwater=0
    i=0
    while i<len(l)-1:
        if l[i+1]>=l[i]:
            i+=1
            continue
        m=0
        for j in range(i+1,len(l)):
            if l[j]<l[i]:
                m+=+l[i]-l[j]
            else:
                i=j
                break
        if i==j:
            mwater+=m
            continue
        i+=1
    return mwater

Elastcio

1. def max_rainwater(list_of_number):
   
2.     i = max(list_of_number)
   
3.     total_white = 0
   
4.     temp = len(list_of_number)*max(list_of_number) - sum(list_of_number)
   
5.     while i>=1:
   
6.         total_white += list_of_number.index(max(list_of_number)) + list_of_number[::-1].index(max(list_of_number))
   
7.         list_of_number = [x-1 if x == max(list_of_number)  else x  for x in list_of_number]
   
8.         i -=1
   
9.     print(temp- total_white )

复制代码

>>> max_rainwater([1,2,3])
0
>>> max_rainwater([11,20,62,6,15,87,27,50,98,52,55,16,48,38,80,80,85,80,7,58,52,4,68,99,29,42,2,1,61,88])
1154
>>> max_rainwater([82,64,94,44,8,56,31,29,37,34,54,66,14,43,82,96,44,60,62,70,26,56,60,61,4,74,32,6,77,51])
1017
>>> max_rainwater([6,53,57,39,90,87,28,95,15,6,63,8,28,93,86,56,28,93,34,71,87,31,67,87,70,2,34,27,6,76])
923
'''

shuo

1. def max_rain(lst):
   
2.         rain = 0
   
3.         lst2 = lst[:]
   
4.         while True:
   
5.                 fn = max(lst)
   
6.                 fi=lst.index(fn)
   
7. 
   
8.                 lst1 = lst[:fi]
   
9.                 if len(lst1) == 1 :
   
10.                         break
    
11.                 else:
    
12.                         sn = max(lst1)
    
13.                         si = lst1.index(sn)
    
14.                         for i in range (si,fi):
    
15.                                 rain += sn - lst[i]
    
16.                         if len(lst1) == 2:
    
17.                                break
    
18.                         else:
    
19.                                lst = lst1
    
20.         while True:
    
21.                 fn = max(lst2)
    
22.                 fi = lst2.index(fn)
    
23. 
    
24.                 lst1 = lst2[fi+1:]
    
25.                 if len(lst1) <= 1 :
    
26.                         break
    
27.                 else:
    
28.                         sn = max(lst1)
    
29.                         si = lst1.index(sn)
    
30.                         if si == 0:
    
31.                                 lst2 = lst1[:]
    
32.                                 continue
    
33.                         else:
    
34.                                 for i in range(si):
    
35.                                         rain += sn - lst1[i]
    
36.                                 lst2 = lst1[si+1:]
    
37.                                 if len(lst2) == 0:
    
38.                                         break
    
39. 
    
40.         return rain

复制代码

gunjang

幸好看了测试。。。否则就出错了，要考虑特殊情况。。。

1. #http://bbs.fishc.com/thread-100583-1-1.html
   
2. t1 = [0,1,0,2,1,0,1,3,2,1,2,1]
   
3. t2=[11,20,62,6,15,87,27,50,98,52,55,16,48,38,80,80,85,80,7,58,52,4,68,99,29,42,2,1,61,88]#答案1154
   
4. #          ^ 103  ^   97    ^          649                             ^     305      ^ =1154
   
5. 
   
6. t3=[82,64,94,44,8,56,31,29,37,34,54,66,14,43,82,96,44,60,62,70,26,56,60,61,4,74,32,6,77,51]#答案1017
   
7. t4=[6,53,57,39,90,87,28,95,15,6,63,8,28,93,86,56,28,93,34,71,87,31,67,87,70,2,34,27,6,76]#答案923
   
8. def max_rainwater(list_of_number):
   
9.         result_of_max_rainwater = 0
   
10.         index1 = 0
    
11.         while True:
    
12.                 while (index1+1 < len(list_of_number)) and (list_of_number[index1+1] >= list_of_number[index1]):
    
13.                         index1 += 1
    
14.                 if index1 >= len(list_of_number)-1:
    
15.                         break
    
16.                 H1 = list_of_number[index1]
    
17.                 j = index1+1
    
18.                 clayArea = 0
    
19.                 while (j < len(list_of_number)) and (H1 > list_of_number[j]):
    
20.                         clayArea += list_of_number[j]
    
21.                         j += 1
    
22.                 if j < len(list_of_number):
    
23.                         #print(index1, j, (j-index1-1)*H1 - clayArea)
    
24.                         result_of_max_rainwater += (j-index1-1)*H1 - clayArea
    
25.                 else:
    
26.                         return result_of_max_rainwater + max_rainwater(list_of_number[len(list_of_number):index1-1:-1])
    
27.                 index1 = j
    
28. 
    
29.         return result_of_max_rainwater
    
30. 
    
31. print(max_rainwater(t1)) #6
    
32. print(max_rainwater(t2))#答案1154
    
33. print(max_rainwater(t3))#答案1017
    
34. print(max_rainwater(t4))#答案923

复制代码

qwc3000

"""
解题思路
1、找最大值及位置
2、按照最大值 分段列表，将列表分为3类，一、逐渐上升的到最大值型； 二、以最大值为两端凹坑性；三、以最大值逐渐下降的
3、上升及凹型 求和
4、下降型 翻转  按照上升型求和
5、
"""
def list_max(P_list):
    temp_max_num=0  #最大值
    temp_max_i=0  #最大值最后出现的位置
    list_type=1
    temp=len(P_list)
    for i in range(temp):
        #如果 大于 那么max_num赋值，重新统计位置列表
        if P_list[i]>temp_max_num:
            temp_max_num=P_list[i]
            temp_max_i=i
        elif P_list[i]==temp_max_num:  #如果 等于  增加位置列表
            temp_max_i = i
    # 判断数列整体走向
    if temp_max_i<temp and temp_max_i>0: #混合型
        list_type=2
    elif temp_max_i==0: #下降型
        list_type=3
    elif temp_max_i==temp: #上升型
        list_type=1
    # print("最大值：",temp_max_num,"位置：",temp_max_i,"类型：",list_type)
    return temp_max_num,temp_max_i,temp,list_type#返回 最大值和位置 走向
# 分解
def list_FJ(P_list):
    L_r_tuple=list_max(P_list) # 获取相关内容
    print(L_r_tuple)
    # 对列表进行切片
    temp_list = []
    if L_r_tuple[3]==2: #混合时
        temp_list.append(P_list[:L_r_tuple[1]+1])
        temp_list.append(P_list[L_r_tuple[1]:])
    else: #单一 上升或者下降时
        temp_list=P_list
    return temp_list,L_r_tuple[3]
# 统计计算方法  适合上升 凹型
def total_result12(P_list):
    temp=0
    result_num=0
    for i in range(len(P_list)):
        if temp > P_list[i]:         #
            result_num=result_num+temp-P_list[i]
        else:
            temp=P_list[i]
    return result_num
# 统计计算方法2 适合下降型
def total_result3(P_list):
    P_list.reverse() #反向
    result=total_result12(P_list)
    return result
# P_list 分解后的列表
# P_type 元列表的类型
def total_list(P_list,P_type):
    temp=len(P_list)
    result=0
    if P_type==2:
        for i in range(temp-1):
            result=result+total_result12(P_list[i])
        result=result+total_result3(P_list[temp-1])  # 下降型 反向后
    elif P_type==1:
        result=result+total_result12(P_list[0])
    elif P_type==3:
        result = result + total_result3(P_list(temp - 1))  # 下降型 反向后
    return result
def max_rainwater(list_of_number):
    temp_tuple = list_FJ(list_of_number)
    result_of_max_rainwater = total_list(temp_tuple[0], temp_tuple[1])
    return result_of_max_rainwater
list1=[6,53,57,39,90,87,28,95,15,6,63,8,28,93,86,56,28,93,34,71,87,31,67,87,70,2,34,27,6,76]
#对列表进行分解，得到此列表类型，和分解后的列表
print(max_rainwater(list1))

大月饼

1. def max_rainwater(list_of_number):
   
2.     result_of_max_rainwater = 0
   
3.     left_max = list_of_number[0]
   
4.     right_max = max(list_of_number[2:])
   
5.     for i in range(len(list_of_number)-2):
   
6.         if left_max<list_of_number[i]:
   
7.             left_max=list_of_number[i]
   
8.         if right_max == list_of_number[i+1]:
   
9.             right_max = max(list_of_number[i+2:])
   
10.         max_lr = left_max if left_max < right_max else right_max
    
11.         if max_lr>list_of_number[i+1]:
    
12.             result_of_max_rainwater += max_lr-list_of_number[i+1]
    
13.     return result_of_max_rainwater

复制代码

蓝色王魂

两种优化方式，方法都是是积水后的面积减原来的面积，如果都大于一个较大的数，比如说都大于10000，第一种方法效率就会很低，或者如果对与list(set(list_of_number)),相邻的值都差个2，3之类的，第一个方法效率也会变低，但如果数字是从0到最大值基本上每个都有取到的话，第一种方法会稍快。

1. def max_rainwater2(list_of_number):
   
2.     max_value = max(list_of_number)
   
3.     sum_all = sum(list_of_number)
   
4.     length = len(list_of_number)
   
5.     sum_watered = 0
   
6.     for i in range(1,max_value+1):
   
7.         for j in range(length):
   
8.             if list_of_number[j] >= i:
   
9.                 start = j
   
10.                 break
    
11.         for j in range(length-1,-1,-1):
    
12.             if list_of_number[j] >= i:
    
13.                 end = j
    
14.                 break
    
15.         sum_watered += end - start + 1
    
16.     return (sum_watered-sum_all)
    
17. 
    
18. def max_rainwater3(list_of_number):
    
19.     sum_all = sum(list_of_number)
    
20.     sum_watered = 0
    
21.     value_list = list(set(list_of_number))
    
22.     length = len(list_of_number)
    
23.     shuiwei = 0
    
24.     for each in value_list:
    
25.         for i in range(length):
    
26.             if list_of_number[i] >= each:
    
27.                 start = i
    
28.                 break
    
29.         for i in range(length-1,-1,-1):
    
30.             if list_of_number[i] >= each:
    
31.                 end = i
    
32.                 break
    
33.         sum_watered += (each-shuiwei) * (end - start + 1)
    
34.         shuiwei = each
    
35.     return (sum_watered-sum_all)

复制代码

蓝色王魂

最终版

1. def max_rainwater4(list_of_number):
   
2.     sum_watered = max(list_of_number)
   
3.     sum_all = sum(list_of_number)
   
4.     max_index = list_of_number.index(sum_watered)
   
5.     shuiwei = list_of_number[0]
   
6.     start = 0
   
7.     length = len(list_of_number)
   
8.     for i in range(1,max_index+1):
   
9.         if list_of_number[i] >= shuiwei:
   
10.             sum_watered += shuiwei*(i-start)
    
11.             start = i
    
12.             shuiwei = list_of_number[i]
    
13.     shuiwei = list_of_number[-1]
    
14.     start = length - 1
    
15.     for i in range(length-2,max_index-1,-1):
    
16.         if list_of_number[i] >= shuiwei:
    
17.             sum_watered += shuiwei*(start - i)
    
18.             start = i
    
19.             shuiwei = list_of_number[i]
    
20.     return (sum_watered-sum_all)

复制代码

凌九霄

1. A = [11, 20, 62, 6, 15, 87, 27, 50, 98, 52, 55, 16, 48, 38, 80, 80, 85, 80, 7, 58, 52, 4, 68, 99, 29, 42, 2, 1, 61, 88]
   
2. B = [82, 64, 94, 44, 8, 56, 31, 29, 37, 34, 54, 66, 14, 43, 82, 96, 44, 60, 62, 70, 26, 56, 60, 61, 4, 74, 32, 6, 77, 51]
   
3. C = [6, 53, 57, 39, 90, 87, 28, 95, 15, 6, 63, 8, 28, 93, 86, 56, 28, 93, 34, 71, 87, 31, 67, 87, 70, 2, 34, 27, 6, 76]
   
4. 
   
5. import random
   
6. import timeit
   
7. 
   
8. D = [random.randint(1, 99) for i in range(1000)]
   
9. E = [random.randint(1, 1000) for i in range(1000000)]
   
10. 
    
11. 
    
12. def max_rainwater(lst):
    
13.     maxvalue = max(lst)
    
14.     ABsection = (lst[:lst.index(maxvalue) + 1], lst[lst.index(maxvalue):][::-1])
    
15.     result = 0
    
16.     for i in ABsection:
    
17.         bigvalue = i[0]
    
18.         for j in range(1, len(i)):
    
19.             if i[j] >= bigvalue:
    
20.                 bigvalue = i[j]
    
21.             else:
    
22.                 result += bigvalue - i[j]
    
23. 
    
24.     return result, lst
    
25. 
    
26. 
    
27. rw = max_rainwater(A)
    
28. print('列表长度：{0}  可收集最大雨水数：{1}'.format(len(rw[1]), rw[0]))
    
29. rw = max_rainwater(B)
    
30. print('列表长度：{0}  可收集最大雨水数：{1}'.format(len(rw[1]), rw[0]))
    
31. rw = max_rainwater(C)
    
32. print('列表长度：{0}  可收集最大雨水数：{1}\n'.format(len(rw[1]), rw[0]))
    
33. 
    
34. rw = max_rainwater(D)
    
35. print('随机列表长度：{0}  可收集最大雨水数：{1}'.format(len(rw[1]), rw[0]))
    
36. print('函数执行用时：{0}s\n'.format(timeit.timeit('max_rainwater(D)', setup='from __main__ import max_rainwater,D', number=1)))
    
37. 
    
38. rw = max_rainwater(E)
    
39. print('随机列表长度：{0}  可收集最大雨水数：{1}'.format(len(rw[1]), rw[0]))
    
40. print('函数执行用时：{0}s'.format(timeit.timeit('max_rainwater(E)', setup='from __main__ import max_rainwater,E', number=1)))
    

复制代码

城管熙

def jishui(x):
    t=time.time()
    water=0
    for k in range(max(x)):
        y=[]
        for i in range(len(x)):
            if x[i]>=max(x)-k:
                y.append(i)
        if len(y)>=2:
            water=water+y[(len(y)-1)]-y[0]-len(y)+1
    t1=time.time()
    print(t1-t)
            
    return water
c=[11,20,62,6,15,87,27,50,98,52,55,16,48,38,80,80,85,80,7,58,52,4,68,99,29,42,2,1,61,88]
print(jishui(c))

城管熙

def jishui(x):
    t=time.time()
    water=0
    for k in range(max(x)):
        y=[]
        for i in range(len(x)):
            if x[i]>=max(x)-k:
                y.append(i)
        if len(y)>=2:
            water=water+y[(len(y)-1)]-y[0]-len(y)+1
    t1=time.time()
    print(t1-t)
            
    return water
c=[11,20,62,6,15,87,27,50,98,52,55,16,48,38,80,80,85,80,7,58,52,4,68,99,29,42,2,1,61,88]
print(jishui(c))

城管熙

怎么发有行数的代码

Pythonbn

def max_rain(lst):
        rain = 0
        lst2 = lst[:]
        while True:
                fn = max(lst)
                fi=lst.index(fn)

                lst1 = lst[:fi]
                if len(lst1) == 1 :
                        break
                else:
                        sn = max(lst1)
                        si = lst1.index(sn)
                        for i in range (si,fi):
                                rain += sn - lst[i]
                        if len(lst1) == 2:
                               break
                        else:
                               lst = lst1
        while True:
                fn = max(lst2)
                fi = lst2.index(fn)

                lst1 = lst2[fi+1:]
                if len(lst1) <= 1 :
                        break
                else:
                        sn = max(lst1)
                        si = lst1.index(sn)
                        if si == 0:
                                lst2 = lst1[:]
                                continue
                        else:
                                for i in range(si):
                                        rain += sn - lst1[i]
                                lst2 = lst1[si+1:]
                                if len(lst2) == 0:
                                        break

        return rain