鸭梨公共文档

主题

第 352 场周赛 ​

2760. 最长奇偶子数组 ​

@easy 找最长的奇偶子数组，子数组的每一项要小于等于阈值。

python
class Solution:
    def longestAlternatingSubarray(self, nums: List[int], threshold: int) -> int:
        res = 0
        l = -1
        last_mod = 0
        for i in range(len(nums)):
            if l == -1:
                if nums[i] <= threshold and nums[i] % 2 == 0:
                    l = i
            else:
                if nums[i] > threshold or nums[i] % 2 == last_mod:
                    res = max(res, i - l)
                    if nums[i] <= threshold and nums[i] % 2 == 0:
                        l = i
                    else:
                        l = -1
            last_mod = nums[i] % 2
        if l != -1:
            res = max(res, len(nums) - l)
        return res

2761. 和等于目标值的质数对 ​

@medium 打表出 10610^6 以内的素数即可。

python
def is_prime(n: int) -> bool:
    if n < 2:
        return False
    for i in range(2, int(sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

PRIMES = {i for i in range(2, 10**6) if is_prime(i)}

class Solution:
    def findPrimePairs(self, n: int) -> List[List[int]]:
        res = []
        for i in range(1, n // 2 + 1):
            if i in PRIMES and n - i in PRIMES:
                res.append([i, n - i])
        return res

2762. 不间断子数组 ​

@medium 计数，回溯。

python
class Solution:
    def continuousSubarrays(self, nums: List[int]) -> int:
        curr_min = nums[0]
        curr_max = nums[0]
        curr = 1
        res = 1
        for i in range(1, len(nums)):
            if nums[i] > curr_max:
                curr_max = nums[i]
                if curr_max - curr_min > 2:
                    curr = 1
                    curr_min = nums[i]
                    while i - curr >= 0 and nums[i] - nums[i - curr] <= 2:
                        curr_min = min(curr_min, nums[i - curr])
                        curr += 1
                    res += curr
                    continue
            elif nums[i] < curr_min:
                curr_min = nums[i]
                if curr_max - curr_min > 2:
                    curr = 1
                    curr_max = nums[i]
                    while i - curr >= 0 and nums[i - curr] - nums[i] <= 2:
                        curr_max = max(curr_max, nums[i - curr])
                        curr += 1
                    res += curr
                    continue
            curr += 1
            res += curr
        return res

2763. 所有子数组中不平衡数字之和 ​

@hard 根据题意，首先使用暴力解用于验证答案。

python
class Solution:
    def sumImbalanceNumbers(self, nums: List[int]) -> int:
        res = 0
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                sorted_sub = sorted(nums[k] for k in range(i, j + 1))
                res += sum(
                    1
                    for k in range(j - i)
                    if sorted_sub[k + 1] - sorted_sub[k] > 1
                )
        return res