[leetcode第349场周赛]心得

已经连续4次周赛三题了，再这么下去肯定不行，感觉需要进行自救了。

6470. 既不是最小值也不是最大值

提示

简单

1

相关企业

给你一个整数数组 nums ，数组由 不同正整数 组成，请你找出并返回数组中 任一 既不是 最小值 也不是 最大值 的数字，如果不存在这样的数字，返回 -1 。

返回所选整数。

示例 1：

输入：nums = [3,2,1,4]
输出：2
解释：在这个示例中，最小值是 1 ，最大值是 4 。因此，2 或 3 都是有效答案。

示例 2：

输入：nums = [1,2]
输出：-1
解释：由于不存在既不是最大值也不是最小值的数字，我们无法选出满足题目给定条件的数字。因此，不存在答案，返回 -1 。

示例 3：

输入：nums = [2,1,3]
输出：2
解释：2 既不是最小值，也不是最大值，这个示例只有这一个有效答案。

提示：

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100
• nums 中的所有数字互不相同

Solution

class Solution:
    def findNonMinOrMax(self, nums: List[int]) -> int:
        if len(nums) <= 2:
            return -1
        mn, mx = min(nums), max(nums)
        for num in nums:
            if num != mn and num != mx:
                return num
        return -1

但是其实只要考虑前三个元素就可以了。首先就是一定要审题，注意是不同正整数，所以完全可以用前三个数进行比较，返回中间那个数即可。

6465. 执行子串操作后的字典序最小字符串

提示

中等

3

相关企业

给你一个仅由小写英文字母组成的字符串 s 。在一步操作中，你可以完成以下行为：

• 选则 s 的任一非空子字符串，可能是整个字符串，接着将字符串中的每一个字符替换为英文字母表中的前一个字符。例如，'b' 用 'a' 替换，'a' 用 'z' 替换。

返回执行上述操作 恰好一次 后可以获得的 字典序最小 的字符串。

子字符串 是字符串中的一个连续字符序列。

现有长度相同的两个字符串 x 和 字符串 y ，在满足 x[i] != y[i] 的第一个位置 i 上，如果  x[i] 在字母表中先于 y[i] 出现，则认为字符串 x 比字符串 y 字典序更小 。

示例 1：

输入：s = "cbabc"
输出："baabc"
解释：我们选择从下标 0 开始、到下标 1 结束的子字符串执行操作。 
可以证明最终得到的字符串是字典序最小的。

示例 2：

输入：s = "acbbc"
输出："abaab"
解释：我们选择从下标 1 开始、到下标 4 结束的子字符串执行操作。
可以证明最终得到的字符串是字典序最小的。

示例 3：

输入：s = "leetcode"
输出："kddsbncd"
解释：我们选择整个字符串执行操作。
可以证明最终得到的字符串是字典序最小的。

提示：

• 1 <= s.length <= 3 * 105
• s 仅由小写英文字母组成

Solution

思路正确，找到第一个无a的区间就行了。如果没有这样的区间，即字符串是aaaaaaaaa这种，那将最后一个a改成z即可。

写复杂了，没有必要用双指针，直接一次遍历即可。

class Solution:
    def smallestString(self, s: str) -> str:
        ls = list(s)
        p1, p2 = 0, 0
        n = len(s)
        while p1 < n and s[p1] == 'a':
            p1 += 1
        p2 = p1
        while p2 < n and s[p2] != 'a':
            p2 += 1
        if p1 >= n:
            ls[-1] = 'z'
        else:
            for i in range(p1, p2):
                ls[i] = chr(ord(ls[i]) - 1)
        return "".join(ls)

6449. 收集巧克力

提示

中等

7

相关企业

给你一个长度为 n 、下标从 0 开始的整数数组 nums ，表示收集不同巧克力的成本。每个巧克力都对应一个不同的类型，最初，位于下标 i 的巧克力就对应第 i 个类型。

在一步操作中，你可以用成本 x 执行下述行为：

• 同时对于所有下标 0 <= i < n - 1 进行以下操作， 将下标 i 处的巧克力的类型更改为下标 (i + 1) 处的巧克力对应的类型。如果 i == n - 1 ，则该巧克力的类型将会变更为下标 0 处巧克力对应的类型。

假设你可以执行任意次操作，请返回收集所有类型巧克力所需的最小成本。

示例 1：

输入：nums = [20,1,15], x = 5
输出：13
解释：最开始，巧克力的类型分别是 [0,1,2] 。我们可以用成本 1 购买第 1 个类型的巧克力。
接着，我们用成本 5 执行一次操作，巧克力的类型变更为 [2,0,1] 。我们可以用成本 1 购买第 0 个类型的巧克力。
然后，我们用成本 5 执行一次操作，巧克力的类型变更为 [1,2,0] 。我们可以用成本 1 购买第 2 个类型的巧克力。
因此，收集所有类型的巧克力需要的总成本是 (1 + 5 + 1 + 5 + 1) = 13 。可以证明这是一种最优方案。

