原题地址: 传送门
¶分析
在二维坐标系中由很多坐标点组成段,段的最小长度为2,且段只有x轴(横轴)和y轴(纵轴)之分,求由两个段组成,垂直有共同顶点,且长边是短边两倍的组合数量。
输入集是一个二维数组,要求中的两个线段互相垂直,这里可以分析出组合中的两个线段一个在x轴一个在y轴。一种思路是通过遍历二维数组得到x和y轴所有的段,再对每个段的端点做索引,再做dfs求组合数,不过这种简单的思路在Test2会出现超时或内存溢出的错误,所以要换一种更简单的思路。
个人解决思路是先对x或y任意维度做head的索引(y轴由上到下,head为上顶点,x轴head为左顶点),例如先对y轴所有段的head做索引,这里直接使用二维数组,假设y轴段的索引定义为二维数组indexs = [1000][1000]int
, indexs第一层下标为x轴坐标,第二层下标为y轴坐标,值为段的长度。之后再遍历获取所有的x轴段,对于x轴的每个段,取其对应的head和tail坐标以及长度len,通过枚举所有满足的y轴坐标值:
- y1 (head.x, head.y - (len/2) + 1)
- y2 (head.x, head.y)
- y3 (head.x, head.y - (len*2) + 1)
- y4 (tail.x, tail.y - (len/2) + 1)
- y5 (tail.x, tail.y)
- y6 (tail.x, tail.y - (len*2) + 1)
(y1和y4只有当len为偶数且大于等于4的时候才成立)
之后通过得到的y轴坐标去检索indexs,如果存在则判断对应段的长度是否满足与当前x轴段长的规则,如果满足则count ++,所有x轴段匹配完毕,输出count为结果值。
¶Slove
1 | package main |