欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Leetcode——443. String Compression

程序员文章站 2024-03-14 13:42:28
...

题目原址

https://leetcode.com/problems/string-compression/description/

题目描述

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.

解题思路

这个题的含义很好理解,就是修改给定的字符数组,将相同的字符只存储一个,并且要存储相同字符的个数,且每个数要小于10,如果某个相同字符的个数是12个,就将12分为字符1和字符2存储在两个数组变量中。

因为要修改原数组,所以要定义一个变量记录数组修改的当前下标,每修改一次该下标值+1,并且题目要求最后要返回被修改后的数组中元素的个数。

  • 步骤1:通过for循环遍历数组中的所有元素,如果当前元素与要比较的元素相同,则记录相同元素的个数
  • 步骤2:如果不相同,就说明需要将之前相同的元素合并元素个数,修改数组
  • 步骤3:如果之前的元素相同的个数大于10,就需要将相同的元素个数拆分存储在数组中。
  • 步骤4:如果之前的元素相同的个数小于10,则直接将元素个数存储在比较的元素的下一个元素位置即可。
  • 步骤5:最后要修改下一层遍历的num的值,将相同元素的值置回1,将要比较的元素置为新的元素值
  • 步骤6:在步骤1中,如果遍历完整个数组后,整个数组的元素都一样,那么就不会执行步骤2-步骤5的操作,但是在这种情况下还是需要修改数组的,因此在循环外面要增加一个判断相同元素个数的操作,如果相同元素个数大于1,说明整个数组中的元素都一样,且数组的长度是大于1的,就要将相同的元素个数变为字符存储在数组中。
  • 步骤6:最后返回新的数组的长度

AC代码

class Solution {
    public int compress(char[] chars) {
        char prev = chars[0];
        int num=1;
        int newLen=0;

        for(int i=1;i<chars.length;i++)
        {
            if(chars[i]==prev)
                num++;
            else
            {
                if(num>1)
                {
                    chars[newLen++]=prev;
                    if(num/10>0)
                        chars[newLen++]=(char) ((int)(num/10)+48);
                    chars[newLen++]=(char) ((int)(num%10)+48);
                }
                else
                    chars[newLen++]=prev;
                num=1;
                prev=chars[i];
            }
        }

        if(num>1)
        {
            chars[newLen++]=prev;
            if(num/10>0)
                chars[newLen++]=(char) ((int)(num/10)+48);
            chars[newLen++]=(char) ((int)(num%10)+48);
        }
        else
            chars[newLen++]=prev;

        return newLen;
    }
}

感谢

https://leetcode.com/problems/string-compression/discuss/123312/Java-Solution-O(1)-Space-O(n)-Time-Complexity