今天的
就從後面滑過來
def minimumSteps(self, s: str) -> int:
cost, ans = 0, 0
for i in range(len(s)-1, -1, -1):
if s[i] == "1":
ans += cost
elif s[i] == "0":
cost += 1
return ans
不知道哪一天的
我直接用兩個pq搞==
好麻煩
def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:
times = [(time, idx) for idx, time in enumerate(times)]
times.sort()
empty_pq = []
occupy_pq = []
for time, idx in times:
while len(occupy_pq)>0 and occupy_pq[0][0]<=time[0]:
_, chair_idx = heappop(occupy_pq)
heappush(empty_pq, chair_idx)
if len(empty_pq)==0:
cur_chair_idx = len(occupy_pq)
else:
cur_chair_idx = heappop(empty_pq)
if idx==targetFriend:
return cur_chair_idx
heappush(occupy_pq, (time[1], cur_chair_idx))
return -1
不知道哪天的
直接用meeting room的方式
找重疊區間最多的地方
def minGroups(self, intervals: List[List[int]]) -> int:
q = []
for interv in intervals:
# -1 for left, 1 for right
q.append((interv[0], -1))
q.append((interv[1], 1))
q.sort()
ans, cur_cnt = 0, 0
for num, flag in q:
if flag==-1:
cur_cnt += 1
else:
cur_cnt -= 1
ans = max(ans, cur_cnt)
return ans
不知道哪天的
直接硬幹
def maxKelements(self, nums: List[int], k: int) -> int:
pq = []
for num in nums:
heappush(pq, -num)
ans = 0
for _ in range(k):
cur = heappop(pq) * -1
ans += cur
heappush(pq, -(ceil(cur/3)))
return ans