记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步
目录
4/291146. 快照数组
快照时无需记录整个数组
只要记录与前一份快照之间的修改
使用history[x]记录x位置元素的修改记录(snapid,value)
查询一个ind位置某个id的数据时
只要在history[ind]中二分找到快照编号小于id的最后一条修改记录值即可
class SnapshotArray(object):
def __init__(self, length):
"""
:type length: int
"""
from collections import defaultdict
self.curid = 0
self.history = defaultdict(list)
def set(self, index, val):
"""
:type index: int
:type val: int
:rtype: None
"""
self.history[index].append((self.curid,val))
def snap(self):
"""
:rtype: int
"""
self.curid +=1
return self.curid-1
def get(self, index, snap_id):
"""
:type index: int
:type snap_id: int
:rtype: int
"""
import bisect
j = bisect.bisect_left(self.history[index], (snap_id+1,))-1
return self.history[index][j][1] if j>=0 else 0
4/30 2798. 满足目标工作时长的员工数目
依次遍历判断是否达到要求
def numberOfEmployeesWhoMetTarget(hours, target):
"""
:type hours: List[int]
:type target: int
:rtype: int
"""
ans = 0
for h in hours:
if h>=target:
ans+=1
return ans
5/1 2462. 雇佣 K 位工人的总代价
建立两个最小堆 如果左右可选择个数加上被选择k个包含了所有的数值
那么直接返回最小的k个数之和即可
def totalCost(costs, k, candidates):
"""
:type costs: List[int]
:type k: int
:type candidates: int
:rtype: int
"""
import heapq
n = len(costs)
if candidates*2+k>n:
costs.sort()
return sum(costs[:k])
pre = costs[:candidates]
suf = costs[-candidates:]
heapq.heapify(pre)
heapq.heapify(suf)
ans = 0
l,r=candidates,n-candidates-1
for _ in range(k):
if pre[0]<=suf[0]:
ans += heapq.heapreplace(pre, costs[l])
l+=1
else:
ans += heapq.heapreplace(suf, costs[r])
r-=1
return ans
5/2 857. 雇佣 K 名工人的最低成本
r=wage/quality
单位工作质量的工资从小到大排序
假设k个工人质量和为sumQ 以r为基准发工资 那么总额为sumQ*r
最大堆维护k个quality 获取更小的sumQ
def mincostToHireWorkers(quality, wage, k):
"""
:type quality: List[int]
:type wage: List[int]
:type k: int
:rtype: float
"""
import heapq
qw = sorted(zip(quality,wage),key = lambda x:1.0*x[1]/x[0])
h = [-q for q,_ in qw[:k]]
heapq.heapify(h)
totalq = -sum(h)
ans = totalq*1.0*qw[k-1][1]/qw[k-1][0]
for q,w in qw[k:]:
if q<-h[0]:
totalq += heapq.heapreplace(h,-q)+q
ans = min(ans,totalq*1.0*w/q)
return ans
5/3 1491. 去掉最低工资和最高工资后的工资平均值
求总和 最大值 最小值
def average(salary):
"""
:type salary: List[int]
:rtype: float
"""
s = sum(salary)
minv = min(salary)
maxv = max(salary)
n = len(salary)
return (s-minv-maxv)/(n-2)
5/4 1235. 规划兼职工作
将工作按结束时间从小到大排列
dp[i]记录截止前i个工作能获得的最大收益
第i-1份工作可以选择做 或者 不做
选择做则需要找到结束时间小于等于开始时间的位置
def jobScheduling(startTime, endTime, profit):
"""
:type startTime: List[int]
:type endTime: List[int]
:type profit: List[int]
:rtype: int
"""
n = len(startTime)
job = sorted(zip(startTime,endTime,profit),key = lambda x:x[1])
dp = [0]*(n+1)
li = sorted(endTime)
def find(r,v):
l = 0
while l<=r:
mid = (l+r)>>1
if li[mid]> v:
r = mid-1
else:
l = mid+1
return l
for i in range(1,n+1):
k = find(i,job[i-1][0])
dp[i] = max(dp[i-1],dp[k]+job[i-1][2])
return dp[n]
5/5 1652. 拆炸弹
三种情况分别判断
def decrypt(code, k):
"""
:type code: List[int]
:type k: int
:rtype: List[int]
"""
n = len(code)
ans = [0]*n
if k>0:
cur = sum(code[:k])
for i in range(n):
cur = cur-code[i]+code[(k+i)%n]
ans[i] = cur
elif k<0:
cur = sum(code[n+k:])
for i in range(n):
ans[i] = cur
cur = cur+code[i]-code[(n+k+i)%n]
return ans