网站建设 开发人一丶一一人一一,绍兴住房和城乡建设厅网站,国际抖抈2022,页面模版 公众号记录了初步解题思路 以及本地实现代码#xff1b;并不一定为最优 也希望大家能一起探讨 一起进步 目录 11/13 307. 区域和检索 - 数组可修改11/14 1334. 阈值距离内邻居最少的城市11/15 2656. K 个元素的最大和11/16 2760. 最长奇偶子数组11/17 2736. 最大和查询11/18 2342. 数…记录了初步解题思路 以及本地实现代码并不一定为最优 也希望大家能一起探讨 一起进步 目录 11/13 307. 区域和检索 - 数组可修改11/14 1334. 阈值距离内邻居最少的城市11/15 2656. K 个元素的最大和11/16 2760. 最长奇偶子数组11/17 2736. 最大和查询11/18 2342. 数位和相等数对的最大和11/19 689. 三个无重叠子数组的最大和 11/13 307. 区域和检索 - 数组可修改 分段处理 对于n个数分为若干块 每块大小size 一共n//size块 初始化统计每块总和 更新index 在index//size块中 取和left在k1中第i个 right在k2中第j个 如果k1k2 那么就是k1中[i,j]和 否则就是k1的[i,size-1] k2的[j,size-1] 加上k11~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]*((nself.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: Noneself.sums[index//self.size] val-self.nums[index]self.nums[index] valdef sumRange(self, left, right)::type left: int:type right: int:rtype: ints self.sizek1,k2 left//s,right//sif k1k2:return sum(self.nums[left:right1])else:return sum(self.nums[left:(k11)*s])sum(self.sums[k11:k2])sum(self.nums[k2*s:right1]) 11/14 1334. 阈值距离内邻居最少的城市 依次判断 def findTheCity(n, edges, distanceThreshold)::type n: int:type edges: List[List[int]]:type distanceThreshold: int:rtype: intw [[float(inf)]*n for _ in range(n)]for x,y,ed in edges:w[x][y]w[y][x]edfwfor 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:cnt1if cntmincnt:mincntcntans ireturn ans 11/15 2656. K 个元素的最大和 只需要选择最大的数进行操作 def maximizeSum(nums, k)::type nums: List[int]:type k: int:rtype: intv max(nums)return v*k(1k-1)*(k-1)//2 11/16 2760. 最长奇偶子数组 从后往前判断 cur记录当前最长子数组 如果遇到大于threshold则0开始 如果遇到奇偶相同则从1开始 def longestAlternatingSubarray(nums, threshold)::type nums: List[int]:type threshold: int:rtype: intanscur0for i in range(len(nums)-1,-1,-1):if nums[i]threshold:cur0elif ilen(nums)-1 or (nums[i]nums[i1])%21:cur1else:cur1if nums[i]%20:ansmax(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)],keylambda x:-x[0])st []j0for i,(x,y) in sorted(enumerate(queries),keylambda x:-x[1][0]):while jlen(l) and l[j][0]x:xx,yyl[j]while st and st[-1][1]xxyy:st.pop()if not st or st[-1][0]yy:st.append((yy,xxyy))j1p bisect.bisect_left(st,(y,))if plen(st):ans[i] st[p][1]return ans 11/18 2342. 数位和相等数对的最大和 遍历求出各个数的数位和 记录所有数位和最大的数 def maximumSum(nums)::type nums: List[int]:rtype: intm{}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):sum1nums[i-k*2]sum2nums[i-k]sum3nums[i]if ik*3-1:if sum1maxs1:maxs1sum1maxs1loc i-k*31if maxs1sum2maxs2:maxs2maxs1sum2maxs2loc (maxs1loc,i-k*21)if maxs2sum3maxs3:maxs3 maxs2sum3ans [maxs2loc[0],maxs2loc[1],i-k1]sum1-nums[i-k*31]sum2-nums[i-k*21]sum3-nums[i-k1]return ans
