class Solution {
public:
int removeAlmostEqualCharacters(string word) {
}
};
100152. 消除相邻近似相等字符
给你一个下标从 0 开始的字符串 word 。
一次操作中，你可以选择 word 中任意一个下标 i ，将 word[i] 修改成任意一个小写英文字母。
请你返回消除 word 中所有相邻 近似相等 字符的 最少 操作次数。
两个字符 a 和 b 如果满足 a == b 或者 a 和 b 在字母表中是相邻的，那么我们称它们是 近似相等 字符。
示例 1：
输入：word = "aaaaa" 输出：2 解释：我们将 word 变为 "acaca" ，该字符串没有相邻近似相等字符。 消除 word 中所有相邻近似相等字符最少需要 2 次操作。
示例 2：
输入：word = "abddez" 输出：2 解释：我们将 word 变为 "ybdoez" ，该字符串没有相邻近似相等字符。 消除 word 中所有相邻近似相等字符最少需要 2 次操作。
示例 3：
输入：word = "zyxyxyz" 输出：3 解释：我们将 word 变为 "zaxaxaz" ，该字符串没有相邻近似相等字符。 消除 word 中所有相邻近似相等字符最少需要 3 次操作
提示：
1 <= word.length <= 100word 只包含小写英文字母。原站题解
golang 解法, 执行用时: 4 ms, 内存消耗: 2 MB, 提交时间: 2023-12-11 17:22:28
func removeAlmostEqualCharacters(s string) (ans int) {
for i := 1; i < len(s); i++ {
if abs(int(s[i-1])-int(s[i])) <= 1 {
ans++
i++
}
}
return
}
func abs(x int) int { if x < 0 { return -x }; return x }
java 解法, 执行用时: 1 ms, 内存消耗: 40.4 MB, 提交时间: 2023-12-11 17:20:24
// 贪心
public class Solution {
public int removeAlmostEqualCharacters(String s) {
int ans = 0;
for (int i = 1; i < s.length(); i++) {
if (Math.abs(s.charAt(i - 1) - s.charAt(i)) <= 1) {
ans++;
i++;
}
}
return ans;
}
}
cpp 解法, 执行用时: 4 ms, 内存消耗: 6.4 MB, 提交时间: 2023-12-11 17:19:54
class Solution {
public:
int removeAlmostEqualCharacters(string s) {
int ans = 0;
for (int i = 1; i < s.length(); i++) {
if (abs(s[i - 1] - s[i]) <= 1) {
ans++;
i++;
}
}
return ans;
}
};
python3 解法, 执行用时: 44 ms, 内存消耗: 16.1 MB, 提交时间: 2023-12-11 17:19:22
'''
贪心算法
每次发现两个相邻字母近似相等，就改右边那个
'''
class Solution:
def removeAlmostEqualCharacters(self, s: str) -> int:
ans = 0
i, n = 1, len(s)
while i < n:
if abs(ord(s[i - 1]) - ord(s[i])) <= 1:
ans += 1
i += 2
else:
i += 1
return ans