本教程深入探讨Java中字符串压缩(如abbbccccc压缩为ab3c4)的实现方法。我们将重点解析常见的循环计数逻辑,并着重解决在处理字符串末尾连续字符时容易出现的计数遗漏问题。通过提供优化后的代码示例和详细解释,帮助开发者构建健壮高效的字符串压缩功能。
什么是字符串压缩?
字符串压缩是一种常见的数据处理技术,旨在通过缩短字符串的长度来节省存储空间或提高传输效率。其中一种常见的压缩方式是“游程编码”(run-length encoding, rle),它通过将连续重复的字符替换为该字符及其出现的次数来工作。例如,字符串aaabbc可以被压缩为a3b2c或a3b2c1(如果计数为1则省略)。本教程的目标是将abbbccccc压缩为ab3c4。
java实现字符串压缩的常见思路
实现字符串压缩的基本思路通常涉及遍历字符串,并维护当前字符及其连续出现的次数。当遇到一个与当前字符不同的字符时,或者遍历到字符串末尾时,就将前一个字符及其计数添加到结果字符串中,然后重置计数器和当前字符。
在Java中,由于String对象的不可变性,频繁地使用+运算符进行字符串拼接会导致创建大量的中间String对象,从而影响性能。因此,推荐使用StringBuilder类来高效地构建结果字符串。
原始问题中的逻辑缺陷分析
在实现字符串压缩时,一个常见的陷阱是未能正确处理字符串末尾的连续字符。原始代码的逻辑如下:
// 原始代码片段(简化) for (int i = 0; i <= len ; i++) { if(i != len) { // 确保不是最后一个字符 if(str.charAt(i) == str.charAt(i+1)) { count++; continue; } // 当字符不同时,或count == 1时,将字符和计数添加到newString if(count == 1) { newString = newString+str.charAt(i); } else { newString = newString+str.charAt(i)+count; } // 重置count count = 1; } } return newString; // 在循环结束后直接返回
这个代码片段的问题在于,它将字符及其计数添加到结果字符串的条件是str.charAt(i) != str.charAt(i+1)(即当前字符与下一个字符不同),或者count == 1。当循环到达字符串的最后一个字符组时(例如”abbbccccc”中的”ccccc”),在最后一个c处,i已经等于len,i+1会越界,或者即使不越界,循环的内部逻辑也无法在字符组的末尾(即最后一个c之后)触发将c和4添加到newString的操作。当循环结束时,”ccccc”这个组的字符和计数(c和4)仍然停留在count变量中,而没有被添加到newString,导致最终输出缺失。
立即学习“Java免费学习笔记(深入)”;
简而言之,循环内部的逻辑依赖于“下一个字符”来判断是否需要输出当前字符组。当没有“下一个字符”时(即遍历到字符串末尾),这个输出条件就无法满足。
优化后的Java字符串压缩实现
为了解决上述问题,我们需要确保在循环结束后,如果还有未处理的字符组(即count大于0),也要将其添加到结果字符串中。更优雅的解决方案是将字符组的判断和输出逻辑统一在循环内部,确保无论是字符变化还是字符串结束,都能正确处理当前字符组。
以下是优化后的Java字符串压缩代码示例:
import java.lang.StringBuilder; public class StringCompressor { /** * 压缩给定字符串,将连续重复的字符替换为字符和其出现次数。 * 例如:"abbbccccc" 压缩为 "ab3c4"。 * 如果字符串为空或NULL,则返回空字符串。 * 如果字符只出现一次,则不添加数字1。 * * @param str 待压缩的字符串。 * @return 压缩后的字符串。 */ public static String getCompressedString(String str) { // 1. 处理边界条件:空字符串或null if (str == null || str.isEmpty()) { return ""; } StringBuilder compressedString = new StringBuilder(); int count = 1; // 记录当前字符的连续出现次数 int n = str.Length(); // 字符串长度 // 2. 遍历字符串 for (int i = 0; i < n; i++) { // 3. 检查当前字符是否与下一个字符相同 // 确保 i + 1 不会越界 if (i + 1 < n && str.charAt(i) == str.charAt(i + 1)) { count++; // 如果相同,则增加计数 } else { // 4. 字符不同,或者已经到达字符串末尾 // 将当前字符添加到结果中 compressedString.append(str.charAt(i)); // 如果计数大于1,则将计数添加到结果中 if (count > 1) { compressedString.append(count); } // 5. 重置计数器为1,为下一个字符组做准备 count = 1; } } // 6. 返回最终压缩后的字符串 return compressedString.toString(); } public static void main(String[] args) { // 测试用例 System.out.println("Original: "abbbccccc" -> Compressed: "" + getCompressedString("abbbccccc") + """); // 预期: ab3c4 System.out.println("Original: "aaaaa" -> Compressed: "" + getCompressedString("aaaaa") + """); // 预期: a5 System.out.println("Original: "abc" -> Compressed: "" + getCompressedString("abc") + """); // 预期: abc System.out.println("Original: "a" -> Compressed: "" + getCompressedString("a") + """); // 预期: a System.out.println("Original: "" -> Compressed: "" + getCompressedString("") + """); // 预期: "" System.out.println("Original: "aaabbc" -> Compressed: "" + getCompressedString("aaabbc") + """); // 预期: a3b2c System.out.println("Original: "abccba" -> Compressed: "" + getCompressedString("abccba") + """); // 预期: abc2ba } }
代码解析
- 边界条件处理: 在函数开始时,我们首先检查输入的字符串是否为null或空。如果是,直接返回空字符串,避免后续操作引发异常或不必要的处理。
- StringBuilder初始化: 使用StringBuilder来构建压缩后的字符串,这比使用String的+操作符效率更高。
- 循环遍历: for循环从字符串的第一个字符遍历到最后一个字符。
- 字符比较与计数:
- if (i + 1 < n && str.charAt(i) == str.charAt(i + 1)):这个条件判断当前字符str.charAt(i)是否与下一个字符str.charAt(i + 1)相同。
- i + 1 < n:这是关键部分,它确保在访问str.charAt(i + 1)时不会发生IndexOutOfBoundsException。只有当i不是字符串的最后一个索引时,才会去比较下一个字符。
- 如果当前字符与下一个字符相同,count递增,然后continue到下一个循环迭代,继续计数。
- if (i + 1 < n && str.charAt(i) == str.charAt(i + 1)):这个条件判断当前字符str.charAt(i)是否与下一个字符str.charAt(i + 1)相同。
- 输出字符组:
- else块:当进入else块时,表示两种情况之一:
- 当前字符与下一个字符不同(即遇到了一个新的字符组的开始)。
- 已经遍历到字符串的最后一个字符(i + 1 >= n),此时没有下一个字符可以比较。
- 在这两种情况下,当前字符组的计数已经完成,需要将其添加到compressedString中。
- compressedString.append(str.charAt(i)):首先添加当前字符。
- if (count > 1) { compressedString.append(count); }:如果count大于1,才将计数数字添加到结果中。这样可以避免像a1这样的输出,而是直接输出a,符合常见的压缩约定。
- count = 1;:处理完当前字符组后,将count重置为1,为下一个字符组的计数做准备。
- else块:当进入else块时,表示两种情况之一:
- 返回结果: 循环结束后,compressedString.toString()将StringBuilder的内容转换为最终的String并返回。
注意事项与最佳实践
- 处理边界情况: 始终考虑空字符串、null输入以及只有一个字符的字符串。本教程的代码已包含这些处理。
- 性能优化: 在Java中,进行大量字符串拼接操作时,StringBuilder是优于String的+运算符的首选。
- 计数为1的字符: 根据需求决定是否省略计数为1的字符的数字。本教程选择省略,使输出更简洁(如abc而非a1b1c1)。
- 可读性: 使用有意义的变量名、适当的注释和清晰的代码结构可以大大提高代码的可读性和可维护性。
- 测试: 编写全面的测试用例,包括各种边界条件和普通情况,以确保代码的正确性。
总结
字符串压缩是一个经典的算法问题,它要求我们不仅要理解核心的遍历和计数逻辑,更要细致地处理各种边界条件,特别是字符串末尾字符组的处理。通过本教程,我们深入分析了原始代码中末尾字符计数遗漏的问题,并提供了一个健壮、高效且易于理解的Java解决方案。掌握这种细致入微的编程思维,对于开发高质量的软件至关重要。
评论(已关闭)
评论已关闭