Weekly Contest 392 周赛题目解析

Posted on Sun 31 March 2024 in Leetcode

Weekly Contest 392

第 392 场周赛

题目列表

3105. Longest Strictly Increasing or Strictly Decreasing Subarray 最长的严格递增或递减子数组

按照题意模拟，分别从左到右从右到左使用双指针即可。

class Solution:
    def longestMonotonicSubarray(self, nums: List[int]) -> int:
        left = 0

        result = 1
        for right in range(1, len(nums)):
            if nums[right] <= nums[right - 1]:
                left = right
            result = max(result, right - left + 1)

        left = 0
        for right in range(1, len(nums)):
            if nums[right] >= nums[right - 1]:
                left = right
            result = max(result, right - left + 1)

        return result

3106. Lexicographically Smallest String After Operations With Constraint 满足距离约束且字典序最小的字符串

给定小写字符串s，你可以对字符串中的任意一位进行加减1操作，使其变换成另一个字母。与此同时，变换的时候遵循循环排列，如z + 1 => a或a - 1 => z。在限定操作k次的情况下，求可以变换得到的字典序最小的字符串。

看到字典序最小，我们可以马上考虑使用贪心的方法：肯定是优先把左边的字母变成更小的字母收益更大。给定字母c和剩余操作次数k，我们有：

  1. 当满足(c + n) % 26 == 'a'，且n <= k时，我们可以把字母c往高位变换直至变成'a'。
  2. 当c - n == 'a'，且n <= k时，我们可以把字母c往低位变换直至变成'a'。
  3. 字母c也可以同时满足以上两个条件，则我们取尽量小的n。
  4. 否则的话，我们只能最多向低位变换k次。

按照这样的逻辑，我们从左到右每次只处理一个字母，直至无法处理为止。

def smallest_achivable(c, k):
    if c == 'a' or k == 0:
        return c, 0

    d = ord(c) - ord('a')

    if d + k >= 26 and d - k < 0:
        return 'a', min(26 - d, d)
    elif d + k >= 26:
        return 'a', 26 - d
    elif d - k < 0:
        return 'a', d

    return chr(d - k + ord('a')), k


class Solution:
    def getSmallestString(self, s: str, k: int) -> str:

        ns = []

        for c in s:
            nc, deduct = smallest_achivable(c, k)
            k -= deduct
            ns.append(nc)

        return ''.join(ns)

3107. Minimum Operations to Make Median of Array Equal to K 使数组中位数等于 K 的最少操作数

给定正整数数组nums和正整数k，可以将数组中任意数字加一或减一。求将数组的中位数变成k的最小操作次数。

这题的中位数定义为 nums[n // 2]，无需考虑偶数个数字时的场景。

将数组排序后，分成左右两边。左边的数字必小于等于k，右边的数字必大于等于k，因此操作次数为违反此规则的数字与k的差值的绝对值的和。

class Solution:
    def minOperationsToMakeMedianK(self, nums: List[int], k: int) -> int:
        nums.sort()
        n = len(nums)
        midIndex = n // 2
        operations = 0

        for i in range(midIndex, -1, -1):
            if nums[i] > k:
                operations += (nums[i] - k)
            else:
                break
        for i in range(midIndex, n):
            if nums[i] < k:
                operations += (k - nums[i])
            else:
                break

        return operations

3072. Distribute Elements Into Two Arrays II 将元素分配到两个数组中 II

给定有权图edges = [[u_i, v_i, w_i]...]。若某条u -> v的路径经过了一系列边，则此路径的代价为经过的边的所有权重的按位与（Bitwise AND），且你可以经过同一条边无数次。给定一系列查询query = [[p_i, q_i]...]，返回每个查询的最短代价。

我们知道按位与操作的真值表只有当两位同时为1的时候才可以得到1，题目也告诉我们可以经过同一条边无数次，因此我们不需要考虑具体的路径，只需要暴力的经过尽可能多的边，就可以得到较小的代价。

我们可以采用并查集Union Find来支持此类查询。我们知道，并查集可以快速的找到图中的两个点是否连接。与此同时，在合并（Union）操作的时候，我们可以顺便进行按位与来计算两个合并节点的代价。

class UF:
    def __init__(self, size: int):
        self.parent = list(range(size))
        self.min_cost = {i: (1 << 31) - 1 for i in range(size)}

    def find(self, x: int) -> int:
        if x != self.parent[x]:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x: int, y: int, weight: int):
        rootX = self.find(x)
        rootY = self.find(y)

        if rootX != rootY:
            self.parent[rootX] = rootY
        self.min_cost[rootY] = self.min_cost[rootY] & self.min_cost[rootX] & weight
        self.min_cost[rootX] = self.min_cost[rootY]
        self.min_cost[x] = self.min_cost[rootY]


class Solution:
    def minimumCost(self, n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:
        uf = UF(n)

        for u, v, w in edges:
            uf.union(u, v, w)

        answer = []
        for s, t in query:
            if s == t:
                answer.append(0)
            elif uf.find(s) == uf.find(t):
                answer.append(uf.min_cost[uf.find(s)])
            else:
                answer.append(-1)

        return answer

Contest