[已解决]Python：每日一题 377

zltzlt

March2615 发表于 2020-4-16 12:57
不知不觉一下午过去了

17 ms

zltzlt

TJBEST 发表于 2020-4-16 14:58
来看看我的史诗巨作，历时1个小时20分钟

输入以下数据超时：

testcase.zip (3.73 KB, 下载次数: 1)

2020-4-16 20:48 上传

点击文件名下载附件

zltzlt

kinkon 发表于 2020-4-16 15:21
优化一下

15 ms

zltzlt

whosyourdaddy 发表于 2020-4-16 20:11
def func377(arr):
    def distance( p,  q):
        return (p[0]-q[0]) * (p[0]-q[0]) + (p[1]-q[1]) ...

解答错误

输入：

1. [[3, 7], [6, 8], [7, 8], [11, 10], [4, 3], [8, 5], [7, 13], [4, 13]]

复制代码

输出：

1. [[3, 7], [6, 8], [11, 10], [4, 3], [8, 5], [4, 13]]

复制代码

预期结果：

1. [[3, 7], [7, 13], [11, 10], [8, 5], [4, 13], [4, 3]]

复制代码

ouyunfu

1. import math
   
2. def f377(points):
   
3.     n = len(points)
   
4.     if n == 0:
   
5.         return 0
   
6.     if n <= 3:
   
7.         return points
   
8.    
   
9.     def get_bottom_point(points):
   
10.         min_index = 0
    
11.         n = len(points)
    
12.         for i in range(0, n):
    
13.             if points[i][1] < points[min_index][1] or (points[i][1] == points[min_index][1] and points[i][0] < points[min_index][0]):
    
14.                 min_index = i
    
15.         return min_index
    
16. 
    
17.     def f2(points, center_point):
    
18.         n = len(points)
    
19.         cos_value = []
    
20.         rank = []
    
21.         norm_list = []
    
22.         for i in range(0, n):
    
23.             point_ = points[i]
    
24.             point = [point_[0]-center_point[0], point_[1]-center_point[1]]
    
25.             rank.append(i)
    
26.             norm_value = math.sqrt(point[0]*point[0] + point[1]*point[1])
    
27.             norm_list.append(norm_value)
    
28.             if norm_value == 0:
    
29.                 cos_value.append(1)
    
30.             else:
    
31.                 cos_value.append(point[0] / norm_value)
    
32.         for i in range(0, n-1):
    
33.             index = i + 1
    
34.             while index > 0:
    
35.                 if cos_value[index] > cos_value[index-1] or (cos_value[index] == cos_value[index-1] and norm_list[index] > norm_list[index-1]):
    
36.                     temp = cos_value[index]
    
37.                     temp_rank = rank[index]
    
38.                     temp_norm = norm_list[index]
    
39.                     cos_value[index] = cos_value[index-1]
    
40.                     rank[index] = rank[index-1]
    
41.                     norm_list[index] = norm_list[index-1]
    
42.                     cos_value[index-1] = temp
    
43.                     rank[index-1] = temp_rank
    
44.                     norm_list[index-1] = temp_norm
    
45.                     index = index-1
    
46.                 else:
    
47.                     break
    
48.         sorted_points = []
    
49.         for i in rank:
    
50.             sorted_points.append(points[i])
    
51.      
    
52.         return sorted_points
    
53.    
    
54.     def vector_angle(vector):
    
55.         norm_ = math.sqrt(vector[0]*vector[0] + vector[1]*vector[1])
    
56.         if norm_ == 0:
    
57.             return 0
    
58.      
    
59.         angle = math.acos(vector[0]/norm_)
    
60.         if vector[1] >= 0:
    
61.             return angle
    
62.         else:
    
63.             return 2*math.pi - angle
    
64.      
    
65.     def coss_multi(v1, v2):
    
66.         return v1[0]*v2[1] - v1[1]*v2[0]
    
67. 
    
68.     bottom_index = get_bottom_point(points)
    
69.     bottom_point = points.pop(bottom_index)
    
70.     sorted_points = f2(points, bottom_point)
    
71.     m = len(sorted_points)
    
72.     if m <2 :
    
73.         return points
    
74.     stack = []
    
75.     stack.append(bottom_point)
    
