1.5利用字符重复出现的次数,编写一个方法,实现基本的字符串压缩功能。如字符串aabcccccaaa会变成a2b1c5a3。若压缩后的字符串没有变短,则返回原字符串。

方法1:直观却不够好。原因是字符串的拼接操作的时间复杂度为O(n平方)。

public String compressBad(String str)
{
    String mystr = "";
    char last = str.charAt(0);
    int count = 1;
    for (int i = 1; i < str.length(); i++)
    {
        if (str.charAt(i) = last)
        {
            count++;
        }
        else
        {
            mystr += last + "" + count;
            last = str.charAt(i)
            count = 1;
        }
    }
    return mystr + last + count;
}

方法2:以下使用了StringBuffer优化了部分性能。(PS:从逻辑上看没区别。)


String compressBetter(String str) {
int size = countCompression(str); if (size >= str.length()) { return str; } StringBuffer mystr = new StringBuffer(); char last = str.charAt(0); int count = 1; for (int i = 1; i < str.length(); i++) { if (str.charAt(i) == last) { count++; } else { mystr.append(last); mystr.append(ccount); last = str.charAt(i); count = 1; } } mystr.append(last); mystr.append(ccount); return mystr.toString(); }
//专门用来数长度
int countCompression(String str) { if (str == null || str.isEmpty()) return 0; char last = str.charAt(0); int size = 0; int count = 1; for (int i = 1; i <str.length(); i++) { if (str.charAt(i) == last) { count++; } else { last = str.charAt(i); size += 1 + String.valueOf(count).length(); count = 1; } } size += 1 + String.valueOf(count).length(); return size; }