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

字符串合并处理

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

题意：

按照如下规则操作：

方法一：

模拟

思路：

      直接模拟。

      第一步：直接合并字符串；

      第二步：分别对下标为奇数的字符和下标为偶数的字符分别从小到大排序；

      第三步：对排序后的字符串中的'0'~'9'、'A'~'F'和'a'~'f'字符进行操作：

                                                                                      先将字符表示为二进制串，再逆向二进制串转化为对应的十六进制大写字符。

#include <bits/stdc++.h>

using namespace std;

int main(){
 
    string s1,s2,s;
    while(cin >> s1 >> s2){
        string a="",b="";
        s=s1+s2;//字符串合并
        int len=s.size();
        for(int i=0;i<len;i++){
            if(i%2==0)
                a+=s[i];
            else
                b+=s[i];
        }
        sort(a.begin(),a.end());//下标为偶数的字符排序
        sort(b.begin(),b.end());//下标为奇数的字符排序
        int j=0;
        for(int i=0;i<len;i++){
            if(i%2==0)
                s[i]=a[j];
            else
                s[i]=b[j++];
        }
//         cout << s << endl;
        for(int i=0;i<len;i++){
            
            if(isdigit(s[i])||(s[i]>='a'&&s[i]<='f')||(s[i]>='A'&&s[i]<='F')){//字符转换
                string c="";
                if(s[i]>='a')//字母统一转为大写字母
                    s[i]-=32;
                int num;
                if(isalpha(s[i]))//如果是字母
                    num=s[i]-'A'+10;
                else//如果是数字
                    num=s[i]-'0';
                string x="";
                while(num){//转为二进制形式
                    x+=num%2+'0';
                    num/=2;
                }
                while(x.size()<4){
                    x+='0';
                }
                int y=0;
                for(int i=0;i<x.size();i++){//逆向运算
                    y=y*2+x[i]-'0';
                }
                if(y>9)
                    s[i]='A'+y-10;
                else
                    s[i]=y+'0';
               
            }
        }
        cout << s << endl;
    }
    return 0;
    
}

时间复杂度： $O(n*logn),快排的时间复杂度。$

空间复杂度： $O(n),n是输入字符串的长度，存储下标为奇数的字符和下标为偶数的字符分别从小到大排序。$

方法二：

map排序

思路：

利用map的有序性，可以实现排序的功能。

构造两个map,分别对下标为奇数的字符和下标为偶数的字符分别从小到大排序。

最后遍历每个字符进行同方法一一样的操作。

#include <bits/stdc++.h>

using namespace std;

int main(){
 
    string s1,s2,s;
    while(cin >> s1 >> s2){
        map<pair<char,int>,int> m1;
        map<pair<char,int>,int> m2;
        string a="",b="";
        s=s1+s2;//字符串合并
        int len=s.size();
        for(int i=0;i<len;i++){
            if(i%2==0)
                m1[{s[i],i}]=1;//下标为偶数的字符排序
            else
                m2[{s[i],i}]=1;//下标为奇数的字符排序
        }
        map<pair<char,int>,int>::iterator it1=m1.begin();
        map<pair<char,int>,int>::iterator it2=m2.begin();
        for(int i=0;i<len;i++){
            if(i%2==0)
                s[i]=it1->first.first,it1++;
            else
                s[i]=it2->first.first,it2++;
        }
//         cout << s << endl;
        for(int i=0;i<len;i++){
            
            if(isdigit(s[i])||(s[i]>='a'&&s[i]<='f')||(s[i]>='A'&&s[i]<='F')){//字符转换
                string c="";
                if(s[i]>='a')//字母统一转为大写字母
                    s[i]-=32;
                int num;
                if(isalpha(s[i]))//如果是字母
                    num=s[i]-'A'+10;
                else//如果是数字
                    num=s[i]-'0';
                string x="";
                while(num){//转为二进制形式
                    x+=num%2+'0';
                    num/=2;
                }
                while(x.size()<4){
                    x+='0';
                }
                int y=0;
                for(int i=0;i<x.size();i++){//逆向运算
                    y=y*2+x[i]-'0';
                }
                if(y>9)
                    s[i]='A'+y-10;
                else
                    s[i]=y+'0';
               
            }
        }
        cout << s << endl;
    }
    return 0;
    
}