LeetCode 每日一题 2023/8/28-2023/9/3

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

---

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: int"""MOD = 10**9+7arr.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*x>v:breakif x*x==v:dp[i]= (dp[i]+dp[j]*dp[j])%MODbreakif v%x==0 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
如果a>b 当前位置超过x+b之后必定再也到不了x
如果a<b x最大为2000 不超过6000

def minimumJumps(forbidden, a, b, x):""":type forbidden: List[int]:type a: int:type b: int:type x: int:rtype: int"""s = set(forbidden)ans = 0l = [(0,1)]mem={(0,1)}while l:tmp = []for loc,k in l:if loc==x:return ansnxt = [(loc+a,1)]if k==1:nxt.append((loc-b,-1))for i,k in nxt:if i not in s and 0<=i<6000 and (i,k) not in mem:tmp.append((i,k))mem.add((i,k))ans+=1l=tmpreturn -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: int"""deg = [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(i+1,n):if m[i][j]==1:for k in range(j+1,n):if m[i][k]==m[j][k]==1:ans = min(ans,deg[i]+deg[j]+deg[k]-6)return -1 if ans==float("inf") else ans

---

9/1 2240. 买钢笔和铅笔的方案数

遍历可以买钢笔的个数 累加各个情况下可以买铅笔的个数

def waysToBuyPensPencils(total, cost1, cost2):""":type total: int:type cost1: int:type cost2: int:rtype: int"""ans = 0for i in range(total//cost1):ans += (total -i*cost1)//cost2+1return ans

---

9/2 2511. 最多可以摧毁的敌人城堡数目

从头遍历记录前一个自己城堡位置x 和 空位置y

def captureForts(forts):""":type forts: List[int]:rtype: int"""x,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 v==1:if y>-1:ans = max(i-1-y,ans)x,y=i,-1return ans

---

9/3 1921. 消灭怪物的最大数量

计算每个怪物到城市的时间 从小到大排序
遍历每个怪物是否能在其到达前被消灭

def eliminateMaximum(dist, speed):""":type dist: List[int]:type speed: List[int]:rtype: int"""n = 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 i<v:ans+=1else:breakreturn ans

---