本文深入探讨了字符串压缩算法，旨在将连续重复字符替换为字符加计数。我们将分析在实现此类算法时常见的末尾字符序列处理遗漏问题，并提供一个优化后的Java解决方案，确保所有字符序列都能被正确压缩，从而实现如“abbbccccc”到“ab3c4”的准确转换。
理解字符串压缩需求
字符串压缩是一种常见的数据处理技术，其目标是将连续重复的字符序列替换为该字符及其重复次数。例如，将字符串 “abbbccccc” 压缩为 “ab3c4″。这种技术在日志处理、数据存储和网络传输中都有应用，有助于减少数据量。
原代码分析及问题定位
我们来看一个尝试实现此功能的Java代码示例：
public class Test12CompressString { public static String getCompressedString(String str) { String newString = ""; int count = 1; int len = str.Length()-1; // len 是字符串最后一个字符的索引 for (int i = 0; i <= len ; i++) { if(i != len) { // 仅当不是最后一个字符时执行此块 // System.out.println(i); // 调试输出 if(str.charAt(i) == str.charAt(i+1)) { count++; continue; // 字符相同，计数增加，跳过当前循环剩余部分 } // 字符不同时，或达到最后一个字符前一个字符时 if(count == 1) { newString = newString+str.charAt(i); // 如果只出现一次，直接添加字符 } else { newString = newString+str.charAt(i)+count; // 添加字符和计数 } // 以下代码块逻辑存在问题，且与前一个if/else重复，实际不会被有效执行 // if ( str.charAt(i) != str.charAt(i+1)) { // count = 1; // continue; // } } } return newString; } public static void main(String[] args) { String str = "abbbccccc"; String ans = getCompressedString(str); System.out.print(ans); // 预期输出: ab3c4, 实际输出: ab3 } }
当输入字符串为 “abbbccccc” 时，预期输出是 “ab3c4″，但实际输出却是 “ab3″。问题出在代码对字符串末尾字符序列的处理上。
问题根源分析：
- if(i != len) 条件限制： 循环体内的核心逻辑被 if(i != len) 包裹。这意味着当 i 等于 len（即处理到字符串的最后一个字符时），整个条件块内的代码都不会被执行。
- 依赖字符变化触发输出： 代码只有在当前字符与下一个字符不同时 (str.charAt(i) != str.charAt(i+1))，或者当前序列的计数达到 count > 1 时，才会将字符及其计数添加到 newString 中。对于字符串末尾的连续字符序列（例如 “ccccc”），由于其后没有不同的字符，这个条件永远不会满足，导致最后一个序列（”c4″）永远不会被添加到结果字符串中。
- 冗余且错误的逻辑： 内部的 if (str.charAt(i) != str.charAt(i+1)) 块是多余的，且其 continue 语句会导致逻辑中断，但由于前面的 if/else 已经处理了字符不同时的逻辑，实际上这块代码的执行路径非常有限且容易混淆。
简而言之，原代码在处理到字符串的倒数第二个字符时，如果它与最后一个字符相同，会正确地增加 count。但当循环到达最后一个字符时，由于 i == len，所有输出逻辑都被跳过，导致最后一个字符序列无法被处理。
立即学习“Java免费学习笔记（深入）”；
优化算法思路
要解决这个问题，我们需要确保在以下两种情况下将当前字符及其计数添加到结果中：
- 当前字符与下一个字符不同时（即一个字符序列的结束）。
- 循环遍历到字符串的最后一个字符时（此时当前序列也必然结束）。
为了提高字符串拼接的效率，我们应该使用 StringBuilder 而不是 String 的 + 操作符。
实现优化后的字符串压缩
以下是修正并优化后的Java代码：
public class CompressedString { public static String getCompressedString(String str) { if (str == NULL || str.isEmpty()) { return ""; // 处理空字符串或null的情况 } StringBuilder compressedString = new StringBuilder(); int count = 1; for (int i = 0; i < str.length(); i++) { // 检查当前字符是否与下一个字符相同，且未超出字符串边界 if (i + 1 < str.length() && str.charAt(i) == str.charAt(i + 1)) { count++; // 字符相同，计数增加 } else { // 字符不同，或者已经到达字符串的末尾 compressedString.append(str.charAt(i)); // 添加当前字符 if (count > 1) { compressedString.append(count); // 如果计数大于1，添加计数 } count = 1; // 重置计数器为1，为下一个字符序列做准备 } } return compressedString.toString(); } public static void main(String[] args) { String str1 = "abbbccccc"; System.out.println("Original: " + str1 + ", Compressed: " + getCompressedString(str1)); // 预期: ab3c4 String str2 = "a"; System.out.println("Original: " + str2 + ", Compressed: " + getCompressedString(str2)); // 预期: a String str3 = "aaabbc"; System.out.println("Original: " + str3 + ", Compressed: " + getCompressedString(str3)); // 预期: a3b2c String str4 = ""; System.out.println("Original: " + str4 + ", Compressed: " + getCompressedString(str4)); // 预期: (空字符串) String str5 = "abc"; System.out.println("Original: " + str5 + ", Compressed: " + getCompressedString(str5)); // 预期: abc } }
代码逻辑解释：
- 空字符串处理： 首先检查输入字符串是否为 null 或空，如果是则直接返回空字符串，避免后续错误。
- StringBuilder 初始化： 使用 StringBuilder 替代 String 进行拼接，以提高性能。
- 循环遍历： 循环 i 从 0 到 str.length() – 1，确保每个字符都被访问到。
- 条件判断：
- if (i + 1 < str.length() && str.charAt(i) == str.charAt(i + 1))：这个条件判断当前字符是否与下一个字符相同，并且 i + 1 没有超出字符串的边界。如果两者都满足，说明当前字符是连续序列的一部分，我们只需增加 count。
- else 块：如果上述条件不满足，说明当前字符是其所在连续序列的最后一个字符（因为下一个字符不同，或者它已经是字符串的最后一个字符）。此时，我们将：
- compressedString.append(str.charAt(i)): 将当前字符添加到结果中。
- if (count > 1) { compressedString.append(count); }: 如果 count 大于 1（表示有重复），则将计数也添加到结果中。
- count = 1;: 重置 count 为 1，为处理下一个可能的新字符序列做准备。
- 返回结果： 循环结束后，compressedString.toString() 将 StringBuilder 的内容转换为最终的 String 返回。
通过这种方式，无论字符序列在字符串的哪个位置，包括末尾，都能被正确地处理和压缩。
关键点与注意事项
- 边界条件处理： 在处理字符串时，尤其要注意循环的边界条件以及对字符串长度的检查（如 i + 1 < str.length()），这对于避免 IndexOutOfBoundsException 至关重要。
- StringBuilder 的使用： 在循环中进行字符串拼接时，使用 StringBuilder 比直接使用 String 的 + 运算符效率更高，因为 String 的 + 操作会创建大量中间字符串对象，而 StringBuilder 则是在内部可变数组上操作。
- 代码可读性： 保持代码逻辑清晰，避免复杂的嵌套条件，可以提高代码的可读性和维护性。
- 空字符串/单字符处理： 良好的算法应该能优雅地处理各种边缘情况，例如空字符串、只包含一个字符的字符串或没有重复字符的字符串。
总结
字符串压缩是一个典型的考察循环逻辑和边界条件处理能力的编程问题。通过分析原始代码的不足，我们发现未能正确处理字符串末尾字符序列是导致压缩不完整的主要原因。优化后的解决方案通过在字符序列结束或到达字符串末尾时统一处理字符及其计数，并结合 StringBuilder 提高了效率和健壮性。这强调了在设计算法时，对所有可能情况，特别是边界条件的全面考虑至关重要。
评论（已关闭）
评论已关闭