就地运行长度编码算法

Question

我遇到一道面试题：

Given a input String: aaaaabcddddee, convert it to a5b1c1d4e2.

一个额外的约束是，这需要就地完成，意味着不应该使用额外的space（数组）。

保证编码后的字符串总是适合原始字符串。换句话说，不会出现像 abcde 这样的字符串，因为它会被编码为 a1b1c1d1e1，比原始字符串占用更多 space。

面试官给我的一个提示是遍历一次字符串并找到保存的 space。

有时我仍然卡住了，如果不使用额外的变量，输入字符串中的某些值可能会被覆盖。

有什么建议吗？

Answer 1

也许只是正常编码，但如果您发现输出索引超过了输入索引，请跳过“1”。然后当你完成后向后移动并在所有没有计数的字母后插入 1 ，将字符串的其余部分移回。在最坏的情况下（没有重复的字母）它是 O(N^2)，所以我认为可能有更好的解决方案。

编辑：看来我错过了最终字符串始终适合源的部分。有了这个限制，是的，这不是最佳解决方案。

EDIT2：它的 O(N) 版本在第一遍期间还计算最终压缩长度（在一般情况下可能比源长度更长），将指针 p1 设置为它，指针 p2到省略 1 的压缩字符串（因此 p2 <= p1），然后继续在两个指针上向后移动，将 p2 复制到 p1 并在必要时添加 1（当发生这种情况时，p2 和 p1 之间的差异将减小）

Answer 2

这是一道很好的面试题。

要点

有2个要点：

单个字符必须编码为c1;
编码后的长度总是小于原始数组。

从 1 开始，我们知道每个字符需要 至少 2 个位置进行编码。也就是说，只有单个字符需要多个space编码.

简单方法

从关键点，我们注意到单个字符在编码过程中给我们带来了很多问题，因为它们可能没有足够的空间来容纳编码后的字符串。那我们先留下它们，然后先压缩其他字符怎么样？

例如，我们从后面编码aaaaabcddddee，同时保留单个字符在前，我们将得到：

aaaaabcddddee
_____a5bcd4e2

然后我们可以安全地从头开始对部分编码的序列进行编码，给定关键点 2，这样就会有足够的 spaces。

分析

看来我们找到了解决方案，完成了吗？不。考虑这个字符串：

aaa3dd11ee4ff666

问题不限制字符范围，所以我们也可以使用数字。在这种情况下，如果我们仍然使用相同的方法，我们将得到：

aaa3dd11ee4ff666
__a33d212e24f263

好的，现在告诉我，你如何区分运行-length 和原始字符串中的那些数字？

嗯，我们需要尝试别的东西。

我们定义Encode Benefit (E)为：编码序列与原始连续字符序列的长度差。.

例如aa有E = 0，因为aa会被编码为a2，两者没有长度差异； aaa有E = 1，因为会被编码成a3，编码后和原来的长度差1。我们来看单字符的情况，它的E是多少？是的，它是 -1。根据定义，我们可以推导出E的公式：E = ori_len - encoded_len.

现在让我们回到问题。从关键点 2，我们知道编码后的字符串总是比原始字符串短。我们如何使用 E 来改写这个关键点？

很简单：sigma(E_i) >= 0，其中E_i是第i^个个连续字符子串的Encode Benefit。

比如你在问题中给出的样本：aaaaabcddddee，可以分解为5个部分：

E(0) = 5 - 2 = 3  // aaaaa -> a5
E(1) = 1 - 2 = -1 // b -> b1
E(2) = 1 - 2 = -1 // c -> c1
E(3) = 4 - 2 = 2  // dddd -> d4
E(4) = 2 - 2 = 0  // ee -> e2

西格玛将为：3 + (-1) + (-1) + 2 + 0 = 3 > 0。这意味着编码后将剩余 3 spaces。

但是，从这个例子中，我们可以看到一个潜在的问题：因为我们在做求和，即使最终答案大于0，也有可能在中间得到一些负数！

是的，这是一个问题，而且相当严重。如果我们得到 E 低于 0，这意味着我们没有足够的 space 来编码当前字符并且将覆盖它之后的一些字符。

但是但是但是，为什么要从第一组开始求和呢？为什么我们不能从中间的某个地方开始求和以跳过负数部分？让我们看一个例子：

2 0 -1 -1 -1 1 3 -1

如果我们从头开始求和，在索引4（从0开始）加上第三个-1后，我们会低于0；如果我们从索引 5 开始求和，当我们结束时循环回到索引 0，我们没有问题。

算法

分析让我们对算法有了更深入的了解：

从头开始，计算当前连续组的E，加到总数E_total；
如果E_total仍然是非负数 (>= 0)，我们很好，我们可以安全地进入下一组；
如果E_total低于0，我们需要从当前位置重新开始，即清除E_total，然后进行下一个位置。

如果我们到达序列的末尾并且E_total仍然是非负的，那么最后一个起点就是一个好的开始！此步骤需要 O(n) 时间。通常我们需要循环再检查，但是由于关键点2，我们肯定会有一个有效的答案，所以我们可以安全地停在这里。

然后我们可以回到起点开始传统的运行长度编码，到达终点后我们需要回到序列的开头来完成第一部分。棘手的部分是，我们需要使用字符串末尾剩余的 spaces。在那之后，我们需要做一些移位以防万一我们有一些顺序问题，并删除任何多余的白色 spaces，然后我们终于完成了:)

因此，我们有一个解决方案（代码只是伪造的，没有经过验证）：