76.     stack.append(sorted_points[0])
    
77.     stack.append(sorted_points[1])
    
78.     for i in range(2, m):
    
79.         length = len(stack)
    
80.         top = stack[length-1]
    
81.         next_top = stack[length-2]
    
82.         v1 = [sorted_points[i][0]-next_top[0], sorted_points[i][1]-next_top[1]]
    
83.         v2 = [top[0]-next_top[0], top[1]-next_top[1]]
    
84.         while coss_multi(v1, v2) > 0:
    
85.             stack.pop()
    
86.             length = len(stack)
    
87.             top = stack[length-1]
    
88.             next_top = stack[length-2]
    
89.             v1 = [sorted_points[i][0] - next_top[0], sorted_points[i][1] - next_top[1]]
    
90.             v2 = [top[0] - next_top[0], top[1] - next_top[1]]
    
91. 
    
92.         stack.append(sorted_points[i])
    
93.     return stack
    
94. 
    
95. print(f377([[1, 2], [2, 2], [4, 2]]))
    
96. print(f377([[1, 1], [2, 2], [2, 0], [2, 4], [3, 3], [4, 2]]))

复制代码

zltzlt

总想起个好名字 发表于 2020-4-16 22:23

？

爱叫什么叫什么

数学不好的人飘过...高等数学没有学过...怎么办

TJBEST

楼主帮忙测测吧 @zltzlt

1. def fun377(points):
   
2.     if len(points) < 4:
   
3.         return points
   
4.     dealWith = sorted(points)
   
5.     Left = dealWith[0]
   
6.     Right = dealWith[-1]
   
7.     del dealWith[0]
   
8.     result = [Left]
   
9.    
   
10.     previous = Left
    
11.     while True:
    
12.         if previous[0] == Left[0]:
    
13.             comList = [i for i in dealWith if (i[0]> previous[0]) or (i[1] > previous[1])]
    
14.         elif previous[0] == Right[0]:
    
15.             comList = [i for i in dealWith if (i[0]== previous[0]) and (i[1] < previous[1])]
    
16.         else:
    
17.             comList = [i for i in dealWith if i[0]> previous[0]]
    
18.         comList.sort()
    
19.         if comList[0][0] == Left[0]:
    
20.             previous = comList[0]
    
21.             result.append(previous)
    
22.             dealWith.remove(previous)
    
23.         elif previous[0] == Right[0]:
    
24.             previous = comList[-1]
    
25.             result.append(previous)
    
26.             dealWith.remove(previous)
    
27.         else:
    
28.             comList.sort(key = lambda ex:(((ex[1]-previous[1])/(ex[0]-previous[0])),-ex[0]))
    
29.             previous = comList.pop()
    
30.             result.append(previous)
    
31.             dealWith.remove(previous)
    
32.         if previous == Right:
    
33.             break
    
34.     dealWith.append(Left)
    
35.     while True:
    
36.         if previous[0] == Left[0]:
    
37.             comList = [i for i in dealWith if (i[0]==previous[0]) and (i[1] > previous[1])]
    
38.         elif previous[0] == Right[0]:
    
39.             comList = [i for i in dealWith if (i[0] < previous[0]) or (i[1] < previous[1])]
    
40.         else:
    
41.             comList = [i for i in dealWith if i[0]< previous[0]]
    
42.         comList.sort()
    
43.         if comList[-1][0] == Right[0]:
    
44.             previous = comList.pop()
    
45.             result.append(previous)
    
46.             dealWith.remove(previous)
    
47.         elif previous[0] == Left[0]:
    
48.             previous = comList[0]
    
49.             result.append(previous)
    
50.             dealWith.remove(previous)
    
51.         else:
    
52.             comList.sort(key = lambda ex:(((ex[1]-previous[1])/(ex[0]-previous[0])),ex[0]))
    
53.             previous = comList.pop()
    
54.             result.append(previous)
    
55.             dealWith.remove(previous)
    
56.         if previous == Left:
    
57.             result.remove(Left)
    
58.             break
    
59.     return result

复制代码

kinkon

自己想的一个测试用例：[[1, 1], [2, 2], [2, 0], [2, 4], [3, 3], [4, 2], [2, 3], [3, 2],[2, 1]]
输出：[[1, 1], [2, 0], [4, 2], [2, 4], [3, 3]]