示例 2：

输入：nums = [1,2,3], x = 4
输出：6
解释：我们将会按最初的成本收集全部三个类型的巧克力，而不需执行任何操作。因此，收集所有类型的巧克力需要的总成本是 1 + 2 + 3 = 6 。

提示：

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 109
• 1 <= x <= 109

Solution

这题存疑，我很怀疑会不会被rej，因为原理感觉还是有点问题。不过目前来看还是能过的。

我是用n3做法做的，但是实际上可以进行优化。反正就用一个数组存每次移位后的新的最小值，然后取min即可，n2复杂度即可通过。

class Solution:
    def minCost(self, nums: List[int], x: int) -> int:
        n = len(nums)
        cost = [i for i in range(n)]
        a = sorted(list(zip(nums, cost)), key=lambda x:x[0])
        cost = [x[1] for x in a]
        mn = inf
        baseline = nums[cost[0]] * n + (n - 1) * x
        for i in range(n):
            tot = 0
            cal = [False] * n
            cur = 0
            for idx in cost:
                for k in range(i + 1):
                    if not cal[(idx + k) % n]:
                        tot += nums[idx]
                        cal[(idx + k) % n] = True
                        cur += 1
                if tot > baseline:
                    break
                if cur == n:
                    break
            tot += i * x
            if tot > baseline:
                continue
            if tot > mn:
                break
            else:
                mn = tot
        return mn

上面是原理有问题的代码，下面是别人的代码：

class Solution:
    def minCost(self, nums: List[int], x: int) -> int:
        n = len(nums)
        s = list(range(0, n * x, x))  # s[i] 对应操作 i 次的总成本
        for i, mn in enumerate(nums):  # 子数组左端点
            for j in range(i, n + i):  # 子数组右端点（把数组视作环形的）
                mn = min(mn, nums[j % n])  # 注：手动 if 比大小会快很多
                s[j - i] += mn  # 累加操作 j-i 次的成本
        return min(s)

作者：灵茶山艾府
链接：https://leetcode.cn/problems/collecting-chocolates/solutions/2304896/qiao-miao-mei-ju-pythonjavacgo-by-endles-5ws2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

6473. 最大和查询

提示

困难

5

相关企业

给你两个长度为 n 、下标从 0 开始的整数数组 nums1 和 nums2 ，另给你一个下标从 1 开始的二维数组 queries ，其中 queries[i] = [xi, yi] 。

对于第 i 个查询，在所有满足 nums1[j] >= xi 且 nums2[j] >= yi 的下标 j (0 <= j < n) 中，找出 nums1[j] + nums2[j] 的 最大值 ，如果不存在满足条件的 j 则返回 -1 。

返回数组 answer ，其中 answer[i] 是第 i 个查询的答案。

示例 1：

xi = 4
yi = 1
j = 0
nums1[j] >= 4
nums2[j] >= 1
nums1[j] + nums2[j]
xi = 1
yi = 3
j = 2
nums1[j] >= 1
nums2[j] >= 3
nums1[j] + nums2[j]
xi = 2
yi = 5
j = 3
nums1[j] >= 2
nums2[j] >= 5
nums1[j] + nums2[j]
[6,10,7]

示例 2：

j = 2

示例 3：

xi
yi
xi
yi

提示：

• nums1.length == nums2.length 
• n == nums1.length 
• 1 <= n <= 105
• 1 <= nums1[i], nums2[i] <= 109 
• 1 <= queries.length <= 105
• queries[i].length == 2
• xi == queries[i][1]
• yi == queries[i][2]
• 1 <= xi, yi <= 109

Solution

线段树还是太高级了，还是用传统的排序+单调栈+二分吧。

具体来说就是先按nums1降序排序，然后维护一个nums2中的单调栈，查询按照nums1的大小从大到小进行，对栈中元素进行二分获得第一个大于nums2的最大的即可。

class Solution:
    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:
        res = [-1] * len(queries)
        a = sorted([(n1, n2) for n1, n2 in zip(nums1, nums2)])
        st = []
        i = len(a) - 1
        for qid, (x, y) in sorted(enumerate(queries), key=lambda x: -x[1][0]):
            while i >= 0 and a[i][0] >= x:
                ax, ay = a[i]
                while st and st[-1][1] <= ax + ay:
                    st.pop()
                if not st or st[-1][0] < ay:
                    st.append((ay, ax + ay))
                i -= 1
            j = bisect_left(st, (y, ))
            if j < len(st):
                res[qid] = st[j][1]
        return res

学习写法：

argsort的另外写法：sorted(enumerate(arr), key=lambda x:x[1])

初始化单个元素的元组：(y,)，这个逗号与普通的优先级括号用法区别。