thảo luận Leetcode contest, đường tới Guardian
- Người tạo chủ đề freedom.9
- Ngày bắt đầu
- Trạng thái
vicejuniordev
Senior Member
Xác định hủy rồi, làm xong submit hơn 1p mới báo kết quả. Chơi bời gì
LmaoSuVuong
Senior Member
Q2 chép 1 bài đã từng làm vào làm helper có tính là cheat ko nhỉ
seastar
Member
Contest này k hủy thì hơi phí, bữa trước t làm full 4 bài bị hủy đây,
seastar
Member
Bài 4 t dùng set để tính prefix and. Hết contest mới làm xong,
Python:
class Solution:
def minimumDifference(self, nums: List[int], k: int) -> int:
ret = abs(nums[0] - k)
pre = {nums[0]}
for x in nums:
next_set = {x}
ret = min(ret, abs(x - k))
for y in pre:
next_set.add(y & x)
ret = min(ret, abs((y & x) - k))
pre = next_set
return retseastar
Member
t cũng ăn 2 bọ câu đó, cũng chỗ merge interval. Mà nay làm mãi mới xong. Đêm qua thức coi C1, sáng nay hơi ngáo,Má nó câu 2 ăn 2 bọ do merge intervals ngáo, cay thật chứ nhỉ
1 lần đặt lộn dấu 1 lần đặt lộn end.
freedom.9
Senior Member
Ủa lưu cả đống prefix vô set được hả fence, ảo thế nhỉ.Bài 4 t dùng set để tính prefix and. Hết contest mới làm xong,
Python:class Solution: def minimumDifference(self, nums: List[int], k: int) -> int: ret = abs(nums[0] - k) pre = {nums[0]} for x in nums: next_set = {x} ret = min(ret, abs(x - k)) for y in pre: next_set.add(y & x) ret = min(ret, abs((y & x) - k)) pre = next_set return ret
Má còn non quá hèn gì ko làm ra, tụi kia nó dùng dp 2 states giải cũng ra
tụi nó đi cái DP đơn giản vãi cứcCứ tưởng TLE nên phải làm sliding windows
trinity
Senior Member
b4 e cũng làm sliding window, chưa biết dp thế nàoỦa lưu cả đống prefix vô set được hả fence, ảo thế nhỉ.
Má còn non quá hèn gì ko làm ra, tụi kia nó dùng dp 2 states giải cũng ra
Cứ tưởng TLE nên phải làm sliding windows
seastar
Member
Tại vì cái AND ấy, nên nó sẽ bị trùng rất nhiều.Ủa lưu cả đống prefix vô set được hả fence, ảo thế nhỉ.
Má còn non quá hèn gì ko làm ra, tụi kia nó dùng dp 2 states giải cũng ra
Cứ tưởng TLE nên phải làm sliding windows
Thực ra hiện tại t cũng mới chỉ có cảm giác là cách sẽ pass chứ chưa thực chứng minh được. Đang ngồi nghĩ xem tại sao nó pass hay là do testcase yếu.
freedom.9
Senior Member
Mình sliding windows bị TLE còn 10 test cases cuối, tụi nó giải DP đây fence. Vì & opeartion nó bị trùng nhiều thì phải, ko hiểu sao
Python:
from functools import cache
class Solution:
def minimumDifference(self, nums: List[int], k: int) -> int:
n = len(nums)
# Recursive funtion with the current index and past bitwise AND value
@cache
def solve(idx, curr_and):
# If index reached at the end simply pass inf
if idx >= n:
return inf
# No need to check the other case since if we include curr_and it will always give us 0 value
if curr_and & nums[idx] == 0:
return min(abs(0-k), abs(nums[idx]-k), solve(idx+1, nums[idx]))
return min(abs((curr_and & nums[idx]) - k), abs(nums[idx]-k), solve(idx+1, nums[idx]), solve(idx+1, curr_and&nums[idx]))
return solve(0, nums[0])LmaoSuVuong
Senior Member
e làm bruteforce TLE có 7 testcase thôi mà sliding windows những 10 tc à bác
freedom.9
Senior Member
We know that AND operation is non-increasing in nature(constant or decreasing). so we know that
adjacent equal elements will lead to AND being constant so first just remove all equal adjacent elements and then
for each element start taking AND within a loop that will run just 31 times for each element.
Because now two adjacent elements are not equal so they would differ in atleast 1 bit making that bit 0, so in atmax
31 moves, the AND becomes 0 and then will remain 0.
So for each element, keep on performing the loop till i + 31, and stop if curr_and <= k or curr_and = 0.
TC: O(UNQ*31) where UNQ = number of distinct elements.
Vẫn còn non thật
, quá đơn giản mà ko nghĩ ra
adjacent equal elements will lead to AND being constant so first just remove all equal adjacent elements and then
for each element start taking AND within a loop that will run just 31 times for each element.
Because now two adjacent elements are not equal so they would differ in atleast 1 bit making that bit 0, so in atmax
31 moves, the AND becomes 0 and then will remain 0.
So for each element, keep on performing the loop till i + 31, and stop if curr_and <= k or curr_and = 0.
TC: O(UNQ*31) where UNQ = number of distinct elements.
Vẫn còn non thật
, quá đơn giản mà ko nghĩ ra- Trạng thái
Chủ đề tương tự
