鱼C论坛

 找回密码
 立即注册
查看: 6960|回复: 53

[技术交流] 鱼C论坛Python精英挑战赛(第四季01期)

[复制链接]
发表于 2017-11-24 09:53:16 | 显示全部楼层 |阅读模式
本帖最后由 jerryxjr1220 于 2017-11-30 16:06 编辑

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

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

新玩法规则:

1. 押宝玩法:进入“押宝”竞猜帖,购买主题(5鱼币)参与“押宝”,最终“押宝”获胜者将平分奖池的奖金并额外获取10鱼币奖励。猜错者将不返还“押宝”的鱼币。若本届比赛无人“押宝”成功,奖金将累计到下次比赛。

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

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

本期题目: 最大包含的水的面积

给定一个包含若干数值的列表,例如:[1,8,6,2,5,4,8,3,7],其中每个数值代表一个木板的长度,在任意两个木板间注水,可以得到其包含的注水面积,如下图蓝色部分的面积为8x5=40(8是木板长度,5是两木板间隔的距离)
下载.png

这2块木板见的水面积是这样的。
下载 (1).png

求给定列表中两木板间包含的最大的水的面积。
  1. def max_area(list_of_number):
  2.     '''your code here'''
  3.     return result_of_max_area
复制代码


要求: 结果正确,程序效率高,代码简洁

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

看到不少鱼油已经非常快得都递交了答案,这个单从难度来说还是比较简单的,不过对于超长列表来说,运算效率是一大问题。比如说给个100万长度的列表,你的程序算得出来吗?

截止日期: 11月30日0时

本期擂主: 蓝色王魂  由于本期只有算法题,所以就不给选择了

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

竞猜:回答正确的参赛者的人数
单选投票, 共有 36 人参与投票
您所在的用户组没有投票权限

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-11-24 10:16:25 | 显示全部楼层
第二和第十之间怎么算?
这样
2.jpg

还是这样
3.jpg

点评

我很赞同!: 1.0
我很赞同!: 1
第一种,只看任意2块木板间  发表于 2017-11-24 10:36
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-11-24 10:32:16 | 显示全部楼层
  1. def max_area(lst):
  2.     length = len(lst)
  3.     area = []
  4.     for i in range(length - 1):
  5.         temp = []
  6.         for j in range(i + 1,length):
  7.             temp.append((j - i) * (lst[i] if lst[i] < lst[j] else lst[j]))            
  8.         area.append(max(temp))
  9.     return max(area)


  10. lst = [1,8,6,2,5,4,8,3,7]
  11. print(max_area(lst))
复制代码

点评

我很赞同!: 5.0
我很赞同!: 5
3.902 s,5000长度的列表,答案正确  发表于 2017-11-24 13:58

评分

参与人数 1荣誉 +2 鱼币 +2 贡献 +2 收起 理由
jerryxjr1220 + 2 + 2 + 2 答题奖励,速度超快!

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-11-24 12:39:29 | 显示全部楼层
  1. L = [1, 8, 6, 2, 5, 4, 8, 3, 7]

  2. def max_area(_list):
  3.     rs = []
  4.     for i in range(len(_list)):
  5.         for j in range(i, len(_list)):
  6.             rs.append((_list[i] if _list[i] < _list[j] else _list[j]) * abs(i - j))
  7.     return max(rs)

  8. print(max_area(L))
复制代码

点评

5.297 s,5000长度的列表,答案正确  发表于 2017-11-24 13:56

评分

参与人数 1荣誉 +2 鱼币 +2 贡献 +2 收起 理由
jerryxjr1220 + 2 + 2 + 2 答题奖励

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-11-24 13:39:21 | 显示全部楼层
試試水溫

  1. def max_area(list_of_num):
  2.         from itertools import combinations
  3.         b=[i for i in range(len(list_of_num))]
  4.         a=list(combinations(b, 2))
  5.         d=[]
  6.         for i in a:
  7.                 if list_of_num[i[0]]>list_of_num[i[1]]:
  8.                         d.append(list_of_num[i[1]]*(i[1]-i[0]))
  9.                 else:
  10.                         d.append(list_of_num[i[0]]*(i[1]-i[0]))
  11.         return print(max(d))

  12. max_area([1,8,6,2,5,4,8,3,7])
复制代码

点评

我很赞同!: 5.0
我很赞同!: 5
7.421 s,5000长度的列表,答案正确 不过一般用了return 后面就不要print了,不然返回的是None  发表于 2017-11-24 14:00

评分

参与人数 1荣誉 +2 鱼币 +2 贡献 +2 收起 理由
jerryxjr1220 + 2 + 2 + 2 答题奖励

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-11-24 16:09:56 | 显示全部楼层
  1. def max_area(list_of_number):
  2.     length = len(list_of_number)
  3.     result_of_max_area = 0
  4.     for i in range(length):
  5.         for j in range(i+1,length):
  6.             area = (j - i)*(min(list_of_number[i], list_of_number[j]))
  7.             if area > result_of_max_area:
  8.                 result_of_max_area = area
  9.     return result_of_max_area
