Topic describes
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.
Answer key
Analog method, after traversing the discovery of repeated character groups, record the number of repeated characters count, and then according to the meaning of the [” character “+” number of repeated characters “] form storage.
The length of the character is compressed, but the chars input itself needs to be modified. So remember to modify chars at the end.
Execution time: 1 ms, beating 94.41% of all Java commits
Memory consumption: 38.2 MB, beating 29.67% of all Java commits
Pass test case: 72/72
import java.util.*; class Solution { public int compress(char[] chars) { // 0. Initstringbuilder res = new StringBuilder(); int i = 0; While (I < chars. Length) {int count = 1; While (I < chars. Length -1 && chars[I] == chars[I + 1]) {I ++; count++; If (count == 1) {res.append(chars[I]); if (count == 1) {res.append(chars[I]); } else if (count > 1) { res.append(chars[i]); res.append(count); } i++; Char [] result = res.tostring ().tochararray ();} // 4. for (int j = 0; j < result.length; j++) { chars[j] = result[j]; } return result.length; }}Copy the code