[数据结构与算法]LeetCode面试金典0106 字符串压缩

字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。
比如，字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没
有变短，则返回原先的字符串。你可以假设字符串中只包含大小写英文字母（a至z）。
链接:?https://leetcode-cn.com/problems/compress-string-lcci/

目录

解题思路

双指针算法

代码

字符串压缩法

代码

解题思路

双指针算法

定义两个指针 left right。如果right 指针处的字符等于 left指针 处的字符 cont++。
相当于我(right)和你(left)一起跳格子。 我先走 我每次走一个就回头和你比较一下，如果我格子里面的字母和你一样我接下来就再走一个，count++；
如果不同 就将 sb.apped(你所在的格子的值).append(count) 然后我就让你走到我这个格子里来，
我再接着走，知道我走到格子的尽头，也就是循环完毕。

代码

    public static String compressString(String S) {
        char[] chars = S.toCharArray();
        int left = 0;
        int right = 0;
        int count = 0;
        StringBuilder sb = new StringBuilder();
        while (right < chars.length) {
            while (chars[left] == chars[right]) {
                count++;
                right++;
                // 判断到最后一个字符之后 right还会+1去比较 这里防止数组越界
                if (right == chars.length) {
                    break;
                }
            }
            sb.append(chars[left]).append(count);
            left = right;
            count = 0;
        }
        // 比较长度
        if (S.length() > sb.toString().length()) {
            return sb.toString();
        } else {
            return S;
        }
    }

字符串压缩法

其实思路差不多，定义一个str记录开始的时候是哪个字符。
循环charr数组去和 str比较 只有两种情况： 要么相同 要么不相同。
只是要处理一下最后一个字符。

代码

   public static String compressString(String S) {
        if (S == null || S.length() < 3) {
            return S;
        }
        char[] chars = S.toCharArray();
        StringBuilder sb = new StringBuilder();
        char str = chars[0];
        int count = 0;
        for (int i = 0; i < chars.length; i++) {
            if (str == chars[i]) {
                count++;
            } else {
                sb.append(str).append(count);
                str = chars[i];
                count = 1;
            }
        }
        // 尾巴处理
        if (count > 0) {
            sb.append(str).append(count);
        }
        return S.length() > sb.toString().length() ? sb.toString() : S;
    }