复制代码

点评

我很赞同!: 5.0
我很赞同!: 5
4.707 s, 列表长度5000, 解答正确  发表于 2017-11-24 16:26

评分

参与人数 1荣誉 +2 鱼币 +2 贡献 +2 收起 理由
jerryxjr1220 + 2 + 2 + 2 答题奖励

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-11-24 16:53:38 | 显示全部楼层
本帖最后由 SixPy 于 2017-11-24 18:06 编辑
  1. import numpy as np
  2. def max_area(ls):
  3.     a = np.array(ls)
  4.     x,y = np.triu_indices(len(ls),1)
  5.     return (np.where(a[x]<a[y],a[x],a[y])*(y-x)).max()

  6. ls = [1,8,6,2,5,4,8,3,7]
  7. print(max_area(ls))
  8. #49
复制代码

点评

我很赞同!: 5.0
我很赞同!: 5
版主V5,0.568s,5000列表长度。不过如果列表长度为100万会导致内存溢出。我的解法100万的列表不到1s ^_^  发表于 2017-11-24 19:26

评分

参与人数 1荣誉 +5 鱼币 +5 贡献 +5 收起 理由
jerryxjr1220 + 5 + 5 + 5 支持楼主!

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-11-24 19:52:25 | 显示全部楼层
@jerryxjr1220 支持大内存,要用64位的python和numpy
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-11-25 09:48:21 | 显示全部楼层
  1. def max_area(nums):
  2.     l = 0
  3.     r = len(nums) - 1
  4.     area = 0
  5.     for width in range(len(nums) - 1, 1, -1):
  6.         height = min(nums[l], nums[r])
  7.         area = max(area, height * width)
  8.         if nums[l] > nums[r]:
  9.             r -= 1
  10.         else:
  11.             l += 1

  12.     return area
复制代码

点评

0.010s,5000列表长度,答案正确! 非常棒,100万列表长度用时0.68秒  发表于 2017-11-30 08:54

评分

参与人数 2荣誉 +7 鱼币 +7 贡献 +2 收起 理由
汨罗江 + 5 + 5 支持楼主!
jerryxjr1220 + 2 + 2 + 2 答题奖励

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-11-25 10:42:04 | 显示全部楼层
感觉题目有问题呢。例子中的最大面积应该是在第1块与第9块之间注水得到的1+8×5+7×2 = 55吧?

点评

不,我坚决不同意楼主的看法!: 1.0
不,我坚决不同意楼主的看法!: 1
不是的,只考虑2块木板。  发表于 2017-11-25 13:38
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-11-26 21:38:47 | 显示全部楼层

RE: 鱼C论坛Python精英挑战赛(第四季01期)

  1. def max_area(o_list):

  2.     import numpy as np

  3.     #o_list = [1,8,6,2,5,4,8,3,7]

  4.     length = len(o_list)
  5.     mat1 = np.mat(np.zeros((length,length)))

  6.     for i in range(length):
  7.         for j in range(length):
  8.             if i<=j :
  9.                 mat1[i,j] =min(o_list[i],o_list[j]) * abs(i-j)

  10.     #print(mat1)
  11.     #print("Max.Area = ", mat1.max())

  12.     return (mat1.max())

  13. r = max_area([1,8,6,2,5,4,8,3,7])
复制代码



在题目截止的最后一秒,如果是奇数我就回答,偶数我就不回答,我岂不是可以控制竞猜结果。

点评

不,我坚决不同意楼主的看法!: 1.0
不,我坚决不同意楼主的看法!: 1
你怎么知道你之前有多少人的回答是正确的?你应该看不到其他人的回帖吧?  发表于 2017-11-26 23:28
6.475s,5000列表长度,答案正确  发表于 2017-11-26 23:27

评分

参与人数 1荣誉 +2 鱼币 +2 贡献 +2 收起 理由
jerryxjr1220 + 2 + 2 + 2 答题奖励

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-11-27 11:19:08 | 显示全部楼层
  1. def max_area(list_of_number):
  2.     length = len(list_of_number)
  3.     s_list = []
  4.     for index1 in range(length):
  5.         for index2 in range(index1+1, length):
  6.             a = index2 - index1
  7.             b = min(list_of_number[index1], list_of_number[index2])
  8.             s = a * b
  9.             s_list.append(s)
  10.     result_of_max_area = max(s_list)
  11.     return result_of_max_area


  12. list_of_number = [1,8,6,2,5,4,8,3,7]

  13. print(max_area(list_of_number))
复制代码

点评

6.295s,5000列表长度,答案正确  发表于 2017-11-27 11:26

评分

