第388场周赛（模拟参赛）

100233. 重新分装苹果

给你一个长度为 n 的数组 apple 和另一个长度为 m 的数组 capacity 。

一共有 n 个包裹，其中第 i 个包裹中装着 apple[i] 个苹果。同时，还有 m 个箱子，第 i 个箱子的容量为 capacity[i] 个苹果。

请你选择一些箱子来将这 n 个包裹中的苹果重新分装到箱子中，返回你需要选择的箱子的 最小 数量。

注意，同一个包裹中的苹果可以分装到不同的箱子中

1
2
3
4
5
6
7
8
class Solution:
    def minimumBoxes(self, apple: List[int], capacity: List[int]) -> int:
        capacity.sort(reverse=True)
        s = sum(apple)
        for i,item in enumerate(capacity):
            s -= item
            if s <= 0:
                return i+1

100247. 幸福值最大化的选择方案

给你一个长度为 n 的数组 happiness ，以及一个 正整数 k 。

n 个孩子站成一队，其中第 i 个孩子的 幸福值 是 happiness[i] 。你计划组织 k 轮筛选从这 n 个孩子中选出 k 个孩子。

在每一轮选择一个孩子时，所有 尚未 被选中的孩子的 幸福值 将减少 1 。注意，幸福值 不能 变成负数，且只有在它是正数的情况下才会减少。

选择 k 个孩子，并使你选中的孩子幸福值之和最大，返回你能够得到的 最大值 。

1
2
3
4
5
6
7
8
9
10
class Solution:
    def maximumHappinessSum(self, happiness: List[int], k: int) -> int:
        happiness.sort()
        happiness = happiness[-1:-k-1:-1]
        sum = 0
        for i, item in enumerate(happiness):
            if item < i+1:
                return sum
            sum += item - i
        return sum

第 126 场双周赛

100262. 求出加密整数的和

给你一个整数数组 nums ，数组中的元素都是 正 整数。定义一个加密函数 encrypt ，encrypt(x) 将一个整数 x 中 每一个 数位都用 x 中的 最大 数位替换。比方说 encrypt(523) = 555 且 encrypt(213) = 333 。

请你返回数组中所有元素加密后的 和 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def sumOfEncryptedInt(self, nums: List[int]) -> int:
        def encrypt(x):
            m = len(str(x))
            n = 0
            while x:
                n = max(n, x % 10)
                x = x // 10
            n1 = 0
            for i in range(m):
                n1 = n1 + n * 10 ** i
            return n1
        res = 0
        for x in nums:
            res += encrypt(x)
        return res

第389场周赛

100248. 字符串及其反转中是否存在同一子字符串

给你一个字符串 s ，请你判断字符串 s 是否存在一个长度为 2 的子字符串，在其反转后的字符串中也出现。

如果存在这样的子字符串，返回 true；如果不存在，返回 false 。

1
2
3
4
5
6
7
class Solution:
    def isSubstringPresent(self, s: str) -> bool:
        sr = s[::-1]
        for i in range(len(s)-1):
            if s[i:i+2] in sr:
                return True
        return False

100236. 统计以给定字符开头和结尾的子字符串总数

给你一个字符串 s 和一个字符 c 。返回在字符串 s 中并且以 c 字符开头和结尾的

非空子字符串

的总数。

1
2
3
4
class Solution:
    def countSubstrings(self, s: str, c: str) -> int:
        n = s.count(c)
        return n * (n + 1) // 2

第127场双周赛

100272. 或值至少 K 的最短子数组 I

给你一个 非负 整数数组 nums 和一个整数 k 。

如果一个数组中所有元素的按位或运算 OR 的值 至少 为 k ，那么我们称这个数组是 特别的 。

请你返回 nums 中 最短特别非空

子数组

的长度，如果特别子数组不存在，那么返回 -1 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
        n = len(nums)
        res = n
        flag = False
        for i in range(n):
            tmp = 0
            for j in range(i,n):
                tmp |= nums[j]
                if tmp >= k: 
                    flag = True
                    res = min(res, j-i+1)
                    break
        return res if flag else -1

100250. 得到更多分数的最少关卡数目

给你一个长度为 n 的二进制数组 possible 。

莉叩酱和冬坂五百里正在玩一个有 n 个关卡的游戏，游戏中有一些关卡是 困难 模式，其他的关卡是 简单 模式。如果 possible[i] == 0 ，那么第 i 个关卡是 困难 模式。一个玩家通过一个简单模式的关卡可以获得 1 分，通过困难模式的关卡将失去 1 分。

游戏的一开始，莉叩酱将从第 0 级开始 按顺序 完成一些关卡，然后冬坂五百里会完成剩下的所有关卡。

假设两名玩家都采取最优策略，目的是 最大化 自己的得分，莉叩酱想知道自己 最少 需要完成多少个关卡，才能获得比冬坂五百里更多的分数。

请你返回莉叩酱获得比冬坂五百里更多的分数所需要完成的 最少 关卡数目，如果 无法 达成，那么返回 -1 。

注意，每个玩家都至少需要完成 1 个关卡。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def minimumLevels(self, possible: List[int]) -> int:
        tot = 0
        for item in possible:
            if item == 1: tot += 1
            else: tot -= 1
        leet = 0
        for i,item in enumerate(possible[:-1]):
            if item == 1: leet += 1
            else: leet -= 1
            if leet > tot-leet: return i+1
        return -1

