Nhớ trừ 1 nếu có 1 nhé k là bugQ4 tiếc quá, nghĩ ra thuật rồi không code kịpdo n <= 10^15 nên sau bước popcount đầu tiên chỉ có thể có ra các số <= 50. Popcount cho từng số bé hơn 50 với k-1 lần rồi xem thằng nào về 1 thì đếm tổ hợp của nó :v dính đoạn DP digit
Muốn nhanh thì lưu sẵn template thôi fence. Dfs, bfs, djikstra, sieve....:v nma công nhận bác nghĩ và code lẹ thật, dùng Python nữa. Em dùng Java mò mò mãi, nghĩ cũng 10-15 phút Q3 mới ra
Câu 4 thì sau 1 bước nó giảm từ n về log rồi nên còn rất ít, chấp cả k to hay nhỏ luôn. Câu 3 em k quen dùng djistra (template sẵn) hơi khó debug, xong hóa ra do bs ngu (dùng recursive) nên tốn cmn 1 tiếng
Mấy cái dfs thì nhớ chứ template nhiều lúc gặp customize là ngọng ngay, mình nghĩ chỉ nên template mấy cái thuật toán nâng cao như Binary lifting, Seg, Sparse table, Kmp, Zfunction này nọ thôi.
Lấy form thôi xong chỉnh lại chứ bác. Hoặc làm đủ nhiều thì tự nhớ thoai
Tính hơi ẩu nên hay ăn bug mấy chỗ tràn số, dùng python nhẹ nhàng hẳnChắc em cũng học Python dần :v chứ code Java mà đi interview hơi lâu
.phát cuối code k kịp chứ xử lý 4 điểm thẳng hàng bù trừ thôi 
total*total-total_sqr) // 2)
may sáng nay k kịp làm
Check theo trung điểm chứ k check theo cạnh song song nữa bácKo biết tìm hình thang mà 2 cạnh song song như thế nào để loại ra
Mình thì ko biết tính cái hình bình thang mà có 4 cạnh song song như thế nào để loại, đen vl.Bài 4 này khoai thật
Tìm hình thang thì xử lý cho đuae về cạnh song song (dùng set bằng ptdt để check)
Tìm hình bình hành check đếm số trung điểm trùng nhau
Nhưng cái lỏ ở chỗ check hình bình hành thì còn case 4 điểm thẳng hàng nữa
class Solution:
def countTrapezoids(self, points: List[List[int]]) -> int:
def get_line_equation(x1, y1, x2, y2):
a = y2 - y1
b = x1 - x2
c = x2 * y1 - x1 * y2
gcd = math.gcd(math.gcd(abs(a), abs(b)), abs(c))
if a == 0:
return 0.0, 1.0, c/b
else:
return 1.0, 0.0 if b == 0 else b/a, c/a
n = len(points)
lines = defaultdict(set)
for i in range(n):
for j in range(i+1, n):
a, b, c = get_line_equation(points[0], points[1], points[j][0], points[j][1])
lines[(a, b, c)].add((points[0], points[1]))
lines[(a, b, c)].add((points[j][0], points[j][1]))
parallel = defaultdict(list)
for key, value in lines.items():
parallel[(key[0], key[1])].append(len(value))
total_count = 0
for _, value in parallel.items():
total = 0
total_sqr = 0
for count in value:
pairs = (count*(count-1))//2
total+= pairs
total_sqr+= pairs*pairs
total_count+
def count_parallelogram()->int:
count = defaultdict(int)
for i in range(n):
for j in range(i+1, n):
mid_point = (points[0]+points[j][0], points[j][1]+points[1])
count[mid_point]+=1
total_parallelogram = 0
for _, value in count.items():
if value >= 2:
total_parallelogram += value*(value-1)//2
for _, point in lines.items():
p = len(point)
if p < 4:
continue
else:
mids = defaultdict(int)
point_line = list(point)
for i in range(p):
for j in range(i+1, p):
mid_point = (point_line[0]+point_line[j][0], point_line[j][1]+point_line[1])
mids[mid_point]+=1
for _, value in mids.items():
if value >= 2:
total_parallelogram -= value*(value-1)//2
return total_parallelogram
return total_count - count_parallelogram()
Không khó lắm nhưng dài, thôi an phận top 888 zay, húp dc bài này là lên 2 lốp
Em trễ bài cuối đúng 1p, thốn vl.Mình thì ko biết tính cái hình bình thang mà có 4 cạnh song song như thế nào để loại, đen vl.
Đm bài 3 optimize tí chỗ tính length mà code ngu dính cái bug mãi mới nhìn thấy
Q4 implement thốn hết cả đít
Cho hỏi tý fen đã apply thằng big tech nào chưa. Chứ 3Q đều thì mình nghĩ là đủ tự tin pass phỏng vấn nhiều thằng rồi đấy.
