周赛笔记217

发布日期: 2020-11-29

更新日期: 2021-12-01

文章字数: 607

阅读时长: 2 分

第一题：https://leetcode-cn.com/problems/richest-customer-wealth/
第二题：https://leetcode-cn.com/problems/find-the-most-competitive-subsequence/
第三题：https://leetcode-cn.com/problems/minimum-moves-to-make-array-complementary/
第四题：https://leetcode-cn.com/problems/minimize-deviation-in-array/

二、找出最具竞争力的子序列

输入：nums = [3,5,2,6], k = 2
输出：[2,6]
解释：在所有可能的子序列集合 {[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]} 中，[2,6] 最具竞争力。

class Solution:
    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:
        stack=[nums[0]]
        count=len(nums)-k #最多可删除
        for i in nums[1:]:
            while stack and i<stack[-1] and count:
                stack.pop()
                count-=1
            stack.append(i)
        return stack[:k]

# 单调栈
# 用那个count和栈来简化问题

三、使数组互补的最少操作次数

给你一个长度为偶数 n 的整数数组 nums 和一个整数 limit 。每一次操作，你可以将 nums 中的任何整数替换为 1 到 limit 之间的另一个整数。

class Solution(object):

    def minMoves(self, A, limit):
        n = len(A)
        count = [0] * (limit * 2 + 2)
        mi = [0] * (limit * 2 + 2)
        ma = [0] * (limit * 2 + 2)
        for i in xrange(n / 2):
            a, b = A[i], A[~i]
            count[a + b] += 1
            mi[min(a, b)] += 1
            ma[max(a, b) + limit + 1] += 1
        for i in xrange(3, limit * 2 + 1):
            ma[i] += ma[i - 1]
        for i in xrange(limit * 2 - 1, -1, -1):
            mi[i] += mi[i + 1]
        return min(n / 2 - count[i] + mi[i] + ma[i] for i in xrange(2, limit * 2 + 1))

#copy

四、数组的最小偏移量

给你一个由 n 个正整数组成的数组 nums 。

你可以对数组的任意元素执行任意次数的两类操作：

如果元素是偶数，除以 2
例如，如果数组是 [1,2,3,4] ，那么你可以对最后一个元素执行此操作，使其变成 [1,2,3,2]
如果元素是奇数，乘上 2
例如，如果数组是 [1,2,3,4] ，那么你可以对第一个元素执行此操作，使其变成 [2,2,3,4]

数组的 偏移量 是数组中任意两个元素之间的 最大差值 。

返回数组在执行某些操作之后可以拥有的 最小偏移量 。

class Solution(object):
    def minimumDeviation(self, A):
        n = len(A)
        heap = []
        for a in A:
            a2 = a
            while a2 % 2 == 0:
                a2 >>= 1
            heapq.heappush(heap, [a2, a])
        res = float('inf')
        ma = max(a for a, a0 in heap)
        while True:
            a, a0 = heapq.heappop(heap)
            res = min(res, ma - a)
            if a % 2 == 1 or a < a0:
                a *= 2
                ma = max(ma, a)
                heapq.heappush(heap, [a, a0])
            else:
                break
        return res

#copy