zltzlt

ouyunfu 发表于 2020-4-16 21:35

解答错误

输入：

1. [[3, 0], [4, 0], [5, 0], [6, 1], [7, 2], [7, 3], [7, 4], [6, 5], [5, 5], [4, 5], [3, 5], [2, 5], [1, 4], [1, 3], [1, 2], [2, 1], [4, 2], [0, 3]]

复制代码

输出：

1. [[3, 0], [5, 0], [6, 1], [7, 2], [7, 3], [7, 4], [6, 5], [5, 5], [4, 5], [3, 5], [2, 5], [1, 4], [1, 3], [1, 2], [2, 1], [0, 3]]

复制代码

预期结果：

1. [[0, 3], [6, 1], [3, 5], [7, 2], [5, 0], [1, 4], [1, 2], [7, 3], [4, 5], [5, 5], [6, 5], [4, 0], [3, 0], [2, 1], [2, 5], [7, 4]]

复制代码

TJBEST

@zltzlt 楼主 新代码见28层

howzyao

待我上机我来画的试试

zltzlt

TJBEST 发表于 2020-4-17 11:16
楼主帮忙测测吧 @zltzlt

56 ms

阴阳神万物主

难度评级：普通
要素分析：数论
随机输入生成器，送给有需要的人：如果觉得好用，麻烦评个分呗

1. from random import randint as r
   
2. def gent(x=[0,4],y=[0,4],m=8,n=5,f=False):
   
3.     '''
   
4.     参数说明：
   
5.         x:'横轴取值闭区间'默认为[0,4]
   
6.         y:'纵轴取值闭区间'默认为[0,4]
   
7.         m:'最多允许多少棵树'默认为8
   
8.         n:'生成数量'默认生成5个测试数据
   
9.         f:'是否固定树的颗数'默认为随机颗树
   
10.     '''
    
11.     x1,x2 = x
    
12.     y1,y2 = y
    
13.     size = min((x2-x1+1)*(y2-y1+1),m)
    
14.     for i in range(n):
    
15.         lst = []
    
16.         for j in range(size if f else r(1,size)):
    
17.             while 1:
    
18.                 pos = [r(x1,x2),r(y1,y2)]
    
19.                 if pos not in lst:
    
20.                     lst.append(pos)
    
21.                     break
    
22.         yield lst
    

复制代码

解题代码1：

1. def solve(trees:'list og points by list')->list:
   
2.     class Func:
   
3.         '''
   
4.         y = kx + b
   
5.         k = (y1-y2)/(x1-x2)
   
6.         b = y - kx
   
7.         '''
   
8.         def __init__(self,p1,p2):
   
9.             x1,y1 = p1
   
10.             x2,y2 = p2
    
11.             self.k = (y1-y2)/(x1-x2) if x1!=x2 else None
    
12.             self.b = y1 - self.k*x1 if self.k!=None else x1
    
13.         def cmp(self,pos):
    
14.             x,y = pos
    
15.             if self.k==None:return 0 if x==self.b else 1 if x > self.b else -1
    
16.             ny = self.k*x + self.b
    
17.             return 0 if y==ny else 1 if y > ny else -1
    
18.     res = []
    
19.     l = len(trees)
    
20.     if l <= 3:return trees
    
21.     for a in range(l-1):
    
22.         for b in range(a+1,l):
    
23.             f =  Func(trees[a],trees[b])
    
24.             c = [f.cmp(pos) for pos in trees]
    
25.             if not(1 in c and -1 in c):
    
26.                 while 0 in c:
    
27.                     n = c.index(0)
    
28.                     if trees[n] not in res:res.append(trees[n])
    
29.                     c[n] += 1
    
30.     return res
    
31. 
    
32. if __name__ == '__main__':
    
33.     print('示例1 输出：',solve([[1, 1], [2, 2], [2, 0], [2, 4], [3, 3], [4, 2]]))
    
34.     print('示例2 输出：',solve([[1, 2], [2, 2], [4, 2]]))
    

复制代码

思路解说：
整体就是一个简单的线性规划问题，所有点两两相连，若所有点都在线的同一侧或者就在线上，那么这条线就是边界。
当然，我上面这个属于是暴力规划，还有更加巧妙的，就是下面那个。