参与人数 1荣誉 +2 鱼币 +2 贡献 +2 收起 理由
jerryxjr1220 + 2 + 2 + 2 答题奖励

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-11-27 11:20:59 | 显示全部楼层
  1. def max_area(list_of_number):
  2.     length = len(list_of_number)
  3.     result_of_max_area = 0
  4.     for index1 in range(length):
  5.         for index2 in range(index1+1, length):
  6.             a = index2 - index1
  7.             b = min(list_of_number[index1], list_of_number[index2])
  8.             area = a * b
  9.             if area > result_of_max_area:
  10.                 result_of_max_area = area
  11.     return result_of_max_area


  12. list_of_number = [1,8,6,2,5,4,8,3,7]

  13. print(max_area(list_of_number))
复制代码

点评

4.845s,5000列表长度,答案正确  发表于 2017-11-27 11:28
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-11-27 11:55:09 | 显示全部楼层
本帖最后由 蓝色王魂 于 2017-11-27 13:23 编辑

改进了一下效率应该会快很多
  1. def max_area(list_of_number):
  2.     length = len(list_of_number)
  3.     result_of_max_area = (length-1)*(min(list_of_number[0],list_of_number[-1]))
  4.     for i in range(length):
  5.         for j in range(i+result_of_max_area//list_of_number[i],length):
  6.             area = (j - i)*(min(list_of_number[i], list_of_number[j]))
  7.             if area > result_of_max_area:
  8.                 result_of_max_area = area
  9.     return result_of_max_area
复制代码

点评

我很赞同!: 5.0
我很赞同!: 5
0.015s,5000列表长度,非常不错!总算看到一个可以计算100万列表长度的程序了。  发表于 2017-11-27 12:54

评分

参与人数 1荣誉 +5 鱼币 +5 收起 理由
SixPy + 5 + 5 巧妙利用面积反推距离

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-11-27 13:25:35 | 显示全部楼层
本帖最后由 蓝色王魂 于 2017-11-27 13:28 编辑
蓝色王魂 发表于 2017-11-27 11:55
改进了一下效率应该会快很多


把多余的try-except去掉了,我以为range函数当起始值大于终止值时会报错呢。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-11-27 14:00:35 | 显示全部楼层
见面会
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-11-27 16:06:12 | 显示全部楼层
本帖最后由 shuo 于 2017-11-27 16:40 编辑
  1. def max_area(list_of_number):
  2.     max_arrea = 0
  3.     for i in (0,len(list_of_number)):
  4.          for j in (0,len(list_of_number)):
  5.               if i == j:
  6.                   continue
  7.               height = list_of_number[i] if list_of_number[i] > list_of_number[j] else list_of_number[j]
  8.               weight = abs(i - j)
  9.               area = height * weight
  10.              max_area = area if area > max_area else max_area
  11.     return max_area
复制代码


水平有限,实在想不出怎么优化,坐等题主答案呢。

点评

程序有误没有结果,max_area = area if area > max_area,python的语法没有这样写的哦。  发表于 2017-11-27 16:28

评分

参与人数 1荣誉 +2 鱼币 +2 贡献 +2 收起 理由
jerryxjr1220 + 2 + 2 + 2 答题奖励

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-11-27 16:41:20 | 显示全部楼层
shuo 发表于 2017-11-27 16:06
水平有限,实在想不出怎么优化,坐等题主答案呢。

是的, 已改正。 感谢指出。

点评

不,我坚决不同意楼主的看法!: 5.0
不,我坚决不同意楼主的看法!: 5
仍然有错误,请再细心检查。 错误代码: height = list_of_number[i] if list_of_number[i] > list_of_number[j] else list_of_number[j] IndexError: list inde   发表于 2017-11-28 11:03
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-11-28 15:50:51 | 显示全部楼层
shuo 发表于 2017-11-27 16:41
是的, 已改正。 感谢指出。

非常感谢 楼主的耐心指出。 改正后代码如下。
  1. def max_area(list):
  2.    max_area = 0
  3.    for i in range(0,len(list)):
  4.        for j in range(0,len(list)):
  5.             if i == j :
  6.                  continue
  7.             height = list[i] if list[i] < list[j] else list[j]
  8.             weight = abs(i - j)
  9.             area = height * weight
  10.             max_area = area if area > max_area else max_area
  11.   return max_area
复制代码

点评

6.746s,5000列表长度,答案正确  发表于 2017-11-28 20:48
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-11-28 16:57:04 | 显示全部楼层
  1. from itertools import combinations

  2. def area(points):
  3.     (ax, ay), (bx, by) = points
  4.     return abs(bx - ax) * min(ay, by)

  5. def max_area(list_of_number):
  6.     coordinates = ((x, y) for x, y in enumerate(list_of_number))
  7.     buckets = combinations(coordinates, 2)
  8.     result_of_max_area = max(area(i) for i in buckets)
  9.     return result_of_max_area
复制代码

点评

6.191s,5000列表长度,答案正确  发表于 2017-11-28 20:46

评分

参与人数 1荣誉 +2 鱼币 +2 贡献 +2 收起 理由
jerryxjr1220 + 2 + 2 + 2 答题奖励

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-28 23:23

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表