LeetCode 每日一题 2023/11/13-2023/11/19

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

---

11/13 307. 区域和检索 - 数组可修改

分段处理 对于n个数分为若干块 每块大小size 一共n//size块
初始化统计每块总和
更新index 在index//size块中
取和left在k1中第i个 right在k2中第j个
如果k1=k2 那么就是k1中[i,j]和
否则就是k1的[i,size-1] k2的[j,size-1] 加上k1+1~k2-1的所有块总和
每块大小去更号n

class NumArray(object):def __init__(self, nums):""":type nums: List[int]"""self.nums = numsn = len(nums)self.size = int(n**0.5)self.sums = [0]*((n+self.size-1)//self.size)for index,num in enumerate(nums):self.sums[index//self.size] += numdef update(self, index, val):""":type index: int:type val: int:rtype: None"""self.sums[index//self.size]+= val-self.nums[index]self.nums[index] = valdef sumRange(self, left, right):""":type left: int:type right: int:rtype: int"""s = self.sizek1,k2 = left//s,right//sif k1==k2:return sum(self.nums[left:right+1])else:return sum(self.nums[left:(k1+1)*s])+sum(self.sums[k1+1:k2])+sum(self.nums[k2*s:right+1])

---

11/14 1334. 阈值距离内邻居最少的城市

依次判断

def findTheCity(n, edges, distanceThreshold):""":type n: int:type edges: List[List[int]]:type distanceThreshold: int:rtype: int"""w = [[float('inf')]*n for _ in range(n)]for x,y,ed in edges:w[x][y]=w[y][x]=edf=wfor k in range(n):for i in range(n):for j in range(n):f[i][j] = min(f[i][j],f[i][k]+f[k][j])ans = 0mincnt = float('inf')for i in range(n):cnt = 0for j in range(n):if j!=i and f[i][j]<=distanceThreshold:cnt+=1if cnt<=mincnt:mincnt=cntans = ireturn ans

---

11/15 2656. K 个元素的最大和

只需要选择最大的数进行操作

def maximizeSum(nums, k):""":type nums: List[int]:type k: int:rtype: int"""v = max(nums)return v*k+(1+k-1)*(k-1)//2

---

11/16 2760. 最长奇偶子数组

从后往前判断 cur记录当前最长子数组
如果遇到大于threshold则0开始
如果遇到奇偶相同则从1开始

def longestAlternatingSubarray(nums, threshold):""":type nums: List[int]:type threshold: int:rtype: int"""ans=cur=0for i in range(len(nums)-1,-1,-1):if nums[i]>threshold:cur=0elif i==len(nums)-1 or (nums[i]+nums[i+1])%2==1:cur+=1else:cur=1if nums[i]%2==0:ans=max(ans,cur)return ans

---

11/17 2736. 最大和查询

将两个数组合并为一个
先按nums1从大到小 再按nums2从大到小
逐一处理查询

def maximumSumQueries(nums1, nums2, queries):""":type nums1: List[int]:type nums2: List[int]:type queries: List[List[int]]:rtype: List[int]"""import bisectans = [-1]*len(queries)l = sorted([(a,b) for a,b in zip(nums1,nums2)],key=lambda x:-x[0])st = []j=0for i,(x,y) in sorted(enumerate(queries),key=lambda x:-x[1][0]):while j<len(l) and l[j][0]>=x:xx,yy=l[j]while st and st[-1][1]<=xx+yy:st.pop()if not st or st[-1][0]<yy:st.append((yy,xx+yy))j+=1p = bisect.bisect_left(st,(y,))if p<len(st):ans[i] = st[p][1]return ans

---

11/18 2342. 数位和相等数对的最大和

遍历求出各个数的数位和 记录所有数位和最大的数

def maximumSum(nums):""":type nums: List[int]:rtype: int"""m={}def check(num):ans = 0while num:ans += num%10num //=10return ansans = -1for num in nums:v = check(num)if v in m:ans = max(ans,m[v]+num)m[v] = max(m.get(v,0),num)return ans

---

11/19 689. 三个无重叠子数组的最大和

从左到右三个滑动窗口
sum1,sum2,sum3分别记录当前三个滑动窗口各自的和
maxs1为第一个滑动窗口最大值
maxs2为前两个滑动窗口最大值
maxs3为三个滑动窗口最大值
maxs1loc为第一个滑动窗口最大值的起始位置
maxs2loc为前两个滑动窗口最大值的起始位置
maxs3loc及我们需要的答案ans

def maxSumOfThreeSubarrays(nums, k):""":type nums: List[int]:type k: int:rtype: List[int]"""ans = []sum1,maxs1,maxs1loc = 0,0,0sum2,maxs2,maxs2loc = 0,0,()sum3,maxs3 = 0,0n = len(nums)for i in range(k*2,n):sum1+=nums[i-k*2]sum2+=nums[i-k]sum3+=nums[i]if i>=k*3-1:if sum1>maxs1:maxs1=sum1maxs1loc = i-k*3+1if maxs1+sum2>maxs2:maxs2=maxs1+sum2maxs2loc = (maxs1loc,i-k*2+1)if maxs2+sum3>maxs3:maxs3 = maxs2+sum3ans = [maxs2loc[0],maxs2loc[1],i-k+1]sum1-=nums[i-k*3+1]sum2-=nums[i-k*2+1]sum3-=nums[i-k+1]return ans

---