Рубрики

Длина кодирования

Учитывая входную строку, напишите функцию, которая возвращает строку длины, закодированную для входной строки.

Например, если входная строка «wwwwaaadexxxxxx», то функция должна вернуть «w4a3d1e1x6».

а) Выберите первый символ из исходной строки.
б) Добавить выбранный символ в строку назначения.
c) Подсчитайте количество последующих вхождений выбранного символа и добавьте счет к строке назначения.
d) Выберите следующий символ и повторите шаги b) c) и d), если конец строки НЕ достигнут.

C ++

// Программа CPP для реализации кодирования длин серий
#include <bits/stdc++.h>

using namespace std;

  

void printRLE(string str)

{

    int n = str.length();

    for (int i = 0; i < n; i++) {

  

        // Считаем вхождения текущего персонажа

        int count = 1;

        while (i < n - 1 && str[i] == str[i + 1]) {

            count++;

            i++;

        }

  

        // Распечатать символ и его количество

        cout << str[i] << count;

    }

}

  

int main()

{

    string str = "wwwwaaadexxxxxxywww";

    printRLE(str);

    return 0;

}

Джава

// Java-программа для реализации кодирования длин серий

  

public class RunLength_Encoding {

    public static void printRLE(String str)

    {

        int n = str.length();

        for (int i = 0; i < n; i++) {

  

            // Считаем вхождения текущего персонажа

            int count = 1;

            while (i < n - 1 && 

                   str.charAt(i) == str.charAt(i + 1)) {

                count++;

                i++;

            }

  

            // Распечатать символ и его количество

            System.out.print(str.charAt(i));

            System.out.print(count);

        }

    }

  

    public static void main(String[] args)

    {

        String str = "wwwwaaadexxxxxxywww";

        printRLE(str);

    }

}

Выход:

w4a3d1e1x6y1w3

Реализация С

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_RLEN 50

  
/ * Возвращает строку длины, закодированную для

   исходная строка src * /

char* encode(char* src)

{

    int rLen;

    char count[MAX_RLEN];

    int len = strlen(src);

  

    / * Если все символы в исходной строке разные,

    тогда размер строки назначения будет вдвое больше входной строки.

    Например, если src "abcd", то dest будет "a1b1c1d1"

    Для других входных данных размер будет меньше, чем в два раза. * /

    char* dest = (char*)malloc(sizeof(char) * (len * 2 + 1));

  

    int i, j = 0, k;

  

    / * пройти по входной строке один за другим * /

    for (i = 0; i < len; i++) {

  

        / * Копировать первое вхождение нового персонажа * /

        dest[j++] = src[i];

  

        / * Подсчитать количество появлений нового персонажа * /

        rLen = 1;

        while (i + 1 < len && src[i] == src[i + 1]) {

            rLen++;

            i++;

        }

  

        / * Сохранить rLen в массиве символов [] * /

        sprintf(count, "%d", rLen);

  

        / * Копировать счет [] в пункт назначения * /

        for (k = 0; *(count + k); k++, j++) {

            dest[j] = count[k];

        }

    }

  

    / * завершить строку назначения * /

    dest[j] = '\0';

    return dest;

}

  
/ * программа драйвера для проверки вышеуказанной функции * /

int main()

{

    char str[] = "geeksforgeeks";

    char* res = encode(str);

    printf("%s", res);

    getchar();

}

Выход:

g1e2k1s1f1o1r1g1e2k1s1

Сложность времени: O (n)

Ссылки:
http://en.wikipedia.org/wiki/Run-length_encoding

Пожалуйста, пишите комментарии, если вы обнаружите, что приведенный выше код / алгоритм неверен, или найдете лучшие способы решения той же проблемы.

Рекомендуемые посты:

Длина кодирования

0.00 (0%) 0 votes