【Leetcode题解】Biweekly Contest 101 双周赛题目解析

Posted on Sun 02 April 2023 in Leetcode

这次双周赛难度不大，侮辱性极强。第三题和第四题完全是对调的难度，尽管一个是Medium一个是Hard。真的搞不懂出题人的思路了（他想让我死）。

题目列表

2606. Find the Substring With Maximum Cost 从两个数字数组里生成最小数字

第一题的要点：如果同一个数字在两个数组里都出现的话，那么这个数字必定最小；否则的话我们就看两个数组里最小的两个数字是否能组成最小的数。

代码

class Solution:
    def minNumber(self, nums1: List[int], nums2: List[int]) -> int:
        nums1.sort()
        nums2.sort()

        nums3 = set(nums1).intersection(nums2)

        if nums3:
            return min(nums3)

        return min(nums1[0] * 10 + nums2[0], nums2[0] * 10 + nums1[0])

2606. Find the Substring With Maximum Cost 找到最大开销的子字符串

输入字符串s, chars和数组vals，其中vals[i]是chars[i]字母的分数。如果字母没有包含在chars里面，那么就按照他的ascii里的顺序来决定分数，比如a = 1，b = 2…… 最终，我们找到一个子字符串的组合使得分数最大。

这题其实是53. Maximum Subarray的变种，因为我们可以简单的根据三个入参转换为一个nums数组，这样我们的问题就是要求找到最大的子数组了。有两个需要注意的点：第一是对于负数的处理，第二是也可以取空集，这样分数就为0。这道题的解法主要是以Kadine's Algorithm来展开。这个解法有一些贪心的意味在里面。我们先来看个例子。

Example 1 
Input: [-1,-4,-5,4,1,2,-3]
Output: 7

这个例子里面我们很明显药跳过前面三个负数，从4开始取。那么我们只取正的子数组是不是就可以了呢？

Example 2
Input: [-1,1000,-5,4,1,2,-3]
Output: 1002

这个例子里面，我们又可以从1000，并且包含-5。当我们有一个绝对大的数字的时候，我们是可以选择性的囊括一些负数以期望获得更大的值的。无论如何，我们期望的是尽可能的囊括正数使得整个最大。

代码

import string

class Solution:
    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:
        v = {chars[i] : vals[i] for i in range(len(chars))}
        for l in string.ascii_lowercase:
            if l in v:
                continue
            v[l] = int(ord(l)- ord('a') + 1)

        # print(v)

        nums = []
        for c in s:
            nums.append(v[c])

        curr = nums[0]
        result = nums[0]

        for i in range(1, len(nums)):
            num = nums[i]
            curr = max(num, curr + num)
            result = max(result, curr)

        return max(result, 0)

2607. Make K-Subarray Sums Equal 使子数组元素和相等

给定一个数字arr，可以对任意数字进行加减1的操作。我们期望找到最少次数的操作使得每个连续子数组的和都相等。此外，这个数组是循环的，也就是说我们数子数组的时候，数到末尾边界了的话需要从头开始继续算。

这题应该算是本次双周赛最难的题目了。我一开始的思路就是分case处理。有这么几种case

  • 若arr的长度可以整除k，arr可以尽可能被调整为以k为单位循环的数组。
  • 否则的话，就需要把所有的数字都变成相同的，而变为相同的最小情况是变为数组的中位数。

但是这样还是会有一些情况缺失。如下面这个例子

Example
Input: arr = [7,3,10,6,7,3,10,6], k = 6
Output: 12

在这个例子里面，有8个元素，而k = 6这样子的话。可以看到，第一个和第二子数组，arr[0:6] = [7,...,3]和arr[1:7] = [3,...10]，少了一个7多了一个10，因此这里arr[0] = 7和arr[6] = 10是要对齐的。而再挪动一位，我们需要把arr[1] = 3和arr[7] = 6进行对齐，arr[2] = arr[8 % 8 = 0]进行对齐，arr[3] = arr[9 % 8 = 1]。这样的话，我们需要变成一致的元素索引为[0, 2, 4, 6]和[1, 3, 5, 7]。这两个组里的元素需要变成一致的才可以。

Example
Input: arr = [7,3,10,6], k = 3
Output: 8

再来看一个例子，在这个例子里面，我们以同样的方法去检查哪些元素需要归成一组。因为arr长度为4而我们需要每3个都相等，因此我们没什么选择，只能把所有元素都归到同一组里面，即把整个组都变成6。

到这里的话，我们的思路大概就清晰了。我们通过上面这种方式把元素分组，然后每个组里的元素需要相等才可以。当然，你可以通过左右指针去做这件事情，但是这里我分享一个更高效的解法。实际上，我们能分的组数其实就是数组长度和k的最大公约数gcd(len(arr), k)。这样我们就可以利用这个循环数组的性质去找到最小的子集，使得我们的结果符合条件。

代码

from collections import defaultdict
from math import gcd

class Solution:
    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:

        k = gcd(k, len(arr))

        m = [[] for i in range(k)]


        for i, v in enumerate(arr):
            m[i % k].append(v)

        result = 0
        for a in m:
            a.sort()

            mid = a[len(a) // 2]

            for v in a:
                result += abs(v - mid)

        print(m)

        return result

2608. Shortest Cycle in a Graph 图中的最短环

给定一个无向图，我们需要找到里面最短的环。当然还有一些其他的条件，如每个点最多只有一条边，不过要解决这个问题的话都用不太上。

这道题实际上是相当标准的bfs做法。我们从任意点i出发，用一个queue来保存，并用一个列表来存某一个节点到i的距离。如果我们发现两个点都可以到达i的话，那么我们就找到了一个最短环。

代码

from collections import deque

class Solution:
    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:
        g = [[] for _ in range(n)]

        for i, j in edges:
            g[i].append(j)
            g[j].append(i)

        def root(i):
            dis = [inf] * n

            dis[i] = 0

            q = deque()

            q.append(i)

            while q:
                i = q.popleft()

                for j in g[i]:
                    if dis[j] == inf:
                        dis[j] = 1 + dis[i]
                        q.append(j)
                    elif dis[i] <= dis[j]:
                        return dis[i] + dis[j] + 1
            return inf

        result = inf
        for i in range(n):
            result = min(result, root(i))

        if result == inf:
            return -1
        return result

小结

总体来讲，这次第三题还是需要一点巧妙的思路的，题型也是不常见到的那种。

如果你想变得更强的话，可以看看

如果你想变得更强的话，可以做做

Contest