算法题记录 22

1328.破坏回文串（1474）

给你一个由小写英文字母组成的回文字符串 palindrome ，请你将其中 一个 字符用任意小写英文字母替换，使得结果字符串的 字典序最小 ，且 不是 回文串。

请你返回结果字符串。如果无法做到，则返回一个 空串 。

如果两个字符串长度相同，那么字符串 a 字典序比字符串 b 小可以这样定义：在 a 和 b 出现不同的第一个位置上，字符串 a 中的字符严格小于 b 中的对应字符。例如，”abcc” 字典序比 “abcd” 小，因为不同的第一个位置是在第四个字符，显然 ‘c’ 比 ‘d’ 小。

涉及知识点

贪心

解决思路

秒答题。

class Solution:
    def breakPalindrome(self, s: str) -> str:
        n = len(s)
        if n == 1:
            return ""
        # 把第一个不等于 a 的字母改成 a
        # 只需找前一半，如果前一半没有不等于 a 的字母，那么后一半肯定也没有
        for i in range(n // 2):
            if s[i] != 'a':
                return s[:i] + 'a' + s[i + 1:]
        # 除了回文中心，全是 a
        return s[:-1] + 'b'  # 最后一个字母改成 b

3083.字符串及其反转中是否存在同一子字符串（1474）

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

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

涉及知识点

字符串

解决思路

秒答题，用集合记录遇见过的字符串即可。

class Solution:
    def isSubstringPresent(self, s: str) -> bool:
        vis = set()
        for x, y in pairwise(s):
            vis.add(x + y)
            if y + x in vis:
                return True
        return False

3181.执行操作可获得的最大总奖励2（2688）

给你一个整数数组 rewardValues，长度为 n，代表奖励的值。

最初，你的总奖励 x 为 0，所有下标都是 未标记 的。你可以执行以下操作 任意次 ：

从区间 [0, n - 1] 中选择一个 未标记 的下标 i。
如果 rewardValues[i] 大于 你当前的总奖励 x，则将 rewardValues[i] 加到 x 上（即 x = x + rewardValues[i]），并 标记 下标 i。
以整数形式返回执行最优操作能够获得的 最大 总奖励。

涉及知识点

背包、动态规划

解决思路

很快能注意到，如果我们对数组排序，问题就变为了背包问题。但是该题数据范围很大，如果用递归的格式写出来会导致内存爆掉、超时。我们需要更换为循环形式的动态规划，并通过位运算进行进一步优化。

会超时的递归写法

class Solution:
    def maxTotalReward(self, rewardValues: List[int]) -> int:
        rewardValues.sort()
        @cache
        def dfs(i:int,s:int)->int:
            tmp=s
            if s<rewardValues[i]:
                if i+1<len(rewardValues):
                    s=max(dfs(i+1,tmp+rewardValues[i]),s)
                else:
                    s=tmp+rewardValues[i]

            if i+1<len(rewardValues):
                s=max(dfs(i+1,tmp),s)
            return s

        return dfs(0,0)

正确解法

class Solution:
    def maxTotalReward(self, rewardValues: List[int]) -> int:
        f = 1
        for v in sorted(set(rewardValues)):
            f |= (f & ((1 << v) - 1)) << v
        return f.bit_length() - 1

声明

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