解题代码2：

1. class Func:
   
2.     '''
   
3.     y = kx + b
   
4.     k = (y1-y2)/(x1-x2)
   
5.     b = y - kx
   
6.     '''
   
7.     def __init__(self,p1,p2):
   
8.         x1,y1 = p1
   
9.         x2,y2 = p2
   
10.         self.k = (y1-y2)/(x1-x2) if x1!=x2 else None
    
11.         self.b = y1 - self.k*x1 if self.k!=None else x1
    
12.     def cmp(self,pos):
    
13.         x,y = pos
    
14.         if self.k==None:return 0 if x==self.b else 1 if x > self.b else -1
    
15.         ny = round(self.k*x + self.b,1)
    
16.         return 0 if y==ny else 1 if y > ny else -1
    
17.    
    
18. def solve(trees:'list og points by list')->list:
    
19.     res = []
    
20.     l = len(trees)
    
21.     if l <= 3:return trees
    
22.     trees.sort()
    
23.     a,b = 0,0
    
24.     plan = [0]*l#标记非端边界点
    
25.     flg = 1
    
26.     while flg:
    
27.         b = (b+1)%l
    
28.         if plan[b]:continue
    
29.         if b == a:a = (a+1)%l;b=a
    
30.         f =  Func(trees[a],trees[b])#解析直线函数
    
31.         c = [f.cmp(pos) for pos in trees]#检查所有点与直线的关系
    
32.         if not(1 in c and -1 in c):#所有点均在直线的同一侧，或者在直线上
    
33.             online = []
    
34.             while 0 in c:
    
35.                 n = c.index(0)
    
36.                 online.append(trees[n])
    
37.                 if trees[n] not in res:res.append(trees[n])#将边界点加入输出列表
    
38.                 elif not plan[n]:flg = 0
    
39.                 c[n] += 1
    
40.                 if n!=a:plan[n] = 1
    
41.             online.sort()
    
42.             ia = online.index(trees[a])
    
43.             ib = online.index(trees[b])
    
44.             a = trees.index(online[-1 if ib>ia else 0])
    
45.             b = a#从线的一端直接到另一端，跳过中间的已被标记的点
    
46.     return res
    
47.         
    
48. if __name__ == '__main__':
    
49.     print('示例1 输出：',solve_1([[1, 1], [2, 2], [2, 0], [2, 4], [3, 3], [4, 2]]))
    
50.     print('示例2 输出：',solve_1([[1, 2], [2, 2], [4, 2]]))
    
51.    

复制代码

我自己测试的用时是，在51*51的区域内，最多允许60颗树存在，100个随机测试用例
法一平均用时：36.3805ms
法二平均用时：6.2350ms
我自己测试用时的代码：

1. >>> import time
   
2. >>> def pt(b,x=5,y=5):        #在发现输出数据不同时，用平面图的方式呈现出数据，便于肉眼分辨
   
3.         plan = [[0]*y for i in range(x)]
   
4.         for i,j in b:
   
5.                 plan[i][j] = 1
   
6.         for line in plan:
   
7.                 print(line)
   
8. 
   
9. >>> if 1:
   
10.         t1,t2 = [],[]
    
11.         for each in gent([0,50],[0,50],m=60,n=100):
    
12.                 a = time.perf_counter()
    
13.                 s1 = solve_1(each)
    
14.                 b = time.perf_counter()
    
15.                 t1.append((b-a)*1000)
    
16.                 a = time.perf_counter()
    
17.                 s2 = solve_2(each)
    
18.                 b = time.perf_counter()
    
19.                 t2.append((b-a)*1000)
    
20.                 for each in s1:          #这个二层循环是检查两种方法的结果是否一致的，如不需要，可直接删去
    
21.                         if each not in s2:
    
22.                                 print('input',len(each))
    
23.                                 pt(each,51,51)
    
24.                                 print('s1',(s1))
    
25.                                 pt(s1,51,51)
    
26.                                 print('s2',(s2))
    
27.                                 pt(s2,51,51)
    
28.                                 break
    
