Re: [閒聊] 每日leetcode

看板Marginalman作者DJYOMIYAHINA (通通打死)時間1天前 (2025/12/04 23:21)推噓3(3推 0噓 0→)

昨天的還真的要求廣義梯形的數量原本想說就照原本想法用 y=ax+b的a跟b當key去建hash table 不過WA 後來才想到，如果有平行四邊形存在的話，這個平行四邊形會被重複計算到所以問題就變成，怎麼找平行四邊形就整個變很複雜== 初步的想法是兩個線段，斜率相同，落在截距不同的直線上，且長度相同這兩個線段(四個點)組起來就會是平行四邊形用這個思路去硬幹就變成下面這樣了不過就還是WA== 我受不了跑去問gemini 結果是精度問題對ㄚ就加個round就可以了 10是隨便取的 def countTrapezoids(self, points: List[List[int]]) -> int: PRECISION = 10 def find_line_params(point1, point2): x1, y1 = point1 x2, y2 = point2 if x1 == x2: return x1, None a = (y2 - y1) / (x2 - x1) b = y1 - a * x1 return round(a, PRECISION), round(b, PRECISION) def calculate_distance(point1, point2): x1, y1 = point1 x2, y2 = point2 delta_x = x2 - x1 delta_y = y2 - y1 distance = delta_x**2 + delta_y**2 return distance n = len(points) cnt = defaultdict(dict) cnt_vertical = defaultdict(dict) cnt_d_bya = defaultdict(dict) cnt_d_vertical = defaultdict(int) # count for i in range(n): for j in range(i+1, n): a, b = find_line_params(points[i], points[j]) d = calculate_distance(points[i], points[j]) if d in cnt_d_bya[a]: cnt_d_bya[a][d] += 1 else: cnt_d_bya[a][d] = 1 if b is not None: if b in cnt[a] and d in cnt[a][b]: cnt[a][b][d] += 1 elif b in cnt[a]: cnt[a][b][d] = 1 else: cnt[a][b] = {d:1} else: cnt_d_vertical[d] += 1 if d in cnt_vertical[a]: cnt_vertical[a][d] += 1 else: cnt_vertical[a][d] = 1 # calc rets = 0 n_parallel = 0 # number of parallelogram for a, v in cnt.items(): s = 0 for b, v2 in v.items(): for d, n in v2.items(): s += n n_parallel += ((cnt_d_bya[a][d]-n)*n) for b, v2 in v.items(): s_b = 0 for d, n in v2.items(): s_b += n rets += ((s-s_b)*s_b) s = 0 for a, v in cnt_vertical.items(): for d, n in v.items(): s += n n_parallel += ((cnt_d_vertical[d]-n)*n) for a, v in cnt_vertical.items(): s_2 = 0 for d, n in v.items(): s_2 += n rets += ((s-s_2)*s_2) return rets//2-n_parallel//4 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.132.58.28 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1764861704.A.C0F.html ※ 編輯: DJYOMIYAHINA (220.132.58.28 臺灣), 12/04/2025 23:22:04

推

oin1104

12/04 23:36, 1天前 , 1^F

12/04 23:36, 1^F

推

rainkaras

12/05 01:27, 1天前 , 2^F

12/05 01:27, 2^F

推

zs111

12/05 07:17, 22小時前 , 3^F

12/05 07:17, 3^F