首页 > Java > java教程 > 正文

Java字符串压缩:实现重复字符计数编码

聖光之護
发布: 2025-10-08 11:20:27
原创
494人浏览过

Java字符串压缩:实现重复字符计数编码

本教程详细讲解如何使用Java实现字符串的重复字符计数压缩(Run-Length Encoding)。通过分析一个常见的编码错误,即忽略字符串末尾字符及其计数的问题,我们将展示如何编写一个健壮的算法,确保所有连续重复的字符序列都能被正确压缩,并提供完整的示例代码和注意事项。

字符串重复字符计数压缩(Run-Length Encoding)原理

字符串重复字符计数压缩(run-length encoding, rle)是一种简单的数据压缩算法,其核心思想是将字符串中连续重复出现的字符序列替换为字符本身加上其重复的次数。例如,字符串 "aaabbc" 经过rle压缩后变为 "a3b2c"。这种方法在处理包含大量连续重复字符的数据时非常有效。

常见实现思路与陷阱

实现RLE通常涉及遍历字符串,统计连续相同字符的个数。当遇到不同的字符或到达字符串末尾时,将之前统计的字符和其计数添加到结果字符串中。然而,在这个过程中,一个常见的陷阱是未能正确处理字符串末尾的字符序列。

考虑以下一个尝试实现RLE的Java代码片段:

