力扣第 169 场双周赛

493
Contest
LeetCode
本文最后更新于 2 分钟前，文中所描述的信息可能已发生改变。

3736. 最小操作次数使数组元素相等 III - 力扣（LeetCode） ​

题目类型 ​

#贪心

解题思路 ​

参考：这道题很简单！

示例代码 ​

python
class Solution:
    def minMoves(self, nums: List[int]) -> int:
        mx = max(nums)
        return sum(mx - x for x in nums)

3737. 统计主要元素子数组数目 I - 力扣（LeetCode） ​

题目类型 ​

#前缀和

解题思路 ​

参考：这道题很简单！

示例代码 ​

python
class Solution:
    def countMajoritySubarrays(self, nums: List[int], target: int) -> int:
        ans = 0
        n = len(nums)
        pre = [0] * (n + 1)
        for i, x in enumerate(nums):
            pre[i + 1] = pre[i] + int(x == target)
        for i in range(1, n + 1):
            for j in range(n - i + 1):
                if (pre[i + j] - pre[j]) > i // 2:
                    ans += 1
        return ans

3738. 替换至多一个元素后最长非递减子数组 - 力扣（LeetCode） ​

题目类型 ​

#前后缀 #状态机DP

解题思路 ​

统计前缀和后缀非递减子数组的长度，特判 nums[i−1]<=nums[i+1]nums[i - 1] <= nums[i + 1] 的情况即可

参考：两种方法：前后缀分解 / 状态机 DP，O(1) 空间（Python/Java/C++/Go）

示例代码 ​

python
TODO

3739. 统计主要元素子数组数目 II - 力扣（LeetCode） ​

题目类型 ​

#有序集合 #二分 #前缀和

解题思路 ​

分析题目可得结论，见下：

pre[i+1]−pre[j]>(i−j+1)//2pre[i + 1] - pre[j] > (i - j + 1) // 2

2∗pre[i+1]−(i+1)>2∗pre[j]−j2 * pre[i + 1] - (i + 1) > 2 * pre[j] - j

示例代码 ​

python
class Solution:
    def countMajoritySubarrays(self, nums: List[int], target: int) -> int:
        n = len(nums)
        ans = 0
        pre = [0] * (n + 1)
        sl = SortedList([0])
        for i, x in enumerate(nums):
            pre[i + 1] = pre[i] + int(x == target)
            t = 2 * pre[i + 1] - (i + 1)
            idx = sl.bisect_left(t)
            ans += idx
            sl.add(t)
        return ans
力扣第 170 场双周赛
力扣第 xxx 场周赛