2

我遇到了一个面试问题：

给定一个输入 String: aaaaabcddddee，将其转换为a5b1c1d4e2.

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

保证编码的字符串总是适合原始字符串。换句话说，abcde不会出现类似字符串的情况，因为它将被编码为a1b1c1d1e1比原始字符串占用更多空间。

面试官给我的一个提示是遍历字符串一次并找到节省的空间。

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

任何建议将不胜感激？

4

4 回答 4

9

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

关键点

有2个关键点：

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

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

简单的方法

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

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

aaaaabcddddee
_____a5bcd4e2

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

分析

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

aaa3dd11ee4ff666

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

aaa3dd11ee4ff666
__a33d212e24f263

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

好吧，我们需要尝试其他方法。

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

例如aahas E = 0, sinceaa将被编码为a2，并且它们没有长度差异；aaa有E = 1，因为它将被编码为a3，并且编码和原始之间的长度差是1。让我们看一下单个字符的情况，它是什么E？是的，它是-1。E根据定义，我们可以推导出:的公式E = ori_len - encoded_len。

现在让我们回到问题上来。从关键点 2，我们知道编码的字符串总是比原始字符串短。我们如何用它E来重新表述这个关键点？

很简单：sigma(E_i) >= 0，E_i第Encode Benefiti个连续字符子串的第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. 量化每个连续字符组的编码收益/成本（又名编码收益）；
  4. 使用您提出的量化来解释原始陈述；
  5. 找出算法找到一个好的起点；
  6. 找出如何以良好的起点进行行程编码；
  7. 意识到您需要旋转编码的字符串并消除空格；
  8. 找出进行就地字符串旋转的算法；
  9. 找出算法来进行适当的空白消除。

老实说，对于一个被采访者来说，在短时间内想出一个可靠的算法有点挑战性，所以你的分析流程真的很重要。什么都不说，展示你的思维导图，这有助于面试官了解你目前的阶段。

于 2016-04-10T11:02:48.893 回答
0

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

#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

于 2020-08-15T06:54:38.060 回答
0

O(n) 并且就地

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

让我们通过一个例子

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

于 2019-04-29T07:33:40.097 回答
0

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

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

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

于 2016-04-10T10:32:38.737 回答