鱼C论坛Python精英挑战赛（第四季02期）,Python交流,技术交流,鱼C论坛

jerryxjr1220 发表于 2017-11-30 09:55:28

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

本帖最后由 jerryxjr1220 于 2017-12-5 21:17 编辑

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

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

新玩法规则：

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

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

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

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

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

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

求给定列表中可收集的最大雨水量。
def max_rainwater(list_of_number):
'''your code here'''
return result_of_max_rainwater

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

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

截止日期： 12月4日24时

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

@小甲鱼 @冬雪雪冬 @～风介～ @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

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

蓝色王魂 发表于 2017-11-30 11:32:16

本帖最后由蓝色王魂于 2017-11-30 12:40 编辑

目前只能想出这个方法，效率还行，但是代码丑。是分别计算每层的水洼面积再累加的。def max_rainwater(list_of_number):
result_of_max_rainwater = 0
length = len(list_of_number)
max_of_list = max(list_of_number)
for times in range(max_of_list):
   for i in range(length):
         if list_of_number>0:
            list_of_number -= 1
            start = i
            break
   for i in range(start+1,length):
         if list_of_number > 0:
            list_of_number -= 1
            distance = i-start-1
            start = i
            if distance>0:
               result_of_max_rainwater += distance
return result_of_max_rainwater

SylarPu 发表于 2017-11-30 14:23:06

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

Elastcio 发表于 2017-11-30 18:58:23

def max_rainwater(list_of_number):
i = max(list_of_number)
total_white = 0
temp = len(list_of_number)*max(list_of_number) - sum(list_of_number)
while i>=1:
   total_white += list_of_number.index(max(list_of_number)) + list_of_number[::-1].index(max(list_of_number))
   list_of_number =
   i -=1
print(temp- total_white )