29.         print('法一平均用时：%0.4fms\n法二平均用时：%0.4fms\n总共用时%0.4fms'%(sum(t1)/len(t1),sum(t2)/len(t2),sum(t1+t2)))

复制代码

archlzy

1. import math
   
2. 
   
3. def fun377(input_list):
   
4.     if len (input_list) <4:
   
5.         return input_list
   
6.     else:
   
7.         temp_list = input_list
   
8.         
   
9.         def test_inner():
   
10.             """"
    
11.             calc_p 检测点 other_p 其他点的列表
    
12.             返回值 : True 是内部点, False 不是内部点
    
13.             检测函数 检测点 所有边都不能夹角 找不到大于 pi的
    
14.             那么这个点就是内部点,否则就是 位于边界上的点
    
15.             """
    
16.             vector_list = [(i-calc_p[0], j-calc_p[1]) for i,j in other_p]
    
17.             deg_list=[]
    
18.             for x,y in vector_list:
    
19.                 r = (x**2 +y**2)**0.5
    
20.                 deg = math.acos(x/r)
    
21.                 if y<0:
    
22.                     deg = -deg + math.pi *2
    
23.                 deg_list.append(deg)
    
24.             deg_list.sort()
    
25.             for i in range(len(deg_list)):
    
26.                 if i == len(deg_list) -1:
    
27.                     if math.pi *2 - deg_list[-1] + deg_list[0]>= math.pi:
    
28.                         break
    
29.                 elif deg_list[i+1] - deg_list[i] >= math.pi:
    
30.                     break
    
31.             else:
    
32.                 return True
    
33.             return False
    
34.             
    
35.         num = 0 # 从0位置开始 记住上次跳出的 for 循环计数 i 进入下一个for 其实从 i 开始
    
36.         while num < len(temp_list):
    
37.             for i in range(num, len(temp_list)):   
    
38.                 calc_p = temp_list[i]
    
39.                 other_p = temp_list[:i] + temp_list[i+1:]
    
40.                 if test_inner():
    
41.                     temp_list.remove(calc_p)
    
42.                     num = i
    
43.                     break
    
44.             else: # 如果for循环 走完了没有被打断说明 现在for里面的都是外部点
    
45.                 return temp_list
    
46.         return temp_list

复制代码

风魔孤行者

1. def f(list1):
   
2.     def x(list1):
   
3.         return list1[0]
   
4.     def y(list1):
   
5.         return list1[1]
   
6.     list2 = []
   
7.     list1 = sorted(list1,key=x)
   
8.     xmin = list1[0][0]
   
9.     xmin_list = []
   
10.     xmax = list1[-1][0]
    
11.     xmax_list = []
    
12.     for each in list1:
    
13.         if each[0] == xmin:
    
14.             list2.append(each)
    
15.             xmin_list.append(each[1])
    
16.         elif each[0] == xmax:
    
17.             list2.append(each)
    
18.             xmax_list.append(each[1])
    
19.    
    
20.     list1 = sorted(list1,key=y)
    
21.     ymin = list1[0][1]
    
22.     ymin_list = []
    
23.     ymax = list1[-1][1]
    
24.     ymax_list = []
    
25.     for each in list1:
    
26.         if each[1] == ymin:
    
27.             list2.append(each)
    
28.             ymin_list.append(each[0])
    
29.         elif each[1] == ymax:
    
30.             list2.append(each)
    
31.             ymax_list.append(each[0])
    
32. 
    
33.     xmin_list.sort()
    
34.     xmax_list.sort()
    
35.     ymin_list.sort()
    
36.     ymax_list.sort()
    
37. 
    
38.     def f1(p1,p2,p3):
    
39.         if abs((p2[1]-p1[1])/(p2[0]-p1[0]))<abs((p3[1]-p1[1])/(p3[0]-p1[0])):
    
40.             return 2
    
41.         elif abs((p2[1]-p1[1])/(p2[0]-p1[0]))==abs((p3[1]-p1[1])/(p3[0]-p1[0])):
    
42.             return 1
    
43.         else:
    
44.             return 0
    
45.         
    
46.     leftup,leftdown,rightup,rightdown = list1[:],list1[:],list1[:],list1[:]
    