public class Test12CompressString {
    public static String getCompressedString(String str) {
        String newString = ""; // 使用String进行拼接效率较低
        int count = 1;
        int len = str.length()-1; // 最后一个字符的索引
        for (int i = 0; i <= len ; i++) {
            if(i != len) { // 避免越界访问str.charAt(i+1)
                // 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 ( 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",但实际输出是 "ab3",丢失了末尾的 "c4"。其根本原因在于:

  1. 循环条件与边界处理不当: for (int i = 0; i <= len ; i++) 配合 if(i != len) 的判断,使得当 i 等于 len (即处理字符串最后一个字符) 时,整个 if(i != len) 块内的逻辑都被跳过。这意味着最后一个字符 str.charAt(len) 从未被处理并添加到 newString 中。
  2. 依赖字符变化触发添加: 代码逻辑中,字符及其计数的添加 (newString = newString+str.charAt(i)+count;) 发生在 str.charAt(i) != str.charAt(i+1) 时。对于字符串末尾的字符序列(如 "ccccc"),当循环处理到最后一个 c 时,由于后面没有字符来触发“字符变化”的条件,这个 c 及其统计的 count 永远不会被添加到 newString。

为了解决这个问题,我们需要确保无论字符是否发生变化,或者是否到达字符串末尾,当前累积的字符和计数都能够被正确地添加到结果中。

立即学习Java免费学习笔记(深入)”;

怪兽AI数字人
怪兽AI数字人

数字人短视频创作,数字人直播,实时驱动数字人

怪兽AI数字人44
查看详情 怪兽AI数字人

正确的实现方法

一种更健壮的RLE实现方法是,在循环中始终检查当前字符与下一个字符的关系。如果它们相同,则继续计数;如果不同或已到达字符串末尾,则将当前字符和其计数添加到结果中,并重置计数器。

import java.lang.StringBuilder; // 导入StringBuilder类

public class StringCompressor {

    /**
     * 对给定字符串执行Run-Length Encoding (RLE) 压缩。
     * 将连续重复的字符替换为字符本身及其重复次数。
     * 例如:"abbbccccc" -> "ab3c4"
     *
     * @param str 待压缩的原始字符串。
     * @return 压缩后的字符串。
     */
    public static String compressString(String str) {
        // 处理空字符串或null输入
        if (str == null || str.isEmpty()) {
            return "";
        }

        // 使用StringBuilder提高字符串拼接效率
        StringBuilder compressedString = new StringBuilder();
        int count = 1; // 记录当前字符的连续重复次数

        // 遍历字符串的每个字符
        for (int i = 0; i < str.length(); i++) {
            // 检查当前字符是否与下一个字符相同,并且确保i+1不会越界
            if (i + 1 < str.length() && str.charAt(i) == str.charAt(i + 1)) {
                count++; // 如果相同,则增加计数
            } else {
                // 如果字符不同,或者已经到达字符串的末尾
                // 将当前字符添加到结果中
                compressedString.append(str.charAt(i));
                // 如果计数大于1,则将计数也添加到结果中
                if (count > 1) {
                    compressedString.append(count);
                }
                // 重置计数器为1,准备统计下一个字符序列
                count = 1;
            }
        }
        return compressedString.toString(); // 返回最终的压缩字符串
    }

    public static void main(String[] args) {
        // 测试用例
        String str1 = "abbbccccc";
        System.out.println("Original: \"" + str1 + "\", Compressed: \"" + compressString(str1) + "\""); // 预期: "ab3c4"

        String str2 = "aabbcc";
        System.out.println("Original: \"" + str2 + "\", Compressed: \"" + compressString(str2) + "\""); // 预期: "a2b2c2"

        String str3 = "abc";
        System.out.println("Original: \"" + str3 + "\", Compressed: \"" + compressString(str3) + "\""); // 预期: "abc"

        String str4 = "aaaaa";
        System.out.println("Original: \"" + str4 + "\", Compressed: \"" + compressString(str4) + "\""); // 预期: "a5"

        String str5 = "";
        System.out.println("Original: \"" + str5 + "\", Compressed: \"" + compressString(str5) + "\""); // 预期: ""

        String str6 = "z";
        System.out.println("Original: \"" + str6 + "\", Compressed: \"" + compressString(str6) + "\""); // 预期: "z"
    }
}
登录后复制

代码解析

  1. 空字符串/Null处理: 函数首先检查输入字符串是否为 null 或空,如果是,则直接返回空字符串,避免后续操作的错误。
  2. StringBuilder: 使用 StringBuilder 而不是 String 的 + 运算符进行字符串拼接。这是因为 String 的 + 运算会创建大量中间字符串对象,导致性能下降,而 StringBuilder 可以在原有对象上进行修改,效率更高。
  3. 循环遍历: for (int i = 0; i < str.length(); i++) 确保遍历了字符串中的每一个字符。
  4. 条件判断:
    • if (i + 1 < str.length() && str.charAt(i) == str.charAt(i + 1)):这个条件判断是核心。它首先确保 i + 1 不会越界(即当前字符不是最后一个字符),然后检查当前字符 str.charAt(i) 是否与下一个字符 str.charAt(i + 1) 相同。
    • 如果相同,说明是连续重复的字符,count 递增。
    • else 块:如果字符不同,或者 i 已经是字符串的最后一个索引(此时 i + 1 < str.length() 为 false),则表示当前连续的字符序列已经结束。
      • compressedString.append(str.charAt(i)):将当前字符添加到结果中。
      • if (count > 1) { compressedString.append(count); }:如果 count 大于1,说明字符重复了多次,将重复次数也添加到结果中。如果 count 等于1,则不添加数字(例如,"a" 压缩后仍为 "a",而不是 "a1")。
      • count = 1;:重置 count 为1,为下一个字符序列的统计做准备。

这种实现方式能够正确处理所有情况,包括字符串末尾的字符序列。

注意事项

  • 边界条件测试: 在开发任何字符串处理函数时,务必测试各种边界条件,包括空字符串、单字符字符串、所有字符都相同、所有字符都不同等情况。
  • 性能优化: 对于频繁的字符串拼接操作,应优先考虑使用 StringBuilder 或 StringBuffer(线程安全版本),而不是 String 的 + 运算符。
  • 算法复杂度: 此RLE算法的时间复杂度为O(N),其中N是字符串的长度,因为它只需要单次遍历字符串。空间复杂度为O(N)(最坏情况下,没有字符重复,结果字符串与原字符串长度相同)。
  • 字符集: 此算法适用于任何字符集,因为它只是比较和拼接字符。

总结

实现字符串的重复字符计数压缩(RLE)是一个常见的编程练习,它强调了在循环中正确处理边界条件的重要性。通过仔细设计循环逻辑,特别是在字符序列结束或到达字符串末尾时如何处理累积的字符和计数,可以避免常见的逻辑错误。同时,采用 StringBuilder 进行字符串构建是Java中优化字符串操作的良好实践。掌握这些原则有助于编写出高效且健壮的字符串处理代码。

以上就是Java字符串压缩:实现重复字符计数编码的详细内容,更多请关注php中文网其它相关文章!

最佳 Windows 性能的顶级免费优化软件
最佳 Windows 性能的顶级免费优化软件

每个人都需要一台速度更快、更稳定的 PC。随着时间的推移,垃圾文件、旧注册表数据和不必要的后台进程会占用资源并降低性能。幸运的是,许多工具可以让 Windows 保持平稳运行。

下载
来源:php中文网
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
最新问题
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责申明 意见反馈 讲师合作 广告合作 最新更新 English
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送
PHP中文网APP
随时随地碎片化学习
PHP中文网抖音号
发现有趣的

Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号