LeetCode 每日一题 2024/1/22-2024/1/28

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

1/22 670. 最大交换

分解 排序
找到最先不同的位置

def maximumSwap(num):""":type num: int:rtype: int"""l = []ori = numwhile num>0:l.append(num%10)num//=10n = len(l)tmp = [v for v in l]tmp.sort()loc = -1for i in range(n-1,-1,-1):if tmp[i]!=l[i]:loc = ibreakif loc==-1:return orifor i in range(n):if tmp[loc]==l[i]:l[loc],l[i] = l[i],l[loc]breakans = 0for v in l[::-1]:ans = ans*10+vreturn ans

1/23 2765. 最长交替子数组

找到最初满足条件两个数
继续判断重复的有多少

def alternatingSubarray(nums):""":type nums: List[int]:rtype: int"""l = 0n = len(nums)ans =-1while l<n-1:if nums[l+1]!=nums[l]+1:l+=1continues = ll+=2while l<n and nums[l]==nums[l-2]:l+=1ans = max(ans,l-s)l-=1return ans

1/24 2865. 美丽塔 I

遍历每个坐标为峰值的情况
非递减单调栈
先从左往右依次入栈
pre[i]记录i位置为峰顶
左侧能够达到的最大值
同理从右往左相同处理suf[i]记录右侧能够达到最大值
相加减去重复的当前位置即为i位置为峰顶的结果

def maximumSumOfHeights(maxHeights):""":type maxHeights: List[int]:rtype: int"""n= len(maxHeights)ans = 0pre,suf=[0]*n,[0]*nst1,st2=[],[]for i in range(n):while st1 and maxHeights[i]<maxHeights[st1[-1]]:st1.pop()if st1:pre[i]=pre[st1[-1]]+(i-st1[-1])*maxHeights[i]else:pre[i]=(i+1)*maxHeights[i]st1.append(i)for i in range(n-1,-1,-1):while st2 and maxHeights[i]<maxHeights[st2[-1]]:st2.pop()if st2:suf[i]=suf[st2[-1]]+(st2[-1]-i)*maxHeights[i]else:suf[i]=(n-i)*maxHeights[i]st2.append(i)ans = max(ans,pre[i]+suf[i]-maxHeights[i])return ans

1/25 2859. 计算 K 置位下标对应元素的和

func判断位置i是否有k个置位
通过num与num-1相与去除最低位的一个置位
mem存储已经判断过的数值 1位满足 0位不满足

def sumIndicesWithKSetBits(nums, k):""":type nums: List[int]:type k: int:rtype: int"""def func(num):tag = 0while tag<k and num>0:num = num&(num-1)tag+=1if tag==k and num==0:return Truereturn Falseans = 0for i,num in enumerate(nums):if func(i):ans+=numreturn ans

1/26 2846. 边权重均等查询

cnt[i][j]记录节点i到节点0的路径上权重为j的边数
对于两个节点a,b
lca为a,b最近公共祖先
那么在a,b路径上，权重为j的边数为cnt[a][j]+cnt[b][j]-2*cnt[lca][j]
权重最大为26 遍历每一种情况

def minOperationsQueries(n, edges, queries):""":type n: int:type edges: List[List[int]]:type queries: List[List[int]]:rtype: List[int]"""m,w=len(queries),26nei = [{} for i in range(n)]for ed in edges:nei[ed[0]][ed[1]]=ed[2]nei[ed[1]][ed[0]]=ed[2]q = [[] for i in range(n)]for i in range(m):q[queries[i][0]].append([queries[i][1],i])q[queries[i][1]].append([queries[i][0],i])cnt=[[0 for _ in range(w+1)] for _ in range(n)]visited = [0 for _ in range(n)]uf = [0 for _ in range(n)]lca = [0 for _ in range(m)]def find(uf,i):if uf[i]==i:return iuf[i] = find(uf,uf[i])return uf[i]def tarjan(node,parent):if parent!=-1:cnt[node] = cnt[parent][:]cnt[node][nei[node][parent]]+=1uf[node] = nodefor c in nei[node].keys():if c==parent:continuetarjan(c,node)uf[c]=nodefor [nd,ind] in q[node]:if node!=nd and not visited[nd]:continuelca[ind] = find(uf,nd)visited[node]=1tarjan(0,-1)ans = [0 for i in range(m)]for i in range(m):totalcnt,maxcnt = 0,0for j in range(1,w+1):t = cnt[queries[i][0]][j]+cnt[queries[i][1]][j]-2*cnt[lca[i]][j]maxcnt = max(maxcnt,t)totalcnt +=tans[i] = totalcnt-maxcntreturn ans

1/27 2861. 最大合金数

遍历每一台机子的情况
二分找到能够产生最大合金数

def maxNumberOfAlloys(n, k, budget, composition, stock, cost):""":type n: int:type k: int:type budget: int:type composition: List[List[int]]:type stock: List[int]:type cost: List[int]:rtype: int"""ans = 0for c in composition:l,r = 0,budget+stock[0]while l<r:mid = (l+r+1)>>1s = 0for x,y,z in zip(c,stock,cost):s += max(0,mid*x-y)*zif s<=budget:l = midelse:r = mid-1ans = max(ans,l)return ans

1/28 365. 水壶问题

裴蜀定理
https://baike.baidu.com/item/%E8%A3%B4%E8%9C%80%E5%AE%9A%E7%90%86/5186593?fromtitle=%E8%B4%9D%E7%A5%96%E5%AE%9A%E7%90%86&fromid=5185441
每次操作
只会让桶的水总量增加x,y 或者减少x,y
找到x,y最大公约数并判断z是否是它的倍数

def canMeasureWater(jug1Capacity, jug2Capacity, targetCapacity):""":type jug1Capacity: int:type jug2Capacity: int:type targetCapacity: int:rtype: bool"""import mathif jug1Capacity+jug2Capacity<targetCapacity:return Falseif jug1Capacity==0 or jug2Capacity==0:return targetCapacity==0 or jug1Capacity+jug2Capacity==targetCapacityreturn targetCapacity%math.gcd(jug1Capacity,jug2Capacity)==0