题解 | #字符串合并处理#

字符串合并处理

http://www.nowcoder.com/practice/d3d8e23870584782b3dd48f26cb39c8f

题意

给两个字符串

拼接它们
对拼接后的奇数位排序，偶数位排序
对十六进制0~F以内的，按照二进制4位表示并颠倒，再转换成十六进制表示，转换后使用大写字母。其它字符不变

方法

利用ASCII运算

我们对于上面三个步骤分别如下处理

直接string相加合并
拆成两个 vector<char>数组，分别sort排序
利用ASCII转换

考虑第三步转换

注意到，数字，小写字母，大写字母，分别在ASCII上连续，同时C++中的char直接参与加减运算时，会以其ascii的值为准

alt

那么我们可以利用这个性质，分别对数字，小写字母，大写字母，编写转换逻辑

对于数字，减去字符'0'
对于小写字母，减去字符'a'再加10
对于大写字母，减去字符'A'再加10

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<(b);i++)

// 字符串转换
char trans(char ch){
    int c;
    if('0' <= ch && ch <= '9'){ // 数字
        c = ch-'0';
    }else if('a' <= ch && ch <= 'f'){ // 可以表示成4位16进制的范围
        c = ch-'a'+10;
    }else if('A' <= ch && ch <= 'F'){ // 可以表示成4位16进制的范围
        c = ch-'A'+10;
    }else{
        return ch; // 其它不变
    }
    // 2进制 翻转
    int newc = 0;
    rep(i,0,4){
        newc*=2;
        newc+=c%2;
        c/=2;
    }
    if(newc < 10){
        return newc+'0';
    }
    return newc-10+'A';
}

int main(){
    string s0,s1;
    while(cin>>s0){
        cin>>s1;
        s0+=s1; // 拼接
        vector<char> s[2] = {{},{}}; // 奇偶分离
        rep(i,0,s0.size()){
            s[i%2].push_back(s0[i]);
        }
        rep(i,0,2){
            sort(s[i].begin(),s[i].end()); // 分别排序
        }
        rep(i,0,s0.size()){
            printf("%c",trans(s[i%2][i/2])); // 输出
        }
        printf("\n");
    }
    return 0;
}

复杂度分析

设两个字符串总长度 $O (n)$

时间复杂度: 对于读入，合并和分离奇偶部分是 $O (n)$ ，排序部分时间复杂度为 $O (n l o g (n))$ , 对于转化每个字符是常数时间复杂度，对于转换结果输出是 $O (n)$

空间复杂度: 本身读入的字符串和拼接，排序的vector都是和字符总长度相关，所以空间复杂度为 $O (n)$

内置函数增加可读

像是c++提供isxdigit函数来判断是否是十六进制字符，sscanf,sprintf 来完成十六进制的读入输出

这样可以简化手动通过ASCII转化的编写，同时增加可读性

alt

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<(b);i++)

// 字符串转换
char trans(char ch){
    char chstr[] ={0,0};
    chstr[0] = ch;
    int c;
    if(isxdigit(ch)){ // 十六进制字符
      sscanf(chstr,"%X",&c); // 读入
    }else{
        return ch; // 其它不变
    }
    // 2进制 翻转
    int newc = 0;
    rep(i,0,4){
        newc*=2;
        newc+=c%2;
        c/=2;
    }
    sprintf(chstr, "%X", newc); // 输出
    return chstr[0];
}

int main(){
    string s0,s1;
    while(cin>>s0){
        cin>>s1;
        s0+=s1; // 拼接
        vector<char> s[2] = {{},{}}; // 奇偶分离
        rep(i,0,s0.size()){
            s[i%2].push_back(s0[i]);
        }
        rep(i,0,2){
            sort(s[i].begin(),s[i].end()); // 分别排序
        }
        rep(i,0,s0.size()){
            printf("%c",trans(s[i%2][i/2])); // 输出
        }
        printf("\n");
    }
    return 0;
}