// find the position first
i = j = E_total = pos = 0;
while (i < s.length) {
    while (s[i] == s[j]) j ++;
    E_total += calculate_encode_benefit(i, j);
    if (E_total < 0) {
        E_total = 0;
        pos = j;
    }
    i = j;
}

// do run length encoding as usual:
// start from pos, end with len(s) - 1, the first available place is pos
int last_available_pos = runlength(s, pos, len(s)-1, pos);
// a tricky part here is to make use of the remaining spaces from the end!!!
int fin_pos = runlength(s, 0, pos-1, last_available_pos);
// eliminate the white
eliminate(s, fin_pos, pos);
// update last_available_pos because of elimination
last_available_pos -= pos - fin_pos < 0 ? 0 : pos - fin_pos;
// rotate back
rotate(s, last_available_pos);

复杂性

我们的算法有4个部分：

找到起点：O(n)
运行-整个字符串的长度编码：O(n)
白space淘汰：O(n)
In place string rotation: O(n)

因此我们总共 O(n)。

可视化

假设我们需要对这个字符串进行编码：abccdddefggggghhhhh

第一步，我们需要找到起始位置：

Group 1: a     -> E_total += -1 -> E_total = -1 < 0 -> E_total = 0, pos = 1;
Group 2: b     -> E_total += -1 -> E_total = -1 < 0 -> E_total = 0, pos = 2;
Group 3: cc    -> E_total += 0  -> E_total = 0 >= 0 -> proceed;
Group 4: ddd   -> E_total += 1  -> E_total = 1 >= 0 -> proceed;
Group 5: e     -> E_total += -1 -> E_total = 0 >= 0 -> proceed;
Group 6: f     -> E_total += -1 -> E_total = -1 < 0 -> E_total = 0, pos = 9;
Group 7: ggggg -> E_total += 3  -> E_total = 3 >= 0 -> proceed;
Group 8: hhhhh -> E_total += 3  -> E_total = 6 >= 0 -> end;

所以起始位置将是 9:

         v this is the starting point
abccdddefggggghhhhh
abccdddefg5h5______
             ^ last_available_pos, we need to make use of these remaining spaces
abccdddefg5h5a1b1c2
d3e1f1___g5h5a1b1c2
      ^^^ remove the white space
d3e1f1g5h5a1b1c2
          ^ last_available_pos, rotate
a1b1c2d3e1f1g5h5

遗言

这个问题不简单，实际上把几个传统的编码面试问题自然地粘在一起了。建议的思维流程是：

观察规律，找出关键点；
意识到不足的原因space是因为编码单个字符；
量化每个连续字符组的编码benefit/cost (a.k.a Encoding Benefit);
使用您提出的量化来解释原始陈述；
想出算法找到好的起点；
弄清楚如何进行运行-length-encoding 有一个好的起点；
意识到您需要旋转编码字符串并消除白色 spaces;
找出执行字符串旋转的算法；
想出原地白space消除的算法。

老实说，对于一个面试者来说，短时间内想出一个可靠的算法是有点挑战的，所以你的分析流程很重要。什么都不要说，展现你的心流，这有助于面试官了解你现在的阶段。

Answer 3

O(n) 到位

设置变量 = 0;
从 1-length 开始循环并找到第一个不匹配的字符。
计数将是两个字符的索引之差。

让我们运行通过一个例子

s = "wwwwaaadexxxxxxywww"

向 s 添加一个虚拟字母

s = s + '#'

现在我们的字符串变成了

s = "wwwwaaadexxxxxxywww#"

我们稍后会回到这一步。

j 给出字符串的第一个字符。

j = 0 // s[j] = w

现在循环 1 - 长度。第一个不匹配的字符是 'a'

print(s[j], i - j) // i = 4, j = 0
j = i              // j = 4, s[j] = a

Output: w4

i 成为下一个不匹配的字符，即 'd'

print(s[j], i - j) // i = 7, j = 4 => a3
j = i              // j = 7, s[j] = d

Output: w4a3


.
.  (Skipping to the second last)
.

j = 15, s[j] = y, i = 16, s[i] = w
print(s[j], i - y) => y1

Output: w4a3d1e1x6y1

好的，现在我们到了最后一个，假设我们没有添加任何虚拟字母

j = 16, s[j] = w and we cannot print it's count 
because we've no 'mis-matching' character

这就是为什么需要添加一个虚拟字母。

这是一个 C++ 实现

void compress(string s){
    int j = 0;
    s = s + '#';
    for(int i=1; i < s.length(); i++){
        if(s[i] != s[j]){
            cout << s[j] << i - j;
            j = i;
        }
     }
}

int main(){
    string s = "wwwwaaadexxxxxxywww";
    compress(s);
    return 0;
}

输出：w4a3d1e1x6y1w3

Answer 4

如果允许使用插入和删除字符串函数，那么您可以使用此实现高效地获得解决方案。

#include<bits/stdc++.h>
using namespace std;
int dig(int n){
    int k=0;
    while(n){
        k++;
        n/=10;
    }
    return k;
}
void stringEncoding(string &n){
    int i=0;
    for(int i=0;i<n.size();i++){
        while(n[i]==n[i+j])j++;
        n.erase((i+1),(j-1));
        n.insert(i+1,to_string(j));
        i+=(dig(j));
    }
}
int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);
    string n="kaaaabcddedddllllllllllllllllllllllp";
    stringEncoding(n);
    cout<<n;
}

这将给出以下输出：k1a4b1c1d2e1d3l22p1

就地运行长度编码算法

In Place Run Length Encoding Algorithm

string

algorithm

run-length-encoding

要点

简单方法

分析

算法

复杂性

可视化

遗言