船员专用网站开发建议,wordpress 图片占用id,北京网站建设有哪些公司,西安知名互联网公司记录了初步解题思路 以及本地实现代码#xff1b;并不一定为最优 也希望大家能一起探讨 一起进步 目录 8/28 57. 插入区间8/29 823. 带因子的二叉树8/30 1654. 到家的最少跳跃次数8/31 1761. 一个图中连通三元组的最小度数9/1 2240. 买钢笔和铅笔的方案数9/2 2511. 最多可以摧…记录了初步解题思路 以及本地实现代码并不一定为最优 也希望大家能一起探讨 一起进步 目录 8/28 57. 插入区间8/29 823. 带因子的二叉树8/30 1654. 到家的最少跳跃次数8/31 1761. 一个图中连通三元组的最小度数9/1 2240. 买钢笔和铅笔的方案数9/2 2511. 最多可以摧毁的敌人城堡数目9/3 1921. 消灭怪物的最大数量 8/28 57. 插入区间 找到新区间起点位置 和终点位置对应的区间位置 def insert(intervals, newInterval)::type intervals: List[List[int]]:type newInterval: List[int]:rtype: List[List[int]]ret []if len(intervals)0:ret.append(newInterval)return retnow newIntervalfor i in range(len(intervals)):v intervals[i]if v[1] now[0]:ret.append(v)continueelif now[1] v[0]:ret.append(now)ret.extend(intervals[i:])breaknow[0] min(v[0],now[0])now[1] max(v[1],now[1])if len(ret)0 or now[0] ret[-1][1]:ret.append(now)return ret 8/29 823. 带因子的二叉树 将数值从小到大排序 dp[i] 代表以arr[i]为根节点能够得到的树个数 从小到大考虑 def numFactoredBinaryTrees(arr)::type arr: List[int]:rtype: intMOD 10**97arr.sort()n len(arr)dp [1]*nidx {arr[i]:i for i in range(n)}for i,v in enumerate(arr):for j in range(i):x arr[j]if x*xv:breakif x*xv:dp[i] (dp[i]dp[j]*dp[j])%MODbreakif v%x0 and v//x in idx:dp[i](dp[i]dp[j]*dp[idx[v//x]]*2)%MODreturn sum(dp)%MOD 8/30 1654. 到家的最少跳跃次数 BFS 标记当前往前为1 往后为-1 如果ab 当前位置超过xb之后必定再也到不了x 如果ab x最大为2000 不超过6000 def minimumJumps(forbidden, a, b, x)::type forbidden: List[int]:type a: int:type b: int:type x: int:rtype: ints set(forbidden)ans 0l [(0,1)]mem{(0,1)}while l:tmp []for loc,k in l:if locx:return ansnxt [(loca,1)]if k1:nxt.append((loc-b,-1))for i,k in nxt:if i not in s and 0i6000 and (i,k) not in mem:tmp.append((i,k))mem.add((i,k))ans1ltmpreturn -1 8/31 1761. 一个图中连通三元组的最小度数 m[i][j]记录i,j的连通情况 deg[i] 记录i的出度 def minTrioDegree(n, edges)::type n: int:type edges: List[List[int]]:rtype: intdeg [0]*nm [[0]*n for i in range(n)]for x,y in edges:x,y x-1,y-1m[x][y] m[y][x] 1deg[x]1deg[y]1ans float(inf)for i in range(n):for j in range(i1,n):if m[i][j]1:for k in range(j1,n):if m[i][k]m[j][k]1:ans min(ans,deg[i]deg[j]deg[k]-6)return -1 if ansfloat(inf) else ans 9/1 2240. 买钢笔和铅笔的方案数 遍历可以买钢笔的个数 累加各个情况下可以买铅笔的个数 def waysToBuyPensPencils(total, cost1, cost2)::type total: int:type cost1: int:type cost2: int:rtype: intans 0for i in range(total//cost1):ans (total -i*cost1)//cost21return ans 9/2 2511. 最多可以摧毁的敌人城堡数目 从头遍历记录前一个自己城堡位置x 和 空位置y def captureForts(forts)::type forts: List[int]:rtype: intx,y-1,-1ans 0for i,v in enumerate(forts):if v-1:if x-1:ans max(i-1-x,ans)x,y-1,ielif v1:if y-1:ans max(i-1-y,ans)x,yi,-1return ans 9/3 1921. 消灭怪物的最大数量 计算每个怪物到城市的时间 从小到大排序 遍历每个怪物是否能在其到达前被消灭 def eliminateMaximum(dist, speed)::type dist: List[int]:type speed: List[int]:rtype: intn len(dist)t[0]*nfor i in range(n):t[i] dist[i]*1.0/speed[i]t.sort()ans 0for i,v in enumerate(t):if iv:ans1else:breakreturn ans
