leetcode-443. 压缩字符串刷题笔记（c++）

比眉伴天荒 2023-02-22 13:39 66阅读 0赞

#### 写在前面 ####

*  难度：简单
 *  `循环 + 多个临时变量`，不再赘述

#### 题目详情 ####

给定一组字符，使用原地算法将其压缩。
    
    压缩后的长度必须始终小于或等于原数组长度。
    
    数组的每个元素应该是长度为1 的字符（不是 int 整数类型）。
    
    在完成原地修改输入数组后，返回数组的新长度。
    
    进阶：
    你能否仅使用O(1) 空间解决问题？
    
    示例 1：
    
    输入：
    ["a","a","b","b","c","c","c"]
    
    输出：
    返回 6 ，输入数组的前 6 个字符应该是：["a","2","b","2","c","3"]
    
    说明：
    "aa" 被 "a2" 替代。"bb" 被 "b2" 替代。"ccc" 被 "c3" 替代。
    示例 2：
    
    输入：
    ["a"]
    
    输出：
    返回 1 ，输入数组的前 1 个字符应该是：["a"]
    
    解释：
    没有任何字符串被替代。
    示例 3：
    
    输入：
    ["a","b","b","b","b","b","b","b","b","b","b","b","b"]
    
    输出：
    返回 4 ，输入数组的前4个字符应该是：["a","b","1","2"]。
    
    解释：
    由于字符 "a" 不重复，所以不会被压缩。"bbbbbbbbbbbb" 被 “b12” 替代。
    注意每个数字在数组中都有它自己的位置。
    
    提示：
    
    所有字符都有一个ASCII值在[35, 126]区间内。
    1 <= len(chars) <= 1000。

#### ac代码 ####

*  解题思想
    
     *  字符有序（题意）
     *  1层总循环
        
         *  2层循环合并、计数字符、`将统计数转换为字符串（可能存在多位数）`

class Solution
    {
        
    public:
        int compress(vector<char>& chars)
        {
        
            int cnt = 0, j = 0, pj = 0, csize = chars.size();
            while (j < csize)
            {
        
                chars[cnt++] = chars[j];
                pj = j;
                while (j < csize && chars[cnt - 1] == chars[j])
                    j++;
                if (j - pj > 1)
                    for (char c : to_string(j - pj))
                        chars[cnt++] = c;
            }
            return cnt;
        }
    };

*  参考文章
    
     *  [LeetCode \#443 String Compression 压缩字符串][LeetCode _443 String Compression]

[LeetCode _443 String Compression]: https://www.jianshu.com/p/a9affc170320