.net做网站教程,全国做临期进口食品的网站,水果网站源码,wordpress文章页文件记录了初步解题思路 以及本地实现代码#xff1b;并不一定为最优 也希望大家能一起探讨 一起进步 目录 9/11 630. 课程表 III9/12 1462. 课程表 IV9/13 2596. 检查骑士巡视方案9/14 1222. 可以攻击国王的皇后9/15 LCP 50. 宝石补给9/16 198. 打家劫舍9/17 9/11 630. 课程表 II…记录了初步解题思路 以及本地实现代码并不一定为最优 也希望大家能一起探讨 一起进步 目录 9/11 630. 课程表 III9/12 1462. 课程表 IV9/13 2596. 检查骑士巡视方案9/14 1222. 可以攻击国王的皇后9/15 LCP 50. 宝石补给9/16 198. 打家劫舍9/17 9/11 630. 课程表 III 将期限日期从小到大排序 将耗时放入大顶堆中 如果当前耗时无法满足 但是比堆中最大值小时 进行替换 def scheduleCourse(courses)::type courses: List[List[int]]:rtype: intimport heapql[]heapq.heapify(l)courses.sort(key lambda x:x[1])now 0for d,last in courses:if nowdlast:now dheapq.heappush(l,-d)elif l and -l[0]d:now nowl[0]dheapq.heappop(l)heapq.heappush(l,-d)return len(l) 9/12 1462. 课程表 IV m[i][j]记录i是否依赖j dg[i]记录当前i是否还有依赖未考虑 g[i]记录i依赖的课程 bfs l中存放当前无课程依赖可以考虑的课程 def checkIfPrerequisite(numCourses, prerequisites, queries)::type numCourses: int:type prerequisites: List[List[int]]:type queries: List[List[int]]:rtype: List[bool]m [[False]*numCourses for _ in range(numCourses)]dg [0]*numCoursesg [[] for _ in range(numCourses)]for p in prerequisites:dg[p[1]] 1g[p[0]].append(p[1])l []for i in range(numCourses):if dg[i]0:l.append(i)while l:tmp []for cur in l:for nx in g[cur]:m[cur][nx] Truefor i in range(numCourses):m[i][nx] m[i][cur] or m[i][nx]dg[nx]-1if dg[nx]0:tmp.append(nx)l tmpans []for q in queries:ans.append(m[q[0]][q[1]])return ans 9/13 2596. 检查骑士巡视方案 规定从左上角出发 判断grid[0][0]是否为0 从当前位置向八个方向遍历是否能够到达下一个点 def checkValidGrid(grid)::type grid: List[List[int]]:rtype: boolx,y0,0n len(grid)if grid[0][0]!0:return Falsesteps[(2,1),(2,-1),(-2,1),(-2,-1),(1,2),(1,-2),(-1,2),(-1,-2)]cur 0while curn*n-1:tag Truefor i,j in steps:nx,ny xi,yjif 0nxn and 0nyn and grid[nx][ny]cur1:cur 1x,ynx,nytag Falsebreakif tag:return Falsereturn True 9/14 1222. 可以攻击国王的皇后 mem记录八个方向皇后可以攻击到国王的最近距离 def queensAttacktheKing(queens, king)::type queens: List[List[int]]:type king: List[int]:rtype: List[List[int]]mem {} for x,y in queens:i,j0,0v 0if xking[0]:v abs(y-king[1])j (y-king[1])//velif yking[1]:v abs(x-king[0])i (x-king[0])//velse:v abs(x-king[0])if v!abs(y-king[1]):continuei (x-king[0])//vj (y-king[1])//vif (i,j) not in mem:mem[(i,j)] velse:if vmem[(i,j)]:mem[(i,j)] vans []for (i,j),v in mem.items():ans.append([king[0]i*v,king[1]j*v])return ans 9/15 LCP 50. 宝石补给 按照规则依次赠送 def giveGem(gem, operations)::type gem: List[int]:type operations: List[List[int]]:rtype: intfor x,y in operations:v gem[x]//2gem[x]-vgem[y]vreturn max(gem)-min(gem) 9/16 198. 打家劫舍 使用一个maxlist记录 进入当前x位置的房间能够得到的最大价值 可知前一个位置无法获取 所以在x时 可以通过[0,x-2]之间的最大值加上x的值获得该位置最大值 而在maxlist中最大的值必定是在最后两个位置 n,n-1 因为位置n的值必定大于n-2的值 所以我们只要比较maxlist中x-3,x-2这两个位置的值 就可以得到[0,x-2]之间的最大值 def rob(nums)::type nums: List[int]:rtype: intmaxlist[]res 0for i in range(len(nums)):if i2:tmp max(maxlist[i-3],maxlist[i-2])nums[i]maxlist.append(tmp)elif i2:tmp maxlist[0]nums[i]maxlist.append(tmp)else:tmp nums[i]maxlist.append(nums[i])res max(res,tmp)return res 9/17
