就地行程长度编码算法

Question

我遇到了一个面试问题:

给定输入String : aaaaabcddddee,将其转换为a5b1c1d4e2.

一个额外的约束是,这需要就地完成,意味着不应该使用额外的空间(数组).

保证编码的字符串始终适合原始字符串.换句话说,字符串abcde就不会出现,因为它将被编码为a1b1c1d1e1占用比原始字符串更多的空间.

一个提示采访者给我的是一次遍历字符串并找到保存的空间.

我有时会陷入困境,不使用额外的变量,输入字符串中的某些值可能会被覆盖.

任何建议将不胜感激？

Answer 1

这是一个很好的面试问题.

关键点

有两个关键点:

1. 单个字符必须编码为c1;
2. 编码长度始终小于原始数组.

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

简单的方法

从关键点来看,我们注意到单个字符在编码过程中会给我们带来很多问题,因为它们可能没有足够的位置来保存编码的字符串.那么我们先把它们留下来,先压缩其他角色呢？

例如,我们aaaaabcddddee从后面编码,同时首先留下单个字符,我们将得到:

aaaaabcddddee
_____a5bcd4e2

然后,我们可以安全地从头开始编码部分编码的序列,给定关键点2,以便有足够的空间.

分析

好像我们有一个解决方案,我们完成了吗？不.考虑这个字符串:

aaa3dd11ee4ff666

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

aaa3dd11ee4ff666
__a33d212e24f263

好的,现在告诉我,你如何区分原始字符串中的游程长度？

好吧,我们需要尝试别的东西.

让我们将编码效益(E)定义为:编码序列与原始连续字符序列之间的长度差异..

例如,aahas 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是Encode Benefit第i ^个连续的字符子串.

例如,您在问题中提供的示例: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个空格.

然而,从这个例子中,我们可以看到一个潜在的问题:因为我们正在进行求和,即使最终答案大于0,也可能在中间得到一些负数!

是的,这是一个问题,而且非常严重.如果我们得到E跌倒0,这意味着我们没有足够的空间来编码当前字符,并会覆盖后面的一些字符.

但是,但是,为什么我们需要从第一组中总结出来呢？为什么我们不能从中间的某个地方开始求和以跳过负面部分？我们来看一个例子:

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

如果我们从头开始总结,我们将-1在索引4(从0开始)添加第三个后降到0以下; 如果我们从索引5总结,当我们到达结束时循环回索引0,我们没有问题.

算法

分析让我们对算法有所了解:

1. 从头开始,计算E当前连续组,并加总E_total;
2. 如果E_total仍然是非负(> = 0),我们很好,我们可以安全地进入下一组;
3. 如果E_total跌破0,我们需要从当前位置重新开始,即清除E_total并进入下一个位置.

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

然后我们可以回到起点并开始传统的游程编码,在我们到达结束之后我们需要回到序列的开头来完成第一部分.棘手的部分是,我们需要使用字符串末尾的剩余空格.在那之后,我们需要做一些转移,以防我们有一些订单问题,并删除任何额外的空格,然后我们终于完成:)

因此,我们有一个解决方案(代码只是一个伪,尚未经过验证):

// 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个部分:

1. 找到出发地: O(n)
2. 整个字符串的运行长度编码: O(n)
3. 消除白色空间: O(n)
4. 到位字符串旋转: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

最后的话

这个问题并不简单,实际上自然地将几个传统的编码面试问题粘在一起.建议的思维流程将是:

1. 观察模式并找出关键点;
2. 认识到空间不足的原因是因为编码单个字符;
3. 量化每个连续字符组的编码的好处/成本(aka 编码好处);
4. 使用你提出的量化来解释原始陈述;
5. 弄清楚算法找到一个好的起点;
6. 弄清楚如何以良好的起点进行游程编码;
7. 意识到你需要旋转编码的字符串并消除空白区域;
8. 找出算法做到位旋转;
9. 弄清楚算法做到位空白消除.

说实话,对于一个受访者来说,在短时间内提出一个可靠的算法是有点挑战性的,所以你的分析流程真的很重要.不要说什么,表明你的思维流,这有助于面试官找到你现在的舞台.