题目的主要信息：

第一步：将输入的两个字符串str1和str2进行前后合并
第二步：对合并后的字符串进行排序，要求为：合并后下标为奇数的字符和下标为偶数的字符分别从小到大排序
第三步：对排序后的字符串进行对每一个字符的转换操作。对每个字符所代表的十六进制用二进制表示并倒序，然后再转换回十六进制对应的大写字符（字符 a ~ f 的十六进制对应十进制的10 ~ 15，大写同理），非十六进制的表示字符不变
输出处理后的字符串

方法一：暴力解法

具体做法：

我们按照题目的要求分三步走即可。

第一步：直接将string类型的字符用加号连接在一起。

第二步：遍历连接好的字符串s，用两个空字符串分别记录s奇数位置和偶数位置的字符，然后分别对这两个字符串单独用sort函数排序，排好后再次遍历字符串s，奇数位置偶数位置依次分别添加那两个字符串上的字符。

alt

第三步：遍历字符串对每一个字符进行转换，当然如果是非0-9或者大小写的a-f就不用转换。对于这些十六进制的字符，我们将其转换成数字，然后用长度为4的数组，记录其二进制的各个位的数，采用对数字连除2取余的操作，因为转换为二进制是取余后逆向将余数连接在一起，我们这里正序连接就相当于将二进制反转了。然后又将二进制数转换成十进制数，再将十进制数转换成十六进制的字符。

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;

char change(char ch){
    int num = -1;
    if(ch >= '0' && ch <= '9') //数字
        num = ch - '0';
    else if( (ch >= 'a' && ch <= 'f') || (ch >= 'A' && ch <= 'F')) //字母
        num = tolower(ch) - 'a' + 10; //十六进制字母转为十进制数
    if(num != -1){ //非数字或者字母num还是为-1
        int bit[4];   // 16以内,4位
        for(int i = 0; i < 4; i++){
            bit[i] = num % 2;  // 从下标0开始存，已经反转了
            num /= 2;
        }
         num = bit[0] * 8 + bit[1] * 4 + bit[2] * 2 + bit[3] * 1;  // 这个数的范围是在0-16之间，用16进制表示它
         if(num <= 9 && num >= 0) //转回十六进制数的字符
             ch  =  num + '0';
         else if (num >= 10 && num <= 16)
             ch = num - 10 + 'A';
    }
    return ch;
}

int main(){
    string str1, str2;
    while(cin >> str1 >> str2){
        string s = str1 + str2; //两个字符串前后相连
        string s1, s2; //分别记录奇数位和偶数位字符
        for(int i = 0; i < s.length(); i++){
            if(i % 2 == 0) //奇数位
                s1 += s[i];
            else //偶数位
                s2 += s[i];
        }
        sort(s1.begin(), s1.end()); //奇数位字符排序
        sort(s2.begin(), s2.end()); //偶数位字符排序
        for(int i = 0, j = 0, k = 0; i < s.length(); i++){
            if(i % 2 == 0)
                s[i] = s1[j++]; //排序后添加到奇数位
            else
                s[i] = s2[k++]; //排序后添加到偶数位
        }
        for(int i = 0; i < s.length(); i++) //遍历字符串
            s[i] = change(s[i]);
        cout << s << endl;
    }
    return 0;
}

复杂度分析：

时间复杂度： $O (n l o g_{2} n)$ ，其中 $n$ 为连接后的字符串长度，分成奇数位和偶数位后刚好都是长度 $n / 2$ ，则排序的复杂度都是 $O (n / 2 l o g_{2} (n / 2) = O (n l o g_{2} n)$ ，其他遍历复杂度都为 $O (n)$ ，属于低次幂，函数change的复杂度为 $O (1)$
空间复杂度： $O (n)$ ，多个辅助字符串，长度都是 $O (n)$ 级别

方法二：索引查表

具体做法：

前两步都和方法一一样，没什么好改进的，对于第三步，我们可以查表。

十六进制字符0-9a-fA-Z的二进制反转后回到十六进制字符，我们都可以分别计算，这是有限的，我们就可以列一个表，将二者一一对应，这里我们用两个长度相等的字符串代替。然后我们要做的就是对于字符串s中的每个字符，找到其在表中位置，即在第一个辅助字符串中的位置，对应第二个辅助字符串的位置就是它转换后的值。

怎么找位置，我们还可以用一个索引。我们都知道字符的ASCⅡ码与数字一一对应，其中数字字母最大的对应122，我们可以准备一个123大小的数组，初始置为-1，这样字符就会与下标一一对应，那么我们通过字符可以直接访问数组中的元素，那我们数组中就记录该字母在上表中所在的下标，准备一个这样的索引数组，我们遍历字符串的时候就可以通过数组直接访问转换表的下标，通过下标找到另一个字符串中对应的值就是它要转换的值，而其他字符没有没有准备下标，就都是初始值-1，只要检查-1就会使其他字符不变。

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;

string helpstr1 = "0123456789abcdefABCDEF";
string helpstr2 = "084C2A6E195D3B7F5D3B7F";
int main(){
    string str1, str2;
    while(cin >> str1 >> str2){
        string s = str1 + str2; //两个字符串前后相连
        string s1, s2; //分别记录奇数位和偶数位字符
        for(int i = 0; i < s.length(); i++){
            if(i % 2 == 0) //奇数位
                s1 += s[i];
            else //偶数位
                s2 += s[i];
        }
        sort(s1.begin(), s1.end()); //奇数位字符排序
        sort(s2.begin(), s2.end()); //偶数位字符排序
        for(int i = 0, j = 0, k = 0; i < s.length(); i++){
            if(i % 2 == 0)
                s[i] = s1[j++]; //排序后添加到奇数位
            else
                s[i] = s2[k++]; //排序后添加到偶数位
        }
        vector<int> index(123, -1);
        for(int i = 0; i < helpstr1.length(); i++) //每个字母所在的索引
            index[helpstr1[i]] = i;
        for(int i = 0; i < s.length(); i++){ //遍历字符串
            if(index[s[i]] != -1){ //对于存在索引，不存在索引就是初始值-1
                s[i] = helpstr2[index[s[i]]]; //添加对应的字符
            }
        }
        cout << s << endl;
    }
    return 0;
}

复杂度分析：

时间复杂度： $O (n l o g_{2} n)$ ，其中 $n$ 为连接后的字符串长度，分成奇数位和偶数位后刚好都是长度 $n / 2$ ，则排序的复杂度都是 $O (n / 2 l o g_{2} (n / 2) = O (n l o g_{2} n)$ ，其他遍历复杂度都为 $O (n)$ ，属于低次幂，构建表属于常数时间
空间复杂度： $O (n)$ ，多个辅助字符串，长度都是 $O (n)$ 级别，表字符串及索引都是常数空间

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

题目的主要信息：

方法一：暴力解法

方法二：索引查表