This is the 21st day of my participation in the August Text Challenge.More challenges in August
Topic describes
This is a 443. Compressed string on LeetCode with medium difficulty.
Tag: “analog”, “double pointer”, “string”
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.
** returns the new length of the input array after ** has modified it.
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".Copy the code
Example 2:
Input: chars = ["a"] Output: returns 1, the first character of the input array should be: ["a"] Explanation: No strings are substituted.Copy the code
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.Copy the code
Tip:
- 1 <= chars.length <= 2000
- Chars [I] can be a lowercase letter, a uppercase letter, a number, or a symbol
Double pointer
Let the input array cs be length NNN.
Use two Pointers I and j to point to “currently processed” and “where the answer is to be inserted” respectively:
i
The pointer is processed backwards, each time finding a contiguous segment with the same character
, let the length be
;- Inserts the current character into the answer and lets
j
Pointer moved back:cs[j++] = cs[i]
; - Check the length of the
If more than
, if greater than
, the number needs to be split and stored. Because in a simple implementation, we can only start with the ones bits
, so it needs to be usedstart
和end
Record the part where the numbers are stored and process them
after
Parts are flipped and updatedj
Pointer; - update
i
为idx
To loop through the next character.
Code:
class Solution {
public int compress(char[] cs) {
int n = cs.length;
int i = 0, j = 0;
while (i < n) {
int idx = i;
while (idx < n && cs[idx] == cs[i]) idx++;
int cnt = idx - i;
cs[j++] = cs[i];
if (cnt > 1) {
int start = j, end = start;
while(cnt ! =0) {
cs[end++] = (char)((cnt % 10) + '0');
cnt /= 10;
}
reverse(cs, start, end - 1);
j = end;
}
i = idx;
}
return j;
}
void reverse(char[] cs, int start, int end) {
while (start < end) {
chart = cs[start]; cs[start] = cs[end]; cs[end] = t; start++; end--; }}}Copy the code
- Time complexity: O(n)O(n)O(n)
- Space complexity: O(1)O(1)O(1)
The last
This is No.446 of our “Brush through LeetCode” series. The series started on 2021/01/01.
In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.
In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .
In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.