LeetCode笔记：Weekly Contest 262

• LeetCode笔记：Weekly Contest 262
  • 1. 题目一
    • 1. 解题思路
    • 2. 代码实现
  • 2. 题目二
    • 1. 解题思路
    • 2. 代码实现
  • 3. 题目三
    • 1. 解题思路
    • 2. 代码实现
  • 4. 题目四

给出题目一的试题链接如下：

• 2032. Two Out of Three

这一题我的思路还是比较暴力的，就是两两求交集，然后求这几个交集的并集，即可得到最终的答案。

给出python代码实现如下：

class Solution:
    def twoOutOfThree(self, nums1: List[int], nums2: List[int], nums3: List[int]) -> List[int]:
        nums1 = set(nums1)
        nums2 = set(nums2)
        nums3 = set(nums3)
        s1 = nums1 & nums2
        s2 = nums2 & nums3
        s3 = nums1 & nums3
        return list(s1 | s2 | s3)

提交代码评测得到：耗时68ms，占用内存14.2MB。

给出题目二的试题链接如下：

• 2033. Minimum Operations to Make a Uni-Value Grid

这一题的思路其实也还好，我们首先判断是否可以成功实现变换，这个只需要判断任意两个数之间的差值是否都是给定的数值的整数倍。

然后，我们来看所需的最小变换数目。有关这一个，我们首先将数字和其对应的重复出现次数进行排序，然后以每一个数作为锚定的最终数值进行变换考察，即可得到最终的结果，这个算是一个经典的题目了，就不做多展开了。

给出python代码实现如下：

class Solution:
    def minOperations(self, grid: List[List[int]], x: int) -> int:
        cnt = defaultdict(int)
        for row in grid:
            for k in row:
                cnt[k] += 1
        y0 = min(cnt.keys())
        if any((y - y0) % x != 0 for y in cnt.keys()):
            return -1

        nums = sorted([((k-y0)//x, v) for k, v in cnt.items()])
        n, s = len(nums), sum(k*v for k, v in nums)
        vlist = [it[0] for it in nums]
        nlist = list(accumulate([it[1] for it in nums]))
        res = s
        for i in range(1, n):
            s = s - (nlist[-1] - nlist[i-1]) * (vlist[i] - vlist[i-1]) + nlist[i-1] * (vlist[i] - vlist[i-1])
            res = min(res, s)
        return res

提交代码评测得到：耗时1488ms，占用内存49.1MB。

给出题目三的试题链接如下：

• 2034. Stock Price Fluctuation

这一题其实比前一题简单，我们只需要用一个dict记录一下当前的timestamp是否有在之前被记录过就可以更新对应的price，但是，关于取最大最小值，我们需要将有效的价格维持一个有序的序列即可，在每一次更新的时候，我们都要先找出之前的错误价格进行删除，然后再补充新的价格即可。

而这个过程，我们可以采用二分法进行优化。

给出python代码实现如下：

class StockPrice:

    def __init__(self):
        self.record = {}
        self.latest_timestamp = 0
        self.prices = []

    def update(self, timestamp: int, price: int) -> None:
        # print(self.prices, self.record, timestamp, price)
        if timestamp in self.record:
            idx = bisect.bisect_left(self.prices, self.record[timestamp])
            self.prices.pop(idx)
        self.record[timestamp] = price
        bisect.insort(self.prices, price)
        self.latest_timestamp = max(self.latest_timestamp, timestamp)
        return

    def current(self) -> int:
        return self.record[self.latest_timestamp]

    def maximum(self) -> int:
        return self.prices[-1]

    def minimum(self) -> int:
        return self.prices[0]

提交代码评测得到：耗时1240ms，占用内存53.7MB。

给出题目四的试题链接如下：

• 2035. Partition Array Into Two Arrays to Minimize Sum Difference

时间有点久了，这题算了，放弃了……