压缩字符串 -- LeetCode -- 8.21

压缩字符串

给你一个字符数组 chars ,请使用下述算法压缩:

从一个空字符串 s 开始。对于 chars 中的每组 连续重复字符 :

如果这一组长度为 1 ,则将字符追加到 s 中。
否则,需要向 s 追加字符,后跟这一组的长度。

示例 1:

  输入:chars = ["a","a","b","b","c","c","c"]
  输出:返回 6 ,输入数组的前 6 个字符应该是:["a","2","b","2","c","3"]
  解释:
    "aa" 被 "a2" 替代。"bb" 被 "b2" 替代。"ccc" 被 "c3" 替代。

思路:

  新建一个字符串 s 。便利 chars ,若前后元素不相等,则将前元素放入 s 中,并使用 to_string 函数将元素数量追加到 s 后;若相等,则统计相同的字符数量;

class Solution {
public:
    int compress(vector<char>& chars) {
        string s = "";
        int cnt = 1, l = chars.size();
        for(int i = 0; i < l - 1; i++){//由于是和下一个字符比较,所以不能遍历到最后,这也导致了最后一串字符将无法放入 s 中;
            if(chars[i] != chars[i + 1]){//和下一个字符比较,若不相等,字符放入 s 中,并追加其数量
                s += chars[i];
                if(cnt != 1) {
                    string ss = to_string(cnt);//将元素数量(整型)转换成字符串
                    s += ss;//将字符串追加到 s 后面
                    cnt = 1;//下一个元素数量重置为 1
                }
            }else   cnt++;//相等,则统计字符数量
        }
        s += chars[l - 1];//将最后字符及其数量放入 s
        if(cnt != 1) {
            string ss = to_string(cnt);
            s += ss;
            cnt = 1;
        }
        for(int i = 0; i < s.size(); i++){//将 s 中所有元素放入 chars 中;
            chars[i] = s[i];
        }
        return s.size();
    }
};

  

上一篇:NC17 最长回文子串


下一篇:经常使用的一些公共方法