算法题记录 20

1278.分割回文串3（1979）

给你一个由小写字母组成的字符串 s，和一个整数 k。

请你按下面的要求分割字符串：

首先，你可以将 s 中的部分字符修改为其他的小写英文字母。
接着，你需要把 s 分割成 k 个非空且不相交的子串，并且每个子串都是回文串。
请返回以这种方式分割字符串所需修改的最少字符数。

涉及知识点

字符串，dfs

解决思路

是“算法题记录19”中第一题的进阶，看似变得很复杂，要判断修改多少次。其实我们继续dfs的枚举思路，不用去管怎么最少修改，只需把所有可能枚举出来，并统计每种方法的修改次数，取最小即可。

class Solution:
    def minCut(self, s: str) -> int:
        # 返回 s[l:r+1] 是否为回文串
        @cache  # 缓存装饰器，避免重复计算 is_palindrome（一行代码实现记忆化）
        def is_palindrome(l: int, r: int) -> bool:
            if l >= r:
                return True
            return s[l] == s[r] and is_palindrome(l + 1, r - 1)

        @cache  # 缓存装饰器，避免重复计算 dfs（一行代码实现记忆化）
        def dfs(r: int) -> int:
            if is_palindrome(0, r):  # 已是回文串，无需分割
                return 0
            res = inf
            for l in range(1, r + 1):  # 枚举分割位置
                if is_palindrome(l, r):
                    res = min(res, dfs(l - 1) + 1)  # 在 l-1 和 l 之间切一刀
            return res

        return dfs(len(s) - 1)

3066.超过阈值的最少操作数2（1400）

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。

你可以对 nums 执行一些操作，在一次操作中，你可以：

选择 nums 中 最小 的两个整数 x 和 y 。
将 x 和 y 从 nums 中删除。
将 min(x, y) * 2 + max(x, y) 添加到数组中的任意位置。
注意，只有当 nums 至少 包含两个元素时，你才可以执行以上操作。

你需要使数组中的所有元素都 大于或等于 k ，请你返回需要的 最少 操作次数。

涉及知识点

最小堆

解决思路

秒答题，找个办法维护有序，取最小两个计算判断即可，用列表的话时间比较慢，最小堆是解决这种问题比较快的。

class Solution:
    def minOperations(self, h: List[int], k: int) -> int:
        heapify(h)
        ans = 0
        while h[0] < k:
            x = heappop(h)
            heapreplace(h, h[0] + x * 2)
            ans += 1
        return ans

3266.K次乘运算后的最终数组2（2509）

给你一个整数数组 nums ，一个整数 k 和一个整数 multiplier 。

你需要对 nums 执行 k 次操作，每次操作中：

找到 nums 中的 最小 值 x ，如果存在多个最小值，选择最 前面 的一个。
将 x 替换为 x * multiplier 。
k 次操作以后，你需要将 nums 中每一个数值对 109 + 7 取余。

请你返回执行完 k 次乘运算以及取余运算之后，最终的 nums 数组。

涉及知识点

最小堆,数学

解决思路

乍一看是秒答题，但实际上会发现在数值较大时会超时，我们需要对计算过程进行简化，然后会发现在数值较大、数量较多时仍会超时，而对于两个数 x 和 y，如果 x 在 y 左边，且 x≤y 以及 x⋅multiplier>y，那么我们会先操作 x，然后操作 y。由于 x⋅multiplier≤y⋅multiplier，这意味着下一次一定会操作 x。继续推导下去，后面的操作顺序一定是 y,x,y,x,⋯
所以我们可以先手动让原数组的最大值mx成为最小值，然后就可以依次循环乘不需要维护最小堆了。

class Solution:
    def getFinalState(self, nums: List[int], k: int, multiplier: int) -> List[int]:
        if multiplier == 1:  # 数组不变
            return nums

        MOD = 1_000_000_007
        n = len(nums)
        mx = max(nums)
        h = [(x, i) for i, x in enumerate(nums)]
        heapify(h)

        # 模拟，直到堆顶是 mx
        while k and h[0][0] < mx:
            x, i = h[0]
            heapreplace(h, (x * multiplier, i))
            k -= 1

        # 剩余的操作可以直接用公式计算
        h.sort()
        for i, (x, j) in enumerate(h):
            nums[j] = x * pow(multiplier, k // n + (i < k % n), MOD) % MOD
        return nums

3239.最少翻转次数使二进制矩阵回文1（1388）

给你一个 m x n 的二进制矩阵 grid 。

如果矩阵中一行或者一列从前往后与从后往前读是一样的，那么我们称这一行或者这一列是 回文 的。

你可以将 grid 中任意格子的值 翻转 ，也就是将格子里的值从 0 变成 1 ，或者从 1 变成 0 。

请你返回 最少 翻转次数，使得矩阵 要么 所有行是 回文的 ，要么所有列是 回文的 。

涉及知识点

字符串、表格

解决思路

要么行是回文的，要么列是回文的，可知这两种情况是等效的。我们只需对每行进行回文判断，遇见前后不同的值计数加一，然后对每列做同样的事，返回两个计数的最小值即可。

class Solution:
    def minFlips(self, grid: List[List[int]]) -> int:
        count1=0
        for row in grid:
            i=0
            while i<len(row)-1-i:
                if row[i]!=row[len(row)-1-i]:
                    count1+=1
                i+=1
        count2=0
        for j in range(len(grid[0])):
            i=0
            while i<len(grid)-1-i:
                if grid[i][j]!=grid[len(grid)-1-i][j]:
                    count2+=1
                i+=1
        return min(count1,count2)

声明

题目均来源于leetcode公开题库，部分方法解析来源于高赞题解，如有不妥请联系。