>>> max_rainwater()
0
>>> max_rainwater()
1154
>>> max_rainwater()
1017
>>> max_rainwater()
923
'''

shuo 发表于 2017-12-1 10:02:52

gunjang 发表于 2017-12-1 11:54:07

本帖最后由 gunjang 于 2017-12-1 14:46 编辑

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

#http://bbs.fishc.com/thread-100583-1-1.html
t1 =
t2=#答案1154
# ^ 103^ 97 ^ 649 ^ 305 ^ =1154

t3=#答案1017
t4=#答案923
def max_rainwater(list_of_number):
result_of_max_rainwater = 0
index1 = 0
while True:
while (index1+1 < len(list_of_number)) and (list_of_number >= list_of_number):
index1 += 1
if index1 >= len(list_of_number)-1:
break
H1 = list_of_number
j = index1+1
clayArea = 0
while (j < len(list_of_number)) and (H1 > list_of_number):
clayArea += list_of_number
j += 1
if j < len(list_of_number):
#print(index1, j, (j-index1-1)*H1 - clayArea)
result_of_max_rainwater += (j-index1-1)*H1 - clayArea
else:
return result_of_max_rainwater + max_rainwater(list_of_number)
index1 = j

return result_of_max_rainwater

print(max_rainwater(t1)) #6
print(max_rainwater(t2))#答案1154
print(max_rainwater(t3))#答案1017
print(max_rainwater(t4))#答案923

qwc3000 发表于 2017-12-2 15:15:09

本帖最后由 qwc3000 于 2017-12-5 22:27 编辑

"""
解题思路
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>temp_max_num:
         temp_max_num=P_list
         temp_max_i=i
   elif P_list==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==2: #混合时
   temp_list.append(P_list[:L_r_tuple+1])
   temp_list.append(P_list:])
else: #单一上升或者下降时
   temp_list=P_list
return temp_list,L_r_tuple
# 统计计算方法适合上升凹型
def total_result12(P_list):
temp=0
result_num=0
for i in range(len(P_list)):
   if temp > P_list:       #
         result_num=result_num+temp-P_list
   else:
         temp=P_list
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)
   result=result+total_result3(P_list)# 下降型反向后
elif P_type==1:
   result=result+total_result12(P_list)
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, temp_tuple)
return result_of_max_rainwater
list1=
#对列表进行分解，得到此列表类型，和分解后的列表
print(max_rainwater(list1))

大月饼 发表于 2017-12-2 20:34:35

本帖最后由大月饼于 2017-12-2 22:48 编辑

def max_rainwater(list_of_number):
result_of_max_rainwater = 0
left_max = list_of_number
right_max = max(list_of_number)
for i in range(len(list_of_number)-2):
   if left_max<list_of_number:
         left_max=list_of_number
   if right_max == list_of_number:
         right_max = max(list_of_number)
   max_lr = left_max if left_max < right_max else right_max
   if max_lr>list_of_number:
         result_of_max_rainwater += max_lr-list_of_number
return result_of_max_rainwater

蓝色王魂 发表于 2017-12-2 22:25:10

本帖最后由蓝色王魂于 2017-12-2 22:41 编辑

两种优化方式，方法都是是积水后的面积减原来的面积，如果都大于一个较大的数，比如说都大于10000，第一种方法效率就会很低，或者如果对与list(set(list_of_number)),相邻的值都差个2，3之类的，第一个方法效率也会变低，但如果数字是从0到最大值基本上每个都有取到的话，第一种方法会稍快。def max_rainwater2(list_of_number):
max_value = max(list_of_number)
sum_all = sum(list_of_number)
length = len(list_of_number)
sum_watered = 0
for i in range(1,max_value+1):
   for j in range(length):
         if list_of_number >= i:
            start = j
            break
   for j in range(length-1,-1,-1):
         if list_of_number >= i:
            end = j
            break
   sum_watered += end - start + 1
return (sum_watered-sum_all)

def max_rainwater3(list_of_number):
sum_all = sum(list_of_number)
sum_watered = 0
value_list = list(set(list_of_number))
length = len(list_of_number)
shuiwei = 0
for each in value_list:
   for i in range(length):
         if list_of_number >= each:
            start = i
            break
   for i in range(length-1,-1,-1):
         if list_of_number >= each:
            end = i
            break
   sum_watered += (each-shuiwei) * (end - start + 1)
   shuiwei = each
return (sum_watered-sum_all)

蓝色王魂 发表于 2017-12-4 18:49:23

最终版def max_rainwater4(list_of_number):
sum_watered = max(list_of_number)
sum_all = sum(list_of_number)
max_index = list_of_number.index(sum_watered)
shuiwei = list_of_number
start = 0
length = len(list_of_number)
for i in range(1,max_index+1):
   if list_of_number >= shuiwei:
         sum_watered += shuiwei*(i-start)
         start = i
         shuiwei = list_of_number
shuiwei = list_of_number[-1]
start = length - 1
for i in range(length-2,max_index-1,-1):
   if list_of_number >= shuiwei:
         sum_watered += shuiwei*(start - i)
         start = i
         shuiwei = list_of_number
return (sum_watered-sum_all)

凌九霄 发表于 2018-5-25 16:12:39

本帖最后由凌九霄于 2018-5-28 16:25 编辑

A =
B =
C =

import random
import timeit

D =
E =

def max_rainwater(lst):
maxvalue = max(lst)
ABsection = (lst[:lst.index(maxvalue) + 1], lst[::-1])
result = 0
for i in ABsection:
   bigvalue = i
   for j in range(1, len(i)):
         if i >= bigvalue:
            bigvalue = i
         else:
            result += bigvalue - i

return result, lst

rw = max_rainwater(A)
print('列表长度：{0}可收集最大雨水数：{1}'.format(len(rw), rw))
rw = max_rainwater(B)
print('列表长度：{0}可收集最大雨水数：{1}'.format(len(rw), rw))
rw = max_rainwater(C)
print('列表长度：{0}可收集最大雨水数：{1}\n'.format(len(rw), rw))

rw = max_rainwater(D)
print('随机列表长度：{0}可收集最大雨水数：{1}'.format(len(rw), rw))
print('函数执行用时：{0}s\n'.format(timeit.timeit('max_rainwater(D)', setup='from __main__ import max_rainwater,D', number=1)))

rw = max_rainwater(E)
print('随机列表长度：{0}可收集最大雨水数：{1}'.format(len(rw), rw))
print('函数执行用时：{0}s'.format(timeit.timeit('max_rainwater(E)', setup='from __main__ import max_rainwater,E', number=1)))

城管熙 发表于 2018-11-19 15:31:32

def jishui(x):
t=time.time()
water=0
for k in range(max(x)):
   y=[]
   for i in range(len(x)):
         if x>=max(x)-k:
            y.append(i)
   if len(y)>=2:
         water=water+y[(len(y)-1)]-y-len(y)+1
t1=time.time()
print(t1-t)

return water
c=
print(jishui(c))

城管熙 发表于 2018-11-19 15:32:31

城管熙 发表于 2018-11-19 15:33:16

怎么发有行数的代码

Pythonbn 发表于 2020-4-2 17:04:13

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
                     if len(lst1) == 2:
                           break
                     else:
                           lst = lst1
   while True:
            fn = max(lst2)
            fi = lst2.index(fn)

            lst1 = lst2
            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
                           lst2 = lst1
                           if len(lst2) == 0:
                                    break

   return rain

页: [1]

鱼C论坛's Archiver

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