力扣第 453 场周赛

762
Contest
LeetCode
本文最后更新于 2 分钟前，文中所描述的信息可能已发生改变。

3576. 数组元素相等转换 - 力扣（LeetCode） ​

解题思路 ​

代码复用，分别判断变成 1 或-1 的情况

示例代码 ​

python
class Solution:
    def canMakeEqual(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        def check(nums, t):
            cnt = 0
            a = nums[:]
            for i in range(n - 1):
                if a[i] != t:
                    a[i + 1] *= -1
                    cnt += 1
            return cnt <= k and a[-1] == t
        return check(nums, 1) or check(nums, -1)

3577. 统计计算机解锁顺序排列数 - 力扣（LeetCode） ​

解题思路 ​

脑筋急转弯，判断能否解锁所有计算机，不能则返回 0，能就计算除计算机编号 0 外的所有编号排序个数

示例代码 ​

python
factorial = cache(factorial)
class Solution:
    def countPermutations(self, complexity: List[int]) -> int:
        return int(min(complexity[1:]) > complexity[0]) and factorial(len(complexity) - 1) % (10 ** 9 + 7)

3578. 统计极差最大为 K 的分割方式数 - 力扣（LeetCode） ​

解题思路 ​

参考：划分型 DP + 单调队列优化（Python/Java/C++/Go）

示例代码 ​

python
class Solution:
    def countPartitions(self, nums: List[int], k: int) -> int:
        n = len(nums)
        mod = 10 ** 9 + 7
        mn = deque()
        mx = deque()
        p = [0] * (n + 1)
        p[0] = 1
        l = 0
        for r, x in enumerate(nums):
            while mn and nums[mn[-1]] >= x: mn.pop()
            mn.append(r)
            while mx and nums[mx[-1]] <= x: mx.pop()
            mx.append(r)
            while nums[mx[0]] - nums[mn[0]] > k:
                if mx[0] == l: mx.popleft()
                if mn[0] == l: mn.popleft()
                l += 1
            s = p[r] - (p[l - 1] if l else 0)
            p[r + 1] = p[r] + s % mod
        return p[-1] - p[-2]
python
class Solution:
    def countPartitions(self, nums: List[int], k: int) -> int:
        n = len(nums)
        mod = 10 ** 9 + 7
        mn = deque()
        mx = deque()
        f = [0] * (n + 1)
        f[0] = 1
        l = s = 0
        for r, x in enumerate(nums):
            s += f[r]
            while mn and nums[mn[-1]] >= x: mn.pop()
            mn.append(r)
            while mx and nums[mx[-1]] <= x: mx.pop()
            mx.append(r)
            while nums[mx[0]] - nums[mn[0]] > k:
                s -= f[l]
                if mx[0] == l: mx.popleft()
                if mn[0] == l: mn.popleft()
                l += 1
            f[r + 1] = s % mod
        return f[-1]
python
class Solution:
    def countPartitions(self, nums: List[int], k: int) -> int:
        n = len(nums)
        mod = 10 ** 9 + 7
        sl = SortedList()
        p = [0] * (n + 1)
        p[0] = 1
        l = 0
        for r, x in enumerate(nums):
            sl.add(x)
            while sl[-1] - sl[0] > k:
                sl.discard(nums[l])
                l += 1
            s = p[r] - (p[l - 1] if l else 0)
            p[r + 1] = p[r] + s % mod
        return p[-1] - p[-2]

3579. 字符串转换需要的最小操作数 - 力扣（LeetCode） ​

解题思路 ​

枚举，哈希表计算操作次数

示例代码 ​

python
class Solution:
    def minOperations(self, word1: str, word2: str) -> int:
        n = len(word1)
        f = [n] * (n + 1)
        f[0] = 0
        def cal(s1, s2):
            diff = swap = 0
            cnt = Counter()
            for a, b in zip(s1, s2):
                if a != b:
                    diff += 1
                if cnt[b + a] and a != b:
                    cnt[b + a] -= 1
                    swap += 1
                else:
                    cnt[a + b] += 1
            return diff - swap

        for i in range(n + 1):
            for j in range(i):
                s1, s2 = word1[j: i], word2[j: i]
                res = min(cal(s1, s2), cal(s1[::-1], s2) + 1)
                f[i] = min(f[i], f[j] + res)
        return f[n]
力扣第 455 场周赛
力扣第 454 场周赛