冠军资讯
代码旅行家内容摘要：LeetCode 1717：贪心算法求解删除子字符串最大得分难题,
今天我们来聊聊 LeetCode 每日一题中的 1717 题，涉及到了 nice!!! 的贪心算法思想，即删除子字符串的最大得分。这道题的核心在于如何选择删除哪些子字符串以获得最大的总分，而贪心算法提供了一种高效的解决思路。遇到这种字符串匹配和删除的场景，如果数据量较大，我们也要考虑是否可以利用 KMP 算法做预处理，加快匹配速度。
问题场景重现
题目是这样的：给定一个字符串 s 和两个整数 x 和 y。你可以执行以下操作任意次数：
- 从
s中删除子字符串"ab"并获得x分。 - 从
s中删除子字符串"ba"并获得y分。
返回你能获得的最大得分。
例如：
输入：s = "cdababab", x = 4, y = 5
输出：19
解释：
- 删除 "ba" 得到 5 分，s = "cdabab"
- 删除 "ba" 得到 5 分，s = "cdab"
- 删除 "ab" 得到 4 分，s = "cd"
总得分为 5 + 5 + 4 = 14。
底层原理深度剖析：贪心算法的选择
贪心算法的核心在于每一步都做出当前看来最优的选择，期望最终能够达到全局最优解。对于这道题，我们可以考虑两种贪心策略：
- 优先删除得分更高的子字符串。
- 根据字符串中
a和b的数量比例决定删除顺序。
第一种策略通常是更有效的。我们可以先尝试删除得分更高的子字符串，直到无法删除为止，然后再删除得分较低的子字符串。这种策略能够保证在每一步都最大化当前得分。
在实现上，我们可以使用栈来辅助删除子字符串。具体来说，我们遍历字符串 s，如果栈顶的字符和当前字符能够组成 "ab" 或 "ba"，就从栈中弹出栈顶字符，并累加相应的得分。否则，就将当前字符压入栈中。
这种算法的时间复杂度是 O(n)，其中 n 是字符串 s 的长度。空间复杂度也是 O(n)，主要用于栈的存储。
具体的代码解决方案 (Java)
class Solution {
public int maximumGain(String s, int x, int y) {
int score = 0;
// 优先删除得分高的子字符串
String first = "ab", second = "ba";
if (x < y) {
first = "ba";
second = "ab";
int temp = x;
x = y;
y = temp;
}
StringBuilder stack = new StringBuilder();
for (char c : s.toCharArray()) {
stack.append(c);
int len = stack.length();
if (len >= 2) {
String lastTwo = stack.substring(len - 2, len);
if (lastTwo.equals(first)) {
score += x;
stack.delete(len - 2, len); // 删除"ab"或者"ba"
} else if (lastTwo.equals(second)) {
score += y;
stack.delete(len - 2, len); // 删除"ab"或者"ba"
}
}
}
return score;
}
}
这里我们优先判断 x 和 y 的大小，保证 first 存储的是得分更高的子字符串，second 存储的是得分较低的子字符串。通过 StringBuilder 模拟栈操作，简化了代码逻辑。
实战避坑经验总结
- 注意边界条件：例如，字符串
s为空或者x和y都为 0 的情况。 - 优先顺序：一定要优先删除得分高的子字符串，否则可能会得到错误的答案。
- 数据规模：如果字符串
s非常长，可以考虑使用更高效的数据结构，例如使用数组模拟栈，避免频繁的字符串拷贝。同时，也要注意JVM的GC调优，避免频繁 Full GC 影响性能。如果后端服务是使用 Spring Boot 框架，要合理设置 JVM 参数。 - 测试用例：编写充分的测试用例，覆盖各种情况，确保代码的正确性。
- 避免重复计算：一些同学可能采用递归或者动态规划，但是该题使用贪心算法最佳，代码简洁高效。遇到类似问题，不要盲目套用复杂的算法。
- 关注并发场景：在实际的生产环境中，如果该算法作为服务的一部分，需要考虑并发请求的处理。可以使用线程池或者异步编程来提高服务的吞吐量。如果采用 Nginx 做反向代理，需要合理配置
worker_processes和worker_connections，保证服务能够承受高并发的压力。同时也要监控服务器的 CPU、内存、IO 等指标，及时发现和解决性能瓶颈。
这道 nice!!! 题的解法就分享到这里，希望对大家有所帮助。祝大家刷题愉快！
