字符串编码解码

    
        标签：
        
            笔试算法题
        
    发布于：2022-03-19 13:10:30
    编辑于：2022-03-22 21:43:31
    浏览量：914

概述

记源字符串为 s，编码后的结果为 t。

编码规则：每次取 s 中间的值（n/2 上取整）作为 t 的第一个值，t 的剩余值为取出中间的值后的 s 的编码结果。

解码规则：需要自己推。

解法

我们拿 abcdef 试一下就能发现规律了：

abcdef 
c abdef
cd abef
cdb aef
cdbe af
cdbea f
cdbeaf

显然，解码时从 t 后面取出一个字符，放入当前 s 的中间。

#include <bits/stdc++.h>

using namespace std;

string encode(string &s) {
    if (s.empty()) return "";
    double n = s.size();
    int i = ceil(n / 2) - 1;
    string t(1, s[i]);
    string newS = s.substr(0, i) + s.substr(i + 1);
    t += encode(newS);
    return t;
}

string decode(string &t, string &s) {
    if (t.empty()) return s;
    char c = t.back();
    t.pop_back();
    int i = s.size() / 2;
    string newS = s.substr(0, i) + string(1, c) + s.substr(i);
    s = newS;
    decode(t, s);
    return s;
}


int main() {
    int n, t;
    cin >> n >> t;
    string s;
    cin >> s;
    if (t == 1) {
        cout << encode(s);
    } else {
        string tmp = "";
        cout << decode(s, tmp);
    }
}

Links: 字符串编码解码