47.     p1,p2,p3,p4,p5,p6,p7,p8 = [xmin,xmin_list[-1]],[ymax_list[0],ymax],[ymax_list[-1],ymax],[xmax,xmax_list[-1]],[xmax,xmax_list[0]],[ymin_list[-1],ymin],[ymin_list[0],ymin],[xmin,xmin_list[0]]
    
48.     h1,h2,h3,h4 = [],[],[],[]
    
49.     while leftup != []:
    
50.         for each in leftup.copy():
    
51.             if each[0]>=p2[0] or each[1]<=p1[1]:
    
52.                 leftup.remove(each)
    
53.             else:
    
54.                 if f1(p1,p2,each)==2:
    
55.                     h1 = []
    
56.                     h1.append(each)
    
57.                     p2 = each
    
58.                 elif f1(p1,p2,each)==1:
    
59.                     h1.append(each)
    
60.         if h1 != []:
    
61.             list2 += h1
    
62.             h1 = sorted(h1,key=y)
    
63.             p1 = h1[-1]
    
64.             p2 = [ymax_list[0],ymax]
    
65.             for m in h1:
    
66.                 leftup.remove(m)
    
67.         else:
    
68.             break
    
69.     while rightup != []:
    
70.         for each in rightup.copy():
    
71.             if each[0]<=p3[0] or each[1]<=p4[1]:
    
72.                 rightup.remove(each)
    
73.             else:
    
74.                 if f1(p4,p3,each)==2:
    
75.                     h2 = []
    
76.                     h2.append(each)
    
77.                     p3 = each
    
78.                 elif f1(p4,p3,each)==1:
    
79.                     h2.append(each)
    
80.         if h2 != []:
    
81.             list2 += h2
    
82.             h2 = sorted(h2,key=y)
    
83.             p4 = h2[-1]
    
84.             p3 = [ymax_list[-1],ymax]
    
85.             for m in h2:
    
86.                 rightup.remove(m)
    
87.         else:
    
88.             break
    
89.     while leftdown != []:
    
90.         for each in leftdown.copy():
    
91.             if each[0]>=p7[0] or each[1]>=p8[1]:
    
92.                 leftdown.remove(each)
    
93.             else:
    
94.                 if f1(p8,p7,each)==2:
    
95.                     h4 = []
    
96.                     h4.append(each)
    
97.                     p7 = each
    
98.                 elif f1(p8,p7,each)==1:
    
99.                     h4.append(each)
    
100.         if h4 != []:
     
101.             list2 += h4
     
102.             h4 = sorted(h4,key=x)
     
103.             p8 = h4[-1]
     
104.             p7 = [ymin_list[0],ymin]
     
105.             for m in h4:
     
106.                 leftdown.remove(m)
     
107.         else:
     
108.             break
     
109.     while rightdown != []:
     
110.         for each in rightdown.copy():
     
111.             if each[0]<=p6[0] or each[1]>=p5[1]:
     
112.                 rightdown.remove(each)
     
113.             else:
     
114.                 if f1(p5,p6,each)==2:
     
115.                     h3 = []
     
116.                     h3.append(each)
     
117.                     p6 = each
     
118.                 elif f1(p5,p6,each)==1:
     
119.                     h3.append(each)
     
120.         if h3 != []:
     
121.             list2 += h3
     
122.             h3 = sorted(h3,key=x)
     
123.             p5 = h3[0]
     
124.             p6 = [ymin_list[-1],ymin]
     
125.             for m in h3:
     
126.                 rightdown.remove(m)
     
127.         else:
     
128.             break
     
129.     return list2

复制代码

zltzlt

阴阳神万物主 发表于 2020-4-18 01:56
难度评级：普通
要素分析：数论
随机输入生成器，送给有需要的人：如果觉得好用，麻烦评个分呗

两段代码输入以下数据都会超时：

testcase2.zip (3.73 KB, 下载次数: 1)

2020-4-18 17:27 上传

点击文件名下载附件

zltzlt

archlzy 发表于 2020-4-18 11:45

输入以下数据超时：

testcase2.zip (3.73 KB, 下载次数: 0)

2020-4-18 17:30 上传

点击文件名下载附件

zltzlt

风魔孤行者 发表于 2020-4-18 16:59

输入 [[1, 2], [2, 2], [4, 2]] 出错