即将失业的人 level
获赞
4
粉丝
3
关注
4
看过 TA
1
上海交通大学
2020
算法工程师
IP属地:未知
暂未填写个人简介
私信
关注
2019-10-24 01:05
已编辑
上海交通大学 算法工程师
0 点赞 评论 收藏
分享
2019-09-25 21:53
已编辑
上海交通大学 算法工程师
0 点赞 评论 收藏
分享
2019-09-15 20:17
已编辑
上海交通大学 算法工程师
问的三角形顶点排序,有大佬给提供个思路吗?
RickNew:import sys def get_all_edges(tri):     a, b, c = tri[0], tri[1], tri[2]     return [(a, b), (b, c), (c, a)] def build_right_pair_from_edges(tri):     min_index = tri.index(min(tri))     return tri[min_index:] + tri[:min_index]      def edges_exist(edges, valid_edges):     for i, edge in enumerate(edges):         if edge in valid_edges:             return 1, i         elif tuple(reversed(edge)) in valid_edges:             return 0, i         else:             continue     return -1, None def find_right_dirs(tris):     tris = [[tri, i] for i, tri in enumerate(tris)]     valid_edges, res, tri0 = [], [], tris[0]     valid_edges.extend(get_all_edges(tri0[0]))     res.append([build_right_pair_from_edges(tri0[0]), 0])     tris.pop(0)     while len(tris):         tri = tris[0]         edges = get_all_edges(tri[0])         code, loc = edges_exist(edges, valid_edges)         if code == 0:             edges.pop(loc)             valid_edges.extend(edges)             res.append([build_right_pair_from_edges(tri[0]), tri[1]])             tris.pop(0)         elif code == 1:             tris.pop(0)             tris.append([list(reversed(tri[0])), tri[1]])         else:             tris.pop(0)             tris.append(tri)     res.sort(key=lambda x: x[1])     return [_[0] for _ in res] if __name__ == "__main__":     # N, M = list(map(int, input().split()))     # tris = []     # for i in range(M):     #    tris.append(list(map(int, input().split())))     N, M = 6, 4     tris = [[3, 2, 4],[1, 3, 2],[3, 6, 5],[5, 3, 4]]     res = find_right_dirs(tris)     for _ in res:         print(_[0], _[1], _[2]) ac了,思路就是以第一个三角形为基准,将合法的双顶点边放到一个列表a中,对于每一个新来的三角形,会出现两种情况: 1. 新的三角形没有双顶点边在a中,这个可以先跳过,延后再算; 2. 新的三角形在a中可以找到双顶点边 (<a, b>与<a, b>、<a, b>与<b, a>),这种就是可以继续计算的,如果边的方向不同 (<a, b>、<b, a>),这个新三角形的朝向就是对的,直接将整个pair放入结果列表res中 (还要排序),同时更新列表a;如果边的方向相同 (<a, b>、<a, b>),朝向就相反了,将这个pair翻转后,再重新计算;最后当所有的pair都被计算了,就结束了。 关于为什么同向边朝向反了,反向边朝向正确,可以画个图就看出来了~
投递网易雷火等公司8个岗位
0 点赞 评论 收藏
分享

创作者周榜

更多
关注他的用户也关注了:
牛客网
牛客网在线编程
牛客网题解
牛客企业服务