题目的主要信息：

本题是需要将两个字符串进行合并，合并之后还需要进行一些变换。具体要求如下：

第一步：将输入的两个字符串str1和str2进行前后合并。
第二步：对合并后的字符串按照奇偶位进行排序。
第三步：对排序后的字符串中的'0'-'9'、'A'-'F'和'a'-'f'字符，进行转换操作。

方法一：

首先从输入的字符串中按照奇偶位置存下对应的奇数串和偶数串，分别对这两串字符串用sort函数进行排序，排序后按照奇偶位置重新合并成新的字符串，最后遍历字符串，对字符逐个转换。字符转换采用查表法，先预先构造了两个字符串strlist1和strlist2，分别存储转换前和转换后的字符，每次转换时，先在strlist1中找到相应的位置strlist[i]，转换后的字符即为strlist2[i]。 alt

具体做法：

#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

const string strlist1 = "0123456789abcdefABCDEF";//转换前的字符list
const string strlist2 = "084C2A6E195D3B7F5D3B7F";//转换后的字符list

int main(){
    string str1, str2;
    while(cin>>str1>>str2){
        string str, s1, s2;
        str = str1 + str2;
        for(int i=0;i<str.size();++i){
            if(i % 2 == 0)
                s1 += str[i];//偶数位的字符
            else
                s2 += str[i];//奇数位的字符
        }
        sort(s1.begin(), s1.end());//偶数位字符排序
        sort(s2.begin(), s2.end());//奇数位字符排序
        string str_sorted;
        int j=0;
        int k=0;
        for(int i=0;i<(s1.size()+s2.size());i++){//将s1、s2中的字符重新放回s中
            if(i % 2 == 0)
                str_sorted += s1[j++];
            else 
                str_sorted += s2[k++];
        }
        for(int i=0;i<str_sorted.size();i++){//遍历字符串对字符进行转换
            for(int j=0;j<strlist1.size();j++){//在strlist1中找到位置
                if(strlist1[j]==str_sorted[i]){//替换为strlist2中相同位置的字符
                    str_sorted[i] = strlist2[j];
                    break;
                }
            }
        }
        cout<<str_sorted<<endl;
    }
    return 0;
}

复杂度分析：

时间复杂度： $O (n l o g_{2} n)$ ，for循环的时间复杂度为 $O (n)$ ，sort排序的时间复杂度为 $O (n l o g_{2} n)$ 。
空间复杂度： $O (n)$ ，用了str和str_sorted来储存字符串。

方法二：

方法二的整体思路和方法一相同，唯一区别在于方法二的字符转换是用ASCII码进行转换的，transform函数记录了转换的步骤。首先将A-F，a-f，0-9转换为十进制中的含义，其余字符无需转换直接返回；第二步进行二进制翻转，计算翻转后代表的十进制的含义，如果大于10则要用A-F表示，若小于10，则直接用数字币表示。二进制翻转转换为10进制只需要从低位开始乘8、乘4，乘2，乘1。

具体做法：

#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

char transform(char ch)
{
    int ascii;
    //先转换为十进制的含义
    if(ch>='A'&&ch<='F'){
        ascii=ch-'A'+10;
    }else if(ch>='a'&&ch<='f'){
        ascii=ch-'a'+10;
    }else if(isdigit(ch)){
        ascii=ch-'0';
    }else return ch;//其他字符无需转换
    int res=0;
    int temp=8;
    while(ascii){//计算翻转后转换成的十进制
        res+=(ascii%2)*temp;
        ascii=ascii/2;
        temp=temp/2;
    }
    if(res>=10){
        return res-10+'A';//将超过10的字符转换为十进制的字母
    }else{
        return res+'0';
    }
}
int main(){
    string str1, str2;
    while(cin>>str1>>str2){
        string str, s1, s2;
        str = str1 + str2;
        for(int i=0;i<str.size();++i){
            if(i % 2 == 0)
                s1 += str[i];//偶数位的字符
            else
                s2 += str[i];//奇数位的字符
        }
        sort(s1.begin(), s1.end());//偶数位字符排序
        sort(s2.begin(), s2.end());//奇数位字符排序
        string str_sorted;
        int j=0;
        int k=0;
        for(int i=0;i<(s1.size()+s2.size());i++){//将s1、s2中的字符重新放回s中
            if(i % 2 == 0)
                str_sorted += s1[j++];
            else 
                str_sorted += s2[k++];
        }
        for(int i=0;i<str_sorted.size();i++){//遍历字符串对字符进行转换
            str_sorted[i]=transform(str_sorted[i]);
        }
        cout<<str_sorted<<endl;
    }
    return 0;
}

复杂度分析：

时间复杂度： $O (n l o g_{2} n)$ ，for循环的时间复杂度为 $O (n)$ ，sort排序的时间复杂度为 $O (n l o g_{2} n)$ 。
空间复杂度： $O (1)$ ，只用了常数空间。

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

题目的主要信息：

方法一：

方法二：