专栏首页chenjx85的技术专栏leetcode-443-String Compression

leetcode-443-String Compression

题目描述:

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:

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

要完成的函数:

int compress(vector<char>& chars) 

说明:

1、看完example之后才明白这道题要干嘛。要求在原本vector上面修改,然后输出最后vector的长度。空间复杂度是O(1)。

2、这道题目不难做,就是比较综合,考察多种操作。做法如下:

从vector首位开始处理,把碰到的第一个数记录下来,后续的数逐个跟它比较,如果相等就把后续的数删去,顺便记录删了几个数。

然后如果确实删去了数,那么把删去的数的个数+1,拆成一位一位的,插入在vector中,要注意插入的位置。

如果没有删去重复的后续的数,也就是记录下来的数只出现了一次,那么继续处理下一个数,仍然记录下来,覆盖掉原本的数。

直到vector所有字符都处理完毕。

有同学可能会疑惑为什么要删除和插入vector中的元素,因为题目要求要in-place处理,而且样例也有要求原vector要处理。

代码如下:

    int compress(vector<char>& chars) 
    {
        int i=0,j,count,ret=0;
        char t1;
        while(i<chars.size())
        {
            t1=chars[i];//t1记录碰到的数
            count=1;//出现了一次
            i++;//i指向下一个要处理的数
            while(chars[i]==t1&&i<chars.size())//如果出现重复了
            {
                chars.erase(chars.begin()+i);//把这个重复的数删掉,删完之后i没有变,仍然指向第i个
                count++;//出现了多一次
            }
            if(count==1)
                ret++;
            else
            {
                ret++;
                j=i;//记录i的数值,i此时指向和上一个不重复的数
                while(count!=0)
                {
                    ret++;
                    chars.insert(chars.begin()+i,count%10+'0');
                    j++;//记录i之后应该要指向第几个数
                    count/=10;
                }
                i=j;//i仍然指向下一个要处理的数
            }
            
        }
        return ret;
    }

上述代码实测8ms,beats 82.94% of cpp submissions。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode-804-Unique Morse Code Words

    chenjx85
  • leetcode-724-Find Pivot Index

    chenjx85
  • leetcode-541-Reverse String II

    chenjx85
  • NLP之tfidf与textrank算法细节对比基于结巴分词

    -NLP之tfidf与textrank算法细节对比 注:结巴默认在site-packages目录 关于结巴分词的添加停用词以及增加词相关操作可参考之前的...

    学到老
  • NLP之tfidf与textrank算法细节对比基于结巴分词

    -NLP之tfidf与textrank算法细节对比 注:结巴默认在site-packages目录 关于结巴分词的添加停用词以及增加词相关操作可参考之前的...

    学到老
  • 异构节点上安全多方计算的性能评估(CS CR)

    安全多方计算密码(MPC)是一个广泛的密码学概念,可用于保护私隐的计算。 使用 MPC,许多参与者可以协同计算一个函数,而不需要向其他人透露明文的实际输入或输出...

    用户7095611
  • ZooKeeper构建分布式锁(选译)

    作者:Scott Leberknight 译者: java达人 来源:http://www.sleberknight.com/blog/sleberkn/en...

    java达人
  • 开源在线编辑复合自动图表

    很多企业的业务对标准数据图表有很多的业务系统需求,而开发的节奏一直跟不上的。在报表开发中,很多的企业的流程是这样的: 1、BI负责数据的获取整合加工; 2、业务...

    openapplus
  • 浅谈numpy中np.array()与np.asarray的区别以及.tolist

    array和asarray都可以将结构数据转化为ndarray,但是主要区别就是当数据源是ndarray时,array仍然会copy出一个副本,占用新的内存,但...

    砸漏
  • POJ2318 TOYS 判断点与直线位置关系 【计算几何】

    Calculate the number of toys that land in each bin of a partitioned toy box.

    ACM算法日常

扫码关注云+社区

领取腾讯云代金券