leetcode443. String Compression

nifhlheimr 发布于2019-08-16 16:41 / 1156人阅读

摘要：题目要求对字符串进行简单的压缩操作，压缩的规则是，如果出现多个重复的字母，则用字母加上字母出现的字数进行表示。如果字母只出现一次，则不记录次数。

题目要求

Given an array of characters, compress it in-place.

The length after compression must always be smaller than or equal to the original array.

Every element of the array should be a character (not int) of length 1.

After you are done modifying the input array in-place, return the new length of the array.

 
Follow up:
Could you solve it using only O(1) extra space?

 
Example 1:

Input:
["a","a","b","b","c","c","c"]

Output:
Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]

Explanation:
"aa" is replaced by "a2". "bb" is replaced by "b2". "ccc" is replaced by "c3".
 

Example 2:

Input:
["a"]

Output:
Return 1, and the first 1 characters of the input array should be: ["a"]

Explanation:
Nothing is replaced.
 

Example 3:

Input:
["a","b","b","b","b","b","b","b","b","b","b","b","b"]

Output:
Return 4, and the first 4 characters of the input array should be: ["a","b","1","2"].

Explanation:
Since the character "a" does not repeat, it is not compressed. "bbbbbbbbbbbb" is replaced by "b12".
Notice each digit has it"s own entry in the array.
 

Note:

All characters have an ASCII value in [35, 126].
1 <= len(chars) <= 1000.

对字符串进行简单的压缩操作，压缩的规则是，如果出现多个重复的字母，则用字母加上字母出现的字数进行表示。如果字母只出现一次，则不记录次数。

思路和代码

核心思路是用三个指针分别记录三个下标：
p1: 记录压缩后的内容的插入下标
p2: 记录当前相同字符串的起始位置
p3: 记录当前和起始位置比较的字符串的位置

一旦出现p3的值不等于p2或是p3的值大于字符数组的长度，则将压缩结果从p1开始填写，实现O(1)的空间复杂度。

    public int compress(char[] chars) {
        int p1 = 0;
        int p2 = 0;
        int p3 = 1;
        while(p2 < chars.length) {
            if(p3 >= chars.length || chars[p3] != chars[p2]) {
                int length = p3 - p2;
                chars[p1++] = chars[p2];
                if(length != 1) {
                    int count = 0;
                    while(length != 0) {
                        int num = length % 10;
                        for(int i = p1+count ; i>p1 ; i--) {
                            chars[i] = chars[i-1];
                        }
                        chars[p1] = (char)("0" + num);
                        length /= 10;
                        count++;
                    }
                    p1 += count;
                }
                p2 = p3;
            }
            p3++;

        }
        return p1;
    }

云服务器 GPU云服务器 LeetCode_String compression Leetcod LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/74119.html

LeetCode 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

tain335 2019-08-26 10:28 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0
Leetcode之Union-Find(并查集)

摘要：并查集包括查询和联合，主要使用不相交集合查询主要是用来决定不同的成员是否在一个子集合之内联合主要是用来把多个子集合成一个集合的实际运用计算机网络检查集群是否联通电路板检查不同的电路元件是否联通初始化联通与检测与是否联通返回联通的数并查集(Union-Find)包括查询(Find)和联合(Union)，主要使用不相交集合(Disjoint-Sets)查询(Find)主要是用来决定不同的...

roland_reed 2019-08-15 13:44 评论0 收藏0
[LintCode] String Compression

String Compression Implement a method to perform basic string compression using the counts of repeated characters. For example, the string aabcccccaaa would become a2b1c5a3. If the compressed string w...

Cruise_Chan 2019-08-15 13:24 评论0 收藏0
[Leetcode] Graph Valid Tree 判断一个图是否为树

摘要：只有一个连通分量还没有环，就是树，无根树。无向图边的两端是对称的，无向图讲究连通这个概念，没有方向，没有拓扑，很像集合，所以非常适合用并查集来解决。并查集写法参考注意方法用找的老大哥，合并的是的老大哥。 Graph Valid Tree Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each...

xbynet 2019-08-14 14:04 评论0 收藏0