443. String Compression

public class Solution {
    public int Compress(char[] chars) {
        int i = 0, res = 0;
        while (i < chars.Length) {
            int groupLength = 1;
            while (i + groupLength < chars.Length && chars[i + groupLength] == chars[i]) {
                groupLength++;
            }
            chars[res++] = chars[i];
            if (groupLength > 1) {
                foreach (char ch in groupLength.ToString()) {
                    chars[res++] = ch;
                }
            }
            i += groupLength;
        }
        return res;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int Compress(char[] chars) {
        int i = 0, res = 0;
        while (i < chars.size()) {
            int groupLength = 1;
            while (i + groupLength < chars.size() && chars[i + groupLength] == chars[i]) {
                groupLength++;
            }
            chars[res++] = chars[i];
            if (groupLength > 1) {
                foreach (char ch in groupLength.ToString()) {
                    chars[res++] = ch;
                }
            }
            i += groupLength;
        }
        return res;
    }
}

class Solution {
    public int compress(char[] chars) {
        int i = 0;
        int res = 0;
        while (i < chars.length) {
            int groupLength = 1;
            while (i + groupLength < chars.length && chars[i + groupLength] == chars[i]) {
                groupLength++;
            }
            chars[res++] = chars[i];
            if (groupLength > 1) {
                String strRepr = Integer.toString(groupLength);
                for (char ch : strRepr.toCharArray()) {
                    chars[res++] = ch;
                }
            }
            i += groupLength;
        }
        return res;
    }
}

var compress = function(chars) {
    let i = 0, res = 0;
    while (i < chars.length) {
        let groupLength = 1;
        while (i + groupLength < chars.length && chars[i + groupLength] === chars[i]) {
            groupLength++;
        }
        chars[res++] = chars[i];
        if (groupLength > 1) {
            let strRepr = groupLength.toString();
            for (let ch of strRepr) {
                chars[res++] = ch;
            }
        }
        i += groupLength;
    }
    return res;
};

class Solution:
    def compress(self, chars: List[str]) -> int:
        i = 0
        res = 0
        while i < len(chars):
            group_length = 1
            while (i + group_length < len(chars) and chars[i + group_length] == chars[i]):
                group_length += 1
            chars[res] = chars[i]
            res += 1
            if group_length > 1:
                str_repr = str(group_length)
                chars[res:res+len(str_repr)] = list(str_repr)
                res += len(str_repr)
            i += group_length
        return res

func compress(chars []byte) int {
    i, res := 0, 0
    for i < len(chars) {
        groupLength := 1
        for i+groupLength < len(chars) && chars[i+groupLength] == chars[i] {
            groupLength++
        }
        chars[res] = chars[i]
        res++
        if groupLength > 1 {
            strRepr := strconv.Itoa(groupLength)
            for j := 0; j < len(strRepr); j++ {
                chars[res] = strRepr[j]
                res++
            }
        }
        i += groupLength
    }
    return res
}

Explanation

Algorithm

Начните с пустой строки s. Для каждой группы последовательных повторяющихся символов в chars:

Если длина группы равна 1, добавьте символ к строке s.

В противном случае добавьте символ, а за ним длину группы.

Сжатая строка s не должна возвращаться отдельно, а вместо этого должна быть сохранена в входном массиве символов chars. Обратите внимание, что длины групп, которые равны 10 или более, будут разделены на несколько символов в chars.

После того как вы закончите модификацию входного массива, верните новую длину массива.

Вы должны написать алгоритм, который использует только постоянное дополнительное пространство.

Пример:

Input: chars = ["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: The groups are "aa", "bb", and "ccc". This compresses to "a2b2c3".

👨‍💻

Алгоритм:

Объявите переменные i – первый индекс текущей группы, и res – длина ответа (сжатой строки). Инициализируйте i = 0, res = 0.

Пока i меньше длины chars: Найдите длину текущей группы последовательных повторяющихся символов groupLength. Добавьте chars[i] к ответу (chars[res++] = chars[i]). Если groupLength > 1, добавьте строковое представление groupLength к ответу и увеличьте res соответственно. Увеличьте i на groupLength и перейдите к следующей группе.

Верните res.

😎