算法题记录 19

132.分割回文串2（困难）

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。

返回符合要求的 最少分割次数 。

涉及知识点

字符串，dfs

解决思路

很简单能想到深搜，枚举分割出的最右边那段子串的左端点 l：
如果 s[l] 到 s[r] 是回文串，那么在 l−1 和 l 之间切一刀，接下来需要解决的子问题为：
把前缀 s[0] 到 s[l−1] 分割成一些子串，使每个子串都是回文串的最少分割次数，即 dfs(l−1)。
所有情况取最小值即可。

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)

3297.统计重新排列后包含另一个字符串的子字符串数目1（1847）

给你两个字符串 word1 和 word2 。

如果一个字符串 x 重新排列后，word2 是重排字符串的 前缀 ，那么我们称字符串 x 是 合法的 。

请你返回 word1 中 合法 子字符串 的数目。

涉及知识点

滑动窗口

解决思路

很迅速能想到统计各字符出现次数，通过滑动窗口对子字符串进行判定并统计子字符串的数目。

class Solution:
    def validSubstringCount(self, s: str, t: str) -> int:
        if len(s) < len(t):
            return 0

        # t 的字母出现次数与 s 的字母出现次数之差
        diff = defaultdict(int)  # 也可以用 Counter(t)，但是会慢很多
        for c in t:
            diff[c] += 1

        # 窗口内有 less 个字母的出现次数比 t 的少
        less = len(diff)

        ans = left = 0
        for c in s:
            diff[c] -= 1
            if diff[c] == 0:
                # c 移入窗口后，窗口内 c 的出现次数和 t 的一样
                less -= 1
            while less == 0:  # 窗口符合要求
                if diff[s[left]] == 0:
                    # s[left] 移出窗口之前，检查出现次数，
                    # 如果窗口内 s[left] 的出现次数和 t 的一样，
                    # 那么 s[left] 移出窗口后，窗口内 s[left] 的出现次数比 t 的少
                    less += 1
                diff[s[left]] += 1
                left += 1
            ans += left
        return ans

3019.按键变更的次数（1176）

给你一个下标从 0 开始的字符串 s ，该字符串由用户输入。按键变更的定义是：使用与上次使用的按键不同的键。例如 s = “ab” 表示按键变更一次，而 s = “bBBb” 不存在按键变更。

返回用户输入过程中按键变更的次数。

注意：shift 或 caps lock 等修饰键不计入按键变更，也就是说，如果用户先输入字母 ‘a’ 然后输入字母 ‘A’ ，不算作按键变更。

涉及知识点

字符串

解决思路

秒答题。

class Solution:
    def countKeyChanges(self, s: str) -> int:
        count=0
        s=s.lower()
        for each in range(len(s)-1):
            if s[each]!=s[each+1]:
                count+=1
        return count

638.大礼包（中等）

在 LeetCode 商店中， 有 n 件在售的物品。每件物品都有对应的价格。然而，也有一些大礼包，每个大礼包以优惠的价格捆绑销售一组物品。

给你一个整数数组 price 表示物品价格，其中 price[i] 是第 i 件物品的价格。另有一个整数数组 needs 表示购物清单，其中 needs[i] 是需要购买第 i 件物品的数量。

还有一个数组 special 表示大礼包，special[i] 的长度为 n + 1 ，其中 special[i][j] 表示第 i 个大礼包中内含第 j 件物品的数量，且 special[i][n] （也就是数组中的最后一个整数）为第 i 个大礼包的价格。

返回 确切 满足购物清单所需花费的最低价格，你可以充分利用大礼包的优惠活动。你不能购买超出购物清单指定数量的物品，即使那样会降低整体价格。任意大礼包可无限次购买。

涉及知识点

dfs

解决思路

很显然的dfs题，可以将需求转换为二进制码来压缩状态，提高算法效率。

class Solution:
    def shoppingOffers(
        self, price: List[int], special: List[List[int]], needs: List[int]
    ) -> int:
        @cache
        def dfs(cur: int) -> int:
            ans = sum(p * (cur >> (i * bits) & 0xF) for i, p in enumerate(price))
            for offer in special:
                nxt = cur
                for j in range(len(needs)):
                    if (cur >> (j * bits) & 0xF) < offer[j]:
                        break
                    nxt -= offer[j] << (j * bits)
                else:
                    ans = min(ans, offer[-1] + dfs(nxt))
            return ans

        bits, mask = 4, 0
        for i, need in enumerate(needs):
            mask |= need << i * bits
        return dfs(mask)

