3

その場でランレングス エンコーディングを実行できますか (入力配列が非常に大きいと仮定します) AAAABBBBCCCCDDDD A4B4C4D4 などの場合に実行できます

しかし、ABCDEFG のような場合はどうすればよいのでしょうか? 出力は A1B1C1D1E1F1G1 になります

4

6 に答える 6

0

O(n)、インプレース RLE、これ以上のことは考えられませんでした。文字の出現回数が 1 の場合、数字は配置されません。文字が 11 回出現した場合は、a9a2 も配置されます。

void RLE(char *str) {
int len = strlen(str);
int count = 1, j = 0;
for (int i = 0; i < len; i++){
    if (str[i] == str[i + 1])
        count++;
    else {
        int times = count / 9;
        int rem = count % 9;
        for (int k = 0; k < times; k++) {
            str[j++] = str[i];
            _itoa(9, &str[j++], 10);
            count = count - 9;
        }
        if (count > 1) {
            str[j++] = str[i];
            _itoa(rem, &str[j++], 10);
            count = 1;
        }
        else 
            str[j++] = str[i];
    }
}
cout << str;

}

I/P => aaabcdeeeefghijklaaaaa

O/P => a3bcde4fghijkla5

于 2016-12-03T11:44:53.097 に答える
0

null は、どの項目が空で、エンコードで無視されるかを示すために使用されます。また、数字をエンコードすることはできません (AAA2222 => A324 => 324 回 'A' ですが、A3;24 です)。あなたの質問により、さらに多くの質問が開かれます。

これがC＃の「解決策」です

public static void Encode(string[] input)
{
    var writeIndex = 0;

    var i = 0;
    while (i < input.Length)
    {
        var symbol = input[i];
        if (symbol == null)
        {
            break;
        }

        var nextIndex = i + 1;

        var offset = 0;
        var count = CountSymbol(input, symbol, nextIndex) + 1;
        if (count == 1)
        {
            ShiftRight(input, nextIndex);
            offset++;
        }

        input[writeIndex++] = symbol;
        input[writeIndex++] = count.ToString();

        i += count + offset;
    }

    Array.Clear(input, writeIndex, input.Length - writeIndex);
}

private static void ShiftRight(string[] input, int nextIndex)
{
    var count = CountSymbol(input, null, nextIndex, (a, b) => a != b);
    Array.Copy(input, nextIndex, input, nextIndex + 1, count);
}

private static int CountSymbol(string[] input, string symbol, int nextIndex)
{
    return CountSymbol(input, symbol, nextIndex, (a, b) => a == b);
}

private static int CountSymbol(string[] input, string symbol, int nextIndex, Func<string, string, bool> cmp)
{
    var count = 0;

    var i = nextIndex;
    while (i < input.Length && cmp(input[i], symbol))
    {
        count++;
        i++;
    }

    return count;
}
于 2012-06-07T09:45:01.080 に答える
0

最初の解決策は、単一の文字を処理しません。たとえば、「こんにちは！」動作しないでしょう。私はまったく異なるアプローチを使用し、「insert()」関数を使用してインプレースに追加しました。これにより、「同じ」文字の合計が 10 を超えるか、100 を超えるか、1 を超えるかに関係なく、すべてが処理されます。

#include<iostream>
#include<algorithm>
using namespace std;

int main(){
    string name = "Hello Buddy!!";
    int start = 0;
    char distinct = name[0];
    for(int i=1;i<name.length()+1;){
        if(distinct!=name[i]){
            string s = to_string(i-start);
            name.insert(start+1,s);
            name.erase(name.begin() + start + 1 + s.length(),name.begin() + s.length() + i);
            i=start+s.length()+1;
            start=i;
            distinct=name[start];
            continue;
        }
        i++;
    }
    cout<<name;
}

何か間違っていることがあれば教えてください。

于 2016-08-14T14:45:13.257 に答える