thảo luận Leetcode contest, đường tới Guardian
- Thread starter freedom.9
- Start date
hieunm3538
Senior Member
Cố lên bác, thế này đến tháng 5 là lên Knight rùi kkkkk
freedom.9
Senior Member
Đến hẹn lại lên, knight đang chờ toy tới 
sắp thoát kiếp Vozlit rồi.
Mấy thằng ăn huy hiệu tháng sắp bị toy khinh
via theNEXTvoz for iPhone
sắp thoát kiếp Vozlit rồi.Mấy thằng ăn huy hiệu tháng sắp bị toy khinh
via theNEXTvoz for iPhone
freedom.9
Senior Member
Chỉ có vô contest múc nhau mới biết thực lực, còn tất cả chỉ là hư khôngView attachment 2374169
K làm live contest được, nay rảnh ngồi làm hết mấy bài trong 2 contest gần đây.
Cái bài 3068 làm mãi không ra đọc solution muốn đập bàn,
via theNEXTvoz for iPhone
seastar
Member
Trình còi thì phải tu luyện thêm thoai,
freedom.9
Senior Member
Cứu với ae sao cách giải của mình nó TLE nhỉ, rõ ràng code chỉ có O 5*n mà ta
À hiểu rồi, chắc concat nó lại thành ra On^2 cmnr, cay thật để optimize lại
Viết kiểu này lại pass ko hiểu kiểu gì ta? sao hàm sort lại nhanh hơn O(n) nhỉ, hay là do merge sort Ologn nhanh hơn
sao cách giải của mình nó TLE nhỉ, rõ ràng code chỉ có O 5*n mà ta
Python:
class Solution:
def placedCoins(self, edges: List[List[int]], cost: List[int]) -> List[int]:
n = len(edges) + 1
coins = [1] * n
graph = defaultdict(list)
for edge in edges:
graph[edge[0]].append(edge[1])
graph[edge[1]].append(edge[0])
def dfs(node, parent):
def getCoins(items):
min1 = inf
min2 = inf
max1 = -inf
max2 = -inf
max3 = -inf
for item in items:
if item >= max1:
max3 = max2
max2 = max1
max1 = item
elif item >= max2:
max3 = max2
max2 = item
elif item >= max3:
max3 = item
if item <= min1:
min2 = min1
min1 = item
elif item <= min2:
min2 = item
return [min2, min1, max3, max2, max1]
items = [cost[node]]
for neighbor in graph[node]:
if neighbor != parent:
items += dfs(neighbor, node)
if len(items) >= 3:
ans = getCoins(items)
coins[node] = max(ans[0] * ans[1] * ans[4], ans[2] * ans[3] * ans[4], 0)
return items
dfs(0, -1)
return coinsViết kiểu này lại pass ko hiểu kiểu gì ta? sao hàm sort lại nhanh hơn O(n) nhỉ, hay là do merge sort Ologn nhanh hơn
Python:
from collections import defaultdict
from math import inf
from typing import List
class Solution:
def placedCoins(self, edges: List[List[int]], cost: List[int]) -> List[int]:
n = len(edges) + 1
coins = [1] * n
graph = defaultdict(list)
for edge in edges:
graph[edge[0]].append(edge[1])
graph[edge[1]].append(edge[0])
def dfs(node, parent):
items = [cost[node]]
for neighbor in graph[node]:
if neighbor != parent:
items += dfs(neighbor, node)
items = sorted(items)
if len(items) >= 3:
coins[node] = max(0, items[-1] * max(items[0] * items[1], items[-3] * items[-2]))
return items
dfs(0, -1)
return coins
Last edited:
RTX3090
Senior Member
cho tham khảo tí mai fenQ3 dễ vậy mà tốn tgian quá, đáng ra xong nửa nốt nhạc rồicay thật huhu
freedom.9
Senior Member
brute force fence ơi, constrain thấp. Loop đầu lưu hết sub array vô dictionary.
loop2 kiểm tra
Violet_7
Senior Member
em ms nghĩ đến đoạn tách ra các mảng toàn dương và toàn âm. nhưng mà lúc sau lại sai logic nên thôiCâu cuối Gang vcl, n*k < 10^6 nhưng mà phải làm là disjoin sub array thì sao mà làm dp
Có trick gì ở đây à ta
youknowwho151
Senior Member
Mới ôn lại DSA 2 tuần.
Tuần trước Q1 gang mà tuần này Q3 gang rồi anh em.
LET'S GOOOOOOOOOOOOOO
Tuần trước Q1 gang mà tuần này Q3 gang rồi anh em.
LET'S GOOOOOOOOOOOOOO
freedom.9
Senior Member
Hay phải tìm maximum subarray ở trong 1 đoạn từ i đến j để xài DP nhỉ. Ko có hướng làm nào cả
em ms nghĩ đến đoạn tách ra các mảng toàn dương và toàn âm. nhưng mà lúc sau lại sai logic nên thôi
humanversion9x
Junior Member
Mình tính làm kiểu quy hoạch động (k, nums.size()). Nhưng nếu làm thế thì Time complexity : O(n* nums.size() * nums.size()) thì sẽ bị TLE ngay cả khi đã tính prefix sum. Mình cố nghĩ cách để optimize mà không ra.em ms nghĩ đến đoạn tách ra các mảng toàn dương và toàn âm. nhưng mà lúc sau lại sai logic nên thôi
freedom.9
Senior Member
Nếu như DP k, nums.size() thì vô tư vì constrain nói rõ là <= 10^6
Nhưng mà ko tìm ra state transition thôi fence ơi
humanversion9x
Junior Member
Nhưng mỗi khi xét một idx thì phải kiểm tra các idx trước đó để xem cái nào cho ra max.Nếu như DP k, nums.size() thì vô tư vì constrain nói rõ là <= 10^6
Nhưng mà ko tìm ra state transition thôi fence ơi
Similar threads
- Locked
