LeetCode 每日一题 2024/7/29-2024/8/4

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

---

7/29 682. 棒球比赛

创建一个list用来储存有效分值

def calPoints(operations):""":type ops: List[str]:rtype: int"""l=[]sum = 0for i in ops:if i=="+":v = l[-1]+l[-2]l.append(v)sum+=velif i=="D":v = 2* l[-1]l.append(v)sum+=velif i=="C":v = l.pop()sum-=velse:sum += int(i)l.append(int(i))return sum

---

7/30 2961. 双模幂运算

依次判断

def getGoodIndices(variables, target):""":type variables: List[List[int]]:type target: int:rtype: List[int]"""n = len(variables)ans = []for i in range(n):a,b,c,m = variables[i]v = 1for _ in range(b):v = (v*a)%10vv = 1for _ in range(c):vv = (vv*v)%mif vv==target:ans.append(i)return ans

---

7/31 3111. 覆盖所有点的最少矩形数目

根据题意 可以不用管矩形的高度
将所有点都投射到x轴 只考虑x的大小即可
将x从小到大排序 判断需要几个w长度的线段能够覆盖所有的点

def minRectanglesToCoverPoints(points, w):""":type points: List[List[int]]:type w: int:rtype: int"""s = set()for x,_ in points:s.add(x)l = sorted(list(s))ans = 0cur = -1for x in l:if x>cur:ans+=1cur=x+wreturn ans

---

8/1 LCP 40. 心算挑战

从大到小排序
先将前cnt个数相加
如果是奇数 则将选中的
最小奇数和未选中的最大偶数替换 或者
最小偶数和未选中的最大奇数替换

def maxmiumScore(cards, cnt):""":type cards: List[int]:type cnt: int:rtype: int"""cards.sort(reverse=True)ans = 0tmp=0odd,even = -1,-1for i in range(cnt):tmp += cards[i]if cards[i]%2==1:odd = cards[i]else:even = cards[i]if tmp%2==0:return tmpfor i in range(cnt,len(cards)):if cards[i]%2==1:if even!=-1:ans = max(ans,tmp-even+cards[i])else:if odd!=-1:ans = max(ans,tmp-odd+cards[i])return ans

---

8/2 3128. 直角三角形

枚举两条直角边的交点 构成直角三角形 将这个点所在行的点与所在列的点一一匹配
假设所在行有row个点 所在列有col个点 那么以这个点为转折点的直角三角形有(row-1)*(col-1)个

def numberOfRightTriangles(grid):""":type grid: List[List[int]]:rtype: int"""n=len(grid)m=len(grid[0])col =[0]*mfor j in range(m):for i in range(n):col[j]+=grid[i][j]ans = 0for i in range(n):row = sum(grid[i])for j in range(m):if grid[i][j]==1:ans +=(row-1)*(col[j]-1)return  ans

---

8/3 3143. 正方形中的最多点数

将正方形边长从0开始往外扩展
对于任意一个点x,y 在第max(|x|,|y|)次扩展后位于正方形内
计算每个点经过几次会被正方形包含在内
第一次出现重复标签则停止

def maxPointsInsideSquare(points, s):""":type points: List[List[int]]:type s: str:rtype: int"""l = []n = len(points)for i in range(n):l.append((max(abs(points[i][0]),abs(points[i][1])),s[i]))l.sort()mem = set()pre = 0cnt = 0ans = 0for r,sign in l:if r>pre:pre = rans += cntcnt = 0if sign not in mem:cnt+=1mem.add(sign)else:cnt = 0breakreturn ans+cnt

---

8/4 572. 另一棵树的子树

same判断两个树是否一致
height判断树的深度
深搜root 如果树的深度不一致必定不一致

class TreeNode(object):def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = right
def isSubtree(root, subRoot):""":type root: TreeNode:type subRoot: TreeNode:rtype: bool"""def same(a,b):if a is None or b is None:return a is breturn a.val==b.val and same(a.left,b.left) and same(a.right,b.right)def height(node):if node is None:return 0lh = height(node.left)rh = height(node.right)return max(lh,rh)+1hs = height(subRoot)def dfs(node):if node is None:return 0,Falselh,lf = dfs(node.left)rh,rf = dfs(node.right)if lf or rf:return 0,Truenh = max(lh,rh)+1return nh,nh==hs and same(node,subRoot)return dfs(root)[1]

---