长沙seo网站优化,如何做网站排名第一,宿州市做网站的公司,html5手机网站开发教程记录了初步解题思路 以及本地实现代码#xff1b;并不一定为最优 也希望大家能一起探讨 一起进步 目录 7/24 771. 宝石与石头7/25 2208. 将数组和减半的最少操作次数7/26 2569. 更新数组后处理求和查询7/27 2500. 删除每行中的最大值7/28 2050. 并行课程 III7/29 141. 环形链表…记录了初步解题思路 以及本地实现代码并不一定为最优 也希望大家能一起探讨 一起进步 目录 7/24 771. 宝石与石头7/25 2208. 将数组和减半的最少操作次数7/26 2569. 更新数组后处理求和查询7/27 2500. 删除每行中的最大值7/28 2050. 并行课程 III7/29 141. 环形链表7/30 7/24 771. 宝石与石头 将宝石类型放入set中 一次判断石头中宝石个数 def numJewelsInStones(jewels, stones)::type jewels: str:type stones: str:rtype: intj set(jewels)ans 0for s in stones:if s in j:ans1return ans 7/25 2208. 将数组和减半的最少操作次数 大顶堆记录当前最大值 每次取最大值减半 def halveArray(nums)::type nums: List[int]:rtype: intimport heapqtarget sum(nums)*1.0/2l []for num in nums:heapq.heappush(l,-num)cur 0ans 0while True:v -heapq.heappop(l)cur v*1.0/2ans1if curtarget:breakheapq.heappush(l,-v*1.0/2)return ans 7/26 2569. 更新数组后处理求和查询 操作1是将nums1中[l,r]的数反转 操作2是将nums2的和加上p*sum(nums1) 操作3是求nums2的和 只要考虑nums1的变化即可 线段树维护nums1区间 l,r左右端点 s区间和 lazy懒标记 class Node:def __init__(self):self.lself.r0self.s 0self.lazy 0
class SegmentTree:def __init__(self,nums):self.nums numsn len(nums)self.tr [Node() for _ in range(n2)]self.build(1,1,n)def build(self,u,l,r):self.tr[u].l,self.tr[u].rl,rif lr:self.tr[u].s self.nums[l-1]returnmid (lr)1self.build(u1,l,mid)self.build(u1|1,mid1,r)self.pushup(u)def modify(self,u,l,r):if self.tr[u].ll and self.tr[u].rr:self.tr[u].lazy^1self.tr[u].s self.tr[u].r-self.tr[u].l1-self.tr[u].sreturnself.pushdown(u)mid (self.tr[u].lself.tr[u].r)1if lmid:self.modify(u1,l,r)if rmid:self.modify(u1|1,l,r)self.pushup(u)def query(self,u,l,r):if self.tr[u].ll and self.tr[u].rr:return self.tr[u].sself.pushdown(u)mid (self.tr[u].lself.tr[u].r)1ans 0if lmid:ans self.query(u1,l,r)if rmid:ans self.query(u1|1,l,r)return ansdef pushup(self,u):self.tr[u].s self.tr[u1].sself.tr[u1|1].sdef pushdown(self,u):if self.tr[u].lazy:mid (self.tr[u].lself.tr[u].r)1self.tr[u1].s mid-self.tr[u].l1-self.tr[u1].sself.tr[u1].lazy^1self.tr[u1|1].s self.tr[u].r-mid-self.tr[u1|1].sself.tr[u1|1].lazy^1self.tr[u].lazy^1def handleQuery(nums1, nums2, queries)::type nums1: List[int]:type nums2: List[int]:type queries: List[List[int]]:rtype: List[int]tr SegmentTree(nums1)s sum(nums2)ans []for op,l,r in queries:if op1:tr.modify(1,l1,r1)elif op2:sl*tr.query(1,1,len(nums1))else:ans.append(s)return ans 7/27 2500. 删除每行中的最大值 每一行从小到大排序 再取每一列的最大值 def deleteGreatestValue(grid)::type grid: List[List[int]]:rtype: intcur []for l in grid:cur.append(sorted(l))return sum([max([cur[i][j] for i in range(len(cur))]) for j in range(len(grid[0]))]) 7/28 2050. 并行课程 III m[i]记录课程i为多少课程的前置课程 ind[i]记录课程i有几个前置课程 t[i]记录课程i的最早完成时间 def minimumTime(n, relations, time)::type n: int:type relations: List[List[int]]:type time: List[int]:rtype: intfrom collections import defaultdictm defaultdict(list)ind[0]*nfor pre,nxt in relations:m[pre-1].append(nxt-1)ind[nxt-1]1l []t[0]*nans 0for i in range(n):if ind[i]0:l.append(i)t[i]time[i]ans max(ans,t[i])while l:tmp []for i in l:for j in m[i]:t[j] max(t[j],t[i]time[j])ans max(ans,t[j])ind[j]-1if ind[j]0:tmp.append(j)ltmpreturn ans 7/29 141. 环形链表 快慢指针 class ListNode(object):def __init__(self, x):self.val xself.next None
def hasCycle(head)::type head: ListNode:rtype: boolif headNone or head.nextNone:return Falseslow headfast head.nextwhile(slow!fast):if fastNone or fast.nextNone:return Falseslowslow.nextfastfast.next.nextreturn True 7/30
