记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步

---

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

---