第391场周赛

100263. 哈沙德数

如果一个整数能够被其各个数位上的数字之和整除，则称之为 哈沙德数（Harshad number）。给你一个整数 x 。如果 x 是 哈沙德数 ，则返回 x 各个数位上的数字之和，否则，返回 -1 。

1
2
3
4
5
6
7
8
class Solution:
    def sumOfTheDigitsOfHarshadNumber(self, x: int) -> int:
        tmp = x
        s = 0
        while tmp:
            s += tmp % 10
            tmp //= 10
        return s if x % s == 0 else -1

100235. 换水问题 II

给你两个整数 numBottles 和 numExchange 。

numBottles 代表你最初拥有的满水瓶数量。在一次操作中，你可以执行以下操作之一：

  • 喝掉任意数量的满水瓶，使它们变成空水瓶。
  • 用 numExchange 个空水瓶交换一个满水瓶。然后，将 numExchange 的值增加 1 。

注意，你不能使用相同的 numExchange 值交换多批空水瓶。例如，如果 numBottles == 3 并且 numExchange == 1 ，则不能用 3 个空水瓶交换成 3 个满水瓶。

返回你 最多 可以喝到多少瓶水。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def maxBottlesDrunk(self, numBottles: int, numExchange: int) -> int:
        res = 0
        empty_bottles = 0
        while numBottles or empty_bottles >= numExchange:
            if numBottles:
                res += numBottles
                empty_bottles += numBottles
                numBottles = 0
            if empty_bottles >= numExchange:
                empty_bottles -= numExchange
                numBottles += 1
                numExchange += 1
        return res

100266. 交替子数组计数

给你一个二进制数组nums

如果一个子数组中 不存在 两个 相邻 元素的值 相同 的情况，我们称这样的子数组为 交替子数组 。

返回数组 nums 中交替子数组的数量。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def countAlternatingSubarrays(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [[1,-1] for _ in range(n)]
        for i in range(1,n):
            if nums[i] != nums[i-1]:
                dp[i][0] = dp[i-1][0] + i - dp[i-1][1]
                dp[i][1] = dp[i-1][1]
            else:
                dp[i][0] = dp[i-1][0] + 1
                dp[i][1] = i-1
        return dp[-1][0]

第392场周赛

100264. 最长的严格递增或递减子数组

返回数组 nums 中 严格递增 或 严格递减 的最长非空子数组的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def longestMonotonicSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        res, tmp = 1, 1
        grow = True
        for i in range(n):
            if grow and i < n-1:
                if nums[i+1] > nums[i]: tmp += 1  
                elif nums[i+1] < nums[i]: 
                    tmp = 2
                    grow = False
                else: tmp = 1
            elif not grow and i < n-1:
                if nums[i+1] < nums[i]: tmp += 1
                elif nums[i+1] > nums[i]: 
                    tmp = 2
                    grow = True
                else: tmp = 1
            res = max(res,tmp)
        return res

100242. 满足距离约束且字典序最小的字符串

给你一个字符串 s 和一个整数 k 。

定义函数 distance(s1, s2) ，用于衡量两个长度为 n 的字符串 s1 和 s2 之间的距离，即：

  • 字符 'a' 到 'z' 按 循环 顺序排列，对于区间 [0, n - 1] 中的 i ，计算所有「 s1[i] 和 s2[i] 之间 最小距离」的 和 。

例如，distance("ab", "cd") == 4 ，且 distance("a", "z") == 1 。

你可以对字符串 s 执行 任意次 操作。在每次操作中，可以将 s 中的一个字母 改变 为 任意 其他小写英文字母。

返回一个字符串，表示在执行一些操作后你可以得到的 字典序最小 的字符串 t ，且满足 distance(s, t) <= k 。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def getSmallestString(self, s: str, k: int) -> str:
        i = 0
        tmp = ''
        while k > 0 and i < len(s):
            move = min(abs(ord(s[i]) - ord('a')), 26 - abs(ord(s[i]) - ord('a')))
            if k >= move: tmp += 'a'
            else: tmp += chr(ord(s[i]) - k)
            k -= move
            i += 1
        return tmp + s[i:] if i < len(s) else tmp

3107. 使数组中位数等于 K 的最少操作数

给你一个整数数组 nums 和一个 非负 整数 k 。

一次操作中，你可以选择任一下标 i ，然后将 nums[i] 加 1 或者减 1 。

请你返回将 nums 中位数 变为 k 所需要的 最少 操作次数。

一个数组的 中位数 指的是数组按 非递减 顺序排序后最中间的元素。如果数组长度为偶数，我们选择中间两个数的较大值为中位数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def minOperationsToMakeMedianK(self, nums: List[int], k: int) -> int:
        nums.sort()
        n = len(nums)
        i = n//2
        res = 0
        mid = nums[i]
        if mid < k:
            while i < n and nums[i] < k:
                res += k - nums[i]
                i += 1
        elif mid > k:
            while i >= 0 and nums[i] > k:
                res += nums[i] - k
                i -= 1
        return res