Q2 em làm 2 mảng from và to để đếm số lượng mảng bắt đầu / kết thúc tại i. Rồi chạy từ 0 -> n-1 để đếm số lượng mảng chứa i bằng cách cộng from_i và trừ đi to của i-1. Q3 thì thay vì đếm số lượng thì là tổng val của các query.Q3 giải được bằng line sweep á, tại mình nghĩ cái thuật toán này cần sort range, mà đề yêu cầu queries in sequence nên ko theo hướng này
ah tks bác, thế cái line sweep mà 10**5 thì mình chạy từ 0->10**5 là coi như sort luôn mà vẫn O(N)Line sweep thì thường ko cần phải sort mà nếu constrain thấp thì bác có thể brute force từ 0 -> 10**5 được mà, nếu 10**9 là max number ở trong lines thì mới cần sort
Có ý tưởng mà code ko ra nó thốn, thấy bài 8 điểm là té đái cmnr. Mấy thằng top code cũng gần giống ý tưởng của mình
Chính xác đó bác, còn nếu như 10**9 thì chắc chắn phải sort thôiah tks bác, thế cái line sweep mà 10**5 thì mình chạy từ 0->10**5 là coi như sort luôn mà vẫn O(N)
bài 3 bọn nó brute force kiểu binary search trên result, cái này làm suốt mà ko nghĩ đến
Xem tệp đính kèm 2786288
Cảm giác ý tưởng mình gần giống ý tưởng tụi top mà mình sai cay vl, tụi nó ăn gì giỏi thếLine sweep thì thường ko cần phải sort mà nếu constrain thấp thì bác có thể brute force từ 0 -> 10**5 được mà, nếu 10**9 là max number ở trong lines thì mới cần sort
Có ý tưởng mà code ko ra nó thốn, thấy bài 8 điểm là té đái cmnr. Mấy thằng top code cũng gần giống ý tưởng của mình
Vẫn là skill issue thôi tập luyện thêm
chơi acc chính luôn bác sợ àVẫn là skill issue thôi tập luyện thêm
Tụi Leetcode nó éo ra cái phone verification nhỉ nhìn cheaters hãi quá ko dám xài nick chính thi luôn
Q3 bọn nó segment tree được bác, hàm ko phải là sum mà dùng hàm max mới ngonKo bác, ko giải segment tree được vì là range update xong rồi phải tính sum toàn bộ bằng range query và loại bỏ thằng nào < -1 nên chắc chắn TLE. Q2 mình đâm đầu vô segment tree mà quên mẹ mất là cái giá trị dưới 0 thì tính sum chết mẹ nó mất ko loại trừ được
Q2 thực ra là giải đc segment tree nhưng mà mình quên mẹ mất ko loop từng thằng mà tính sum đúng ngu mất mẹ 20ph cuộc đời
Q3 thì chỉ cần binary search thôi, dùng line sweep như Q2 sẽ cho time complexity Onlogn là ănPython:class SegmentTree: def __init__(self, nums): n = len(nums) self.n = n self.tree = [0]*n + nums for i in range(n - 1, -1, -1): self.tree[i] = self.tree[i*2] + self.tree[i*2 + 1] def update(self, index, val): index += self.n if index >= len(self.tree): return self.tree[index] += val while index > 1: index //= 2 self.tree[index] = self.tree[index*2] + self.tree[index*2 + 1] def query(self, index): left = self.n right = index + self.n + 1 ans = 0 while left < right: if left & 1: ans += self.tree[left] left += 1 if right & 1: right -= 1 ans += self.tree[right] left//=2 right//=2 return ans class Solution: def isZeroArray(self, nums: List[int], queries: List[List[int]]) -> bool: n = len(nums) diff = [0]*n diff[0] = nums[0] for i in range(1, n): diff[i] = nums[i] - nums[i - 1] seg = SegmentTree(diff) for left, right in queries: seg.update(left, -1) seg.update(right + 1, +1) sumSofar = 0 for i in range(n): if seg.query(i) > 0: return False return True
class Node:
def __init__(self, l, r):
self.l = l
self.r = r
self.mid = (l + r) >> 1
self.v = 0
self.lazy = 0
self.left = None
self.right = None
class SegmentTree:
def __init__(self, arr):
self.arr = arr
self.root = self._build(0, len(arr) - 1)
def _build(self, l, r):
node = Node(l, r)
if l == r:
node.v = self.arr[l]
return node
node.left = self._build(l, node.mid)
node.right = self._build(node.mid + 1, r)
node.v = max(node.left.v, node.right.v)
return node
def _push(self, node):
if node.lazy:
node.left.lazy += node.lazy
node.left.v = max(0, node.left.v - node.lazy)
node.right.lazy += node.lazy
node.right.v = max(0, node.right.v - node.lazy)
node.lazy = 0
def update(self, l, r, val, node=None):
if not node:
node = self.root
if r < node.l or l > node.r:
return
if l <= node.l and node.r <= r:
node.v = max(0, node.v - val)
node.lazy += val
return
self._push(node)
self.update(l, r, val, node.left)
self.update(l, r, val, node.right)
node.v = max(node.left.v, node.right.v)
def query(self, l, r, node=None):
if not node:
node = self.root
if r < node.l or l > node.r:
return 0
if l <= node.l and node.r <= r:
return node.v
self._push(node)
return max(self.query(l, r, node.left), self.query(l, r, node.right))
class Solution:
def minZeroArray(self, nums: List[int], queries: List[List[int]]) -> int:
n = len(nums)
if sum(nums) == 0:
return 0
tree = SegmentTree(nums)
for index, [l, r, val] in enumerate(queries):
tree.update(l, r, val)
total = tree.query(0, n - 1)
if total <= 0:
return index + 1
return -1Linesweep On mà, segment tree hơi khắm do quên mất cứ đi tính sum của cả đoạn thay vì check từng thằng <= 0 chứ segment tree vẫn đúng
Q2 mà mình nghĩ tới segment tree thì cũng max độ lú rồihiểu biết sâu rộng dễ nghĩ ra mấy cách làm phức tạp đấy bác
Ồ xài hàm cả update range và cả max range luôn à, mình chỉ biết tới update range và query tại 1 điểm thôi hoặc ngc lại, skill có hạn mới học lóm đc vài chiêu seg
Topic nhiều newbie quá, cố gắng vững tay chèo feed rank nhé các bácHôm nay lần đầu làm được 2 bài, bài 1 ăn 3 bọ, mong tháng sau lên được 3 bài.
e cũng mới học đc tuần này, cứ nghĩ update là hàm cộng, rồi cũng code query hàm cộng luôn, mà code hay bug vãi, toàn phải dùng chatgpt nó fix mãi mới chạy đc
Thì ra cái Lazy segment tree là để dùng cho cái này. Mà để đi interview thì cũng ko cần segment tree, còn những bài contest mà dùng Segment tree nâng cao thì khó quá nên mình cũng lười học
Cái này đương nhiên bác, nhiều yếu tố ở leetcode server nó có thể khác nhau ở runtime mỗi lần submit mà.
, cái tính điểm là web nào vậy bác
Xem tệp đính kèm 2786384
đang 1k7 mà rank 5k8 chắc +2 điểm như tuần trước, dậm chân tại chỗ quá
ơ bài 1 cũng là update cả range mà sao bác áp dụng được segment tree mà ko lazy àThì ra cái Lazy segment tree là để dùng cho cái này. Mà để đi interview thì cũng ko cần segment tree, còn những bài contest mà dùng Segment tree nâng cao thì khó quá nên mình cũng lười học
via theNEXTvoz for iPhone
Cái này đương nhiên bác, nhiều yếu tố ở leetcode server nó có thể khác nhau ở runtime mỗi lần submit mà.
Ko, bài 2 update range thì mình tính dựa vào công thức diff, build 1 segment tree dựa trên cái diff của 2 elements liên tiếp.
Vậy làm sao biết được solution của mình là tốt vậy bác, mình mới bắt đầu làm leetcode nên chưa rõ lắm
Thì phải phân tích time + space complexity, càng nhỏ càng tốt. Lớn thì sẽ bị TLE
