443. Compress strings

This is the 21st day of my participation in the August Text Challenge.More challenges in August

Given a character array chars, compress it using the following algorithm:

Start with an empty string s. For each group of consecutive repeating characters in chars:

If the length is 1, the character is appended to s. Otherwise, you need to append a character to s, followed by the length of the group. The compressed string S should not be returned directly and needs to be dumped into the character array chars. Note that if the length is 10 or more, it is split into multiple characters in the CHars array.

After modifying the input array, return the new length of the array.

You must design and implement an algorithm that uses only constant extra space to solve this problem.

Example 1:

Input: chars = [” a “, “a”, “b”, “b”, “c”, “c”, “c”] output: return to 6, the input of the array before 6 characters should be: [” a “, “2”, “b”, “2”, “c”, “3”] explains: “aa” is replaced by “a2″.” “Bb” is replaced by “b2”. “CCC” is replaced by “C3”.

Example 2:

Input: chars = [“a”] Output: returns 1, the first character of the input array should be: [“a”] Explanation: No strings are substituted.

Example 3:

Input: chars = [” a “, “b”, “b”, “b”, “b”, “b”, “b”, “b”, “b”, “b”, “b”, “b”, “b”] output: return 4, input array should be the first four characters: [” a “, “b”, “1”, “2”]. Explanation: The character “a” is not compressed because it is not repeated. BBBBBBBBBBBB “is replaced by” B12 “. Note that each number has its own place in the array.

Tip:

1 <= chars.length <= 2000

Chars [I] can be a lowercase letter, a uppercase letter, a number, or a symbol

Their thinking

Iterates through the character array to find the number of occurrences of consecutive characters

The difficulty is that we need to cut the number of occurrences into characters and write them back into the character array. We can maintain write Pointers one by one

First, we need to write consecutive characters. If the number of characters is greater than one, we need to split the number of characters and write to the array. Each character is written to the pointer later
Finally returns the position of the write pointer

code

class Solution {
    public int compress(char[] chars) {
        char pre=chars[0],cnt=1,w=1;
        for (int i = 1; i < chars.length; i++) {
            if (chars[i]==pre)
            {
                cnt++;
            }else {
                        if(cnt>1)
        {
               int old=w;
                while (cnt>0) {
                    chars[w++] = (char) ('0'+ cnt%10);
                    cnt/=10;
                }
                for (int l=old,r=w-1; l<r; l++,r--) {char c=chars[l];
                    chars[l]=chars[r];
                    chars[r]=c;
                }
                }
                cnt=1; pre=chars[i]; chars[w++]=pre; }}if(cnt>1)
        {
               int old=w;
                while (cnt>0) {
                    chars[w++] = (char) ('0'+ cnt%10);
                    cnt/=10;
                }
                for (int l=old,r=w-1; l<r; l++,r--) {charc=chars[l]; chars[l]=chars[r]; chars[r]=c; }}returnw; }}Copy the code

443. Compress strings