字符串编码解码

Tag: 笔试算法题 Posted on 2022-03-19 13:10:30 Edited on 2022-03-22 21:43:31 Views: 168

概述

记源字符串为 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);
    }
}

未经允许,禁止转载,本文源站链接:https://iamazing.cn/