Re: [閒聊] 每日leetcode
看板Marginalman作者DJYOMIYAHINA (通通打死)時間11月前 (2024/12/29 18:22)推噓1(1推 0噓 0→)留言1則, 1人參與討論串1228/1554 (看更多)
不知道哪一天的
2593. Find Score of an Array After Marking All Elements
就照做 用priority queue
看別人寫O(N) 但我看不是很懂 懶得研究了 對不起
def findScore(self, nums: List[int]) -> int:
st = set()
hp = []
for i,num in enumerate(nums):
heappush(hp, (num, i))
ans = 0
while hp:
cur_num, cur_idx = heappop(hp)
if cur_idx not in st:
ans += cur_num
st.add(cur_idx)
st.add(cur_idx-1)
st.add(cur_idx+1)
return ans
不知道哪一天的
2762. Continuous Subarrays
雞掰
就感覺卡在一個地方想不出來
偷偷看關鍵字
用兩個monotonic queue去maintain subarr的maximum跟minimum
然後加以操作
有點刁鑽
def continuousSubarrays(self, nums: List[int]) -> int:
l=0
ans=0
increaseD, decreaseD = deque(), deque()
for r in range(len(nums)):
while increaseD and nums[increaseD[-1]]>=nums[r]:
increaseD.pop()
while decreaseD and nums[decreaseD[-1]]<=nums[r]:
decreaseD.pop()
decreaseD.append(r)
increaseD.append(r)
while nums[decreaseD[0]]-nums[increaseD[0]]>2:
l += 1
if decreaseD[0]<l:
decreaseD.popleft()
if increaseD[0]<l:
increaseD.popleft()
ans += (r-l+1)
return ans
不知道哪一天的
1792. Maximum Average Pass Ratio
就一樣pq硬搞
懶得想其他方法了
寫得有點雜亂
def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) ->
float:
pq = []
for idx, classs in enumerate(classes):
heappush(pq, (classs[0]/classs[1]-(classs[0]+1)/(classs[1]+1), idx))
for _ in range(extraStudents):
_, idx = heappop(pq)
classes[idx][0] += 1
classes[idx][1] += 1
heappush(pq,
(classes[idx][0]/classes[idx][1]-(classes[idx][0]+1)/(classes[idx][1]+1),
idx))
return sum([passs/total for passs,total in classes])/len(classes)
今天的hard晚點有空再說
但大機率懶得搞 對不起
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.79.52.230 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1735467724.A.D4C.html
推
12/29 18:22,
11月前
, 1F
12/29 18:22, 1F
討論串 (同標題文章)
完整討論串 (本文為第 1228 之 1554 篇)：