就地行程长度编码算法

问题描述 投票：2回答：3

我遇到了一个面试问题：

给定输入字符串：aaaaabcddddee，将其转换为a5b1c1d4e2。

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

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

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

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

任何建议将不胜感激？

string algorithm run-length-encoding
3个回答
8
投票

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

关键点

有两个关键点：

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

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

简单的方法

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

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

aaaaabcddddee
_____a5bcd4e2

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

分析

好像我们有一个解决方案，我们完成了吗？不。考虑这个字符串：

aaa3dd11ee4ff666

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

aaa3dd11ee4ff666
__a33d212e24f263

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

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

让我们将编码效益（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。

例如，您在问题中的样本：qazxsw poi，可以分为5个部分：

aaaaabcddddee

西格玛将是：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个空格。

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

是的，这是一个问题，而且非常严重。如果我们得到3 + (-1) + (-1) + 2 + 0 = 3 > 0低于E，这意味着我们没有足够的空间来编码当前字符并将覆盖它后面的一些字符。

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

0

如果我们从头开始总结，我们将在指数4（基于0）的基础上添加第三个2 0 -1 -1 -1 1 3 -1 后降至0以下;如果我们从索引5总结，当我们到达结束时循环回索引0，我们没有问题。

算法

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

  1. 从头开始，计算当前连续组的-1，并添加到总E;
  2. 如果E_total仍然是非负的（> = 0），我们很好，我们可以安全地进入下一组;
  3. 如果E_total低于0，我们需要从当前位置重新开始，即清除E_total并继续前进到下一个位置。

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

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

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

O(n)

复杂

我们在算法中有4个部分：

  1. 找到出发地：// 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);
  2. 整个字符串的运行长度编码：O(n)
  3. 白色空间消除：O(n)
  4. O(n)：In place string rotation

因此我们总共有O(n)。

可视化

假设我们需要对这个字符串进行编码：O(n)

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

abccdddefggggghhhhh

所以起始位置将是9：

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;

最后的话

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

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

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

0
投票

也许只是正常编码，但如果你看到输出索引超过输入索引，只需跳过“1”。然后当你完成后退并在没有计数的所有字母后面插入1时，将其余的字符串移回。在最坏的情况下是O（N ^ 2）（没有重复的字母），所以我假设可能有更好的解决方案。

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

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

0
投票

O（n）并到位

  1. set var = 0;
  2. 从1长度循环并找到第一个不匹配的字符。
  3. 计数将是两个字符的索引的差异。

让我们来看一个例子

         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

给s添加一个虚拟字母

s = "wwwwaaadexxxxxxywww"

现在我们的字符串变成

s = s + '#'

我们稍后会回到这一步。

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

s = "wwwwaaadexxxxxxywww#"

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

j = 0 // s[j] = w

我成为下一个不匹配的角色，这将是'd'

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

Output: w4

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

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

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

这是一个C ++实现

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

输出：w4a3d1e1x6y1w3

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.