Re: [閒聊] 每日leetcode

看板Marginalman作者sixB (6B)時間1天前 (2025/12/05 02:15)推噓0(0推 0噓 0→)

我好後悔沒有早點來看DJ寶的文我剛剛debug 到很崩潰已經查到-82.3333 不等於-82.3333了想上來靠杯就看到這篇我真的幹你娘C++ 我也要round了 ※ 引述《DJYOMIYAHINA (通通打死)》之銘言： : 昨天的 : 還真的要求廣義梯形的數量 : 原本想說就照原本想法用 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 -- 很姆的咪姆之咪 http://i.imgur.com/5sw7QOj.jpg