双周赛62

1. 将一维数组转变成二维数组

暴力

class Solution:
    def construct2DArray(self, original: List[int], m: int, n: int) -> List[List[int]]:
        cnt = len(original)
        if m*n != cnt: return []
        
        res=[[0]*n for _ in range(m)]
        it = iter(original)
        for i in range(m):
            for j in range(n):
                res[i][j] = next(it)
                
        return res

2. 连接后等于目标字符串的字符串对

暴力

class Solution:
    def numOfPairs(self, nums: List[str], target: str) -> int:
        n = len(nums)
        res = 0
        for i in range(n):
            for j in range(n):
                if i==j:
                    continue
                if nums[i]+nums[j] == target:
                    res += 1
                    
        return res

3. 考试的最大困扰度

滑动窗口

class Solution:
    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:
        n = len(answerKey)
        res = k
        
        # f
        q = deque()
        l = 0
        cnt = 0
        for r,c in enumerate(answerKey):
            if c=="F":
                q.append(r)
                cnt += 1
                if cnt > k:
                    l = q.popleft()+1
            res = max(res, r-l+1)
            
        # t
        q = deque()
        l = 0
        cnt = 0
        for r,c in enumerate(answerKey):
            if c=="T":
                q.append(r)
                cnt += 1
                if cnt > k:
                    l = q.popleft()+1
            res = max(res, r-l+1)
            
        return res

4. 分割数组的最多方案数

给你一个下标从 0 开始且长度为 n 的整数数组 nums 。分割 数组 nums 的方案数定义为符合以下两个条件的 pivot 数目：

• 1 <= pivot < n
• nums[0] + nums[1] + ... + nums[pivot - 1] == nums[pivot] + nums[pivot + 1] + ... + nums[n - 1]

同时给你一个整数 k 。你可以将 nums 中 一个 元素变为 k 或 不改变 数组。

请你返回在 至多 改变一个元素的前提下，最多 有多少种方法 分割 nums 使得上述两个条件都满足。

示例 1：

输入：nums = [2,-1,2], k = 3
输出：1
解释：一个最优的方案是将 nums[0] 改为 k 。数组变为 [3,-1,2] 。
有一种方法分割数组：
- pivot = 2 ，我们有分割 [3,-1 | 2]：3 + -1 == 2 。

示例 2：

输入：nums = [0,0,0], k = 1
输出：2
解释：一个最优的方案是不改动数组。
有两种方法分割数组：
- pivot = 1 ，我们有分割 [0 | 0,0]：0 == 0 + 0 。
- pivot = 2 ，我们有分割 [0,0 | 0]: 0 + 0 == 0 。

示例 3：

输入：nums = [22,4,-25,-20,-15,15,-16,7,19,-10,0,-13,-14], k = -33
输出：4
解释：一个最优的方案是将 nums[2] 改为 k 。数组变为 [22,4,-33,-20,-15,15,-16,7,19,-10,0,-13,-14] 。
有四种方法分割数组。

提示：

n == nums.length
2 <= n <= 105
-105 <= k, nums[i] <= 105

class Solution:
    def waysToPartition(self, nums: List[int], k: int) -> int:
        n = len(nums)
        pre = [0] + list(accumulate(nums))
        tot = pre[n]

        d1 = collections.defaultdict(int) # 左边
        d2 = collections.defaultdict(int) # 右边
        for i in range(1, n):
            d1[pre[i] - (tot - pre[i])] += 1  #左比右多多少
        res = d1[0]

        for i in range(n):
            d = k - nums[i]  # 修改后增加的值
            res = max(res, d1[0-d] + d2[0+d])  # 对左边，只有 比右边多 （0-d）的才有效，因为右边会加d。右边同理
            d1[pre[i + 1] - (tot - pre[i + 1])] -= 1
            d2[pre[i + 1] - (tot - pre[i + 1])] += 1
        return res