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 = nums
        n = 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] += num
        
    def update(self, index, val):
        """
        :type index: int
        :type val: int
        :rtype: None
        """
        self.sums[index//self.size]+= val-self.nums[index]
        self.nums[index] = val

    def sumRange(self, left, right):
        """
        :type left: int
        :type right: int
        :rtype: int
        """
        s = self.size
        k1,k2 = left//s,right//s
        if 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])




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

---

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]=ed
        
    f=w
    for 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 = 0
    mincnt = float('inf')
    for i in range(n):
        cnt = 0
        for j in range(n):
            if j!=i and f[i][j]<=distanceThreshold:
                cnt+=1
        if cnt<=mincnt:
            mincnt=cnt
            ans = i
    return ans


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

---

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
    



1
2
3
4
5
6
7
8
9
10
11
12

---

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

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

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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

---

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 bisect
    ans = [-1]*len(queries)
    l = sorted([(a,b) for a,b in zip(nums1,nums2)],key=lambda x:-x[0])
    st = []
    j=0
    for 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+=1
        p = bisect.bisect_left(st,(y,))
        if p<len(st):
            ans[i] = st[p][1]
    return ans



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

---

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

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

def maximumSum(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    m={}
    def check(num):
        ans = 0
        while num:
            ans += num%10
            num //=10
        return ans
    ans = -1
    for 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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

---

11/19

1
2
3

---