119.杨辉三角2（简单）

给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。

涉及知识点

预处理

解决思路

每一排的第一个数和最后一个数都是 1，即 c[i][0]=c[i][i]=1。
其余数字，等于左上方的数，加上正上方的数，即 c[i][j]=c[i−1][j−1]+c[i−1][j]。

MX = 34
c = [[1] * (i + 1) for i in range(MX)]
for i in range(2, MX):
    for j in range(1, i):
        # 左上方的数 + 正上方的数
        c[i][j] = c[i - 1][j - 1] + c[i - 1][j]

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        return c[rowIndex]

2545.根据第K场考试的分数排序（1294）

班里有 m 位学生，共计划组织 n 场考试。给你一个下标从 0 开始、大小为 m x n 的整数矩阵 score ，其中每一行对应一位学生，而 score[i][j] 表示第 i 位学生在第 j 场考试取得的分数。矩阵 score 包含的整数 互不相同 。

另给你一个整数 k 。请你按第 k 场考试分数从高到低完成对这些学生（矩阵中的行）的排序。

返回排序后的矩阵。

涉及知识点

排序

解决思路

对于python是秒答题，熟悉sort用法即可。

class Solution:
    def sortTheStudents(self, score: List[List[int]], k: int) -> List[List[int]]:
        score.sort(key=lambda x:x[k],reverse=True)
        return score

782.变为棋盘（1294）

一个 n x n 的二维网络 board 仅由 0 和 1 组成 。每次移动，你能交换任意两列或是两行的位置。

返回 将这个矩阵变为 “棋盘” 所需的最小移动次数 。如果不存在可行的变换，输出 -1。

“棋盘” 是指任意一格的上下左右四个方向的值均与本身不同的矩阵。

涉及知识点

分类讨论

解决思路

有难度，先判断能否变成棋盘，再讨论要多少次。
board 要能变成棋盘，有两个必要条件：

只有两种行：A 行是从 0101⋯ 交换得到的，也就是说，A 行中的 0 的个数和 1 的个数相差至多为 1；B 行是从 1010⋯ 交换得到的，和 A 行完全相反。
这两种行的个数相差至多为 1。

统计 A 行和 B 行的个数。统计的过程中，如果发现有一行既不是 A 行也不是 B 行，直接返回 −1。统计结束后，如果发现 A 行和 B 行的个数相差超过 1，也返回 −1。

比如把 s=001110 通过交换元素，变成 t=010101。这其中不同出现了 4 次。我们需要让 s 中的 0 在偶数下标上，1 在奇数下标上。那么把奇数上的 0 和偶数上的 1 交换，就可以满足要求，所以只需要4/2=2次。答案是第一行的最小交换次数，加上第一列的最小交换次数。
​

class Solution:
    def movesToChessboard(self, board: List[List[int]]) -> int:
        # 第一行，0 和 1 的个数之差不能超过 1
        first_row = board[0]
        row_cnt = Counter(first_row)
        if abs(row_cnt[0] - row_cnt[1]) > 1:
            return -1

        # 第一列，0 和 1 的个数之差不能超过 1
        first_col = list(next(zip(*board)))
        col_cnt = Counter(first_col)
        if abs(col_cnt[0] - col_cnt[1]) > 1:
            return -1

        # 每一行和第一行比较，要么完全相同，要么完全不同
        for row in board:
            same = row[0] == first_row[0]
            for x, y in zip(row, first_row):
                if (x == y) != same:
                    return -1

        # 计算最小交换次数
        def min_swap(s: List[int], cnt: Counter) -> int:
            n = len(s)
            x0 = 1 if cnt[1] > cnt[0] else 0  # 如果 n 是偶数，x0 是 0
            # 计算规则见题解正文最后一段，这里 t[i] = i % 2 ^ x0
            diff = sum(x ^ i % 2 ^ x0 for i, x in enumerate(s))
            return diff // 2 if n % 2 else min(diff, n - diff) // 2

        return min_swap(first_row, row_cnt) + min_swap(first_col, col_cnt)

声明

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