字符串合并处理（二进制位的倒序）

我会带着你远行 2022-08-05 12:06 183阅读 0赞

<table> 
 <tbody> 
 <tr> 
 <td>描述:&nbsp;</td> 
 <td> 按照指定规则对输入的字符串进行处理。 详细描述： 将输入的两个字符串合并。 对合并后的字符串进行排序，要求为：下标为奇数的字符和下标为偶数的字符分别从小到大排序。这里的下标意思是字符在字符串中的位置。 对排训后的字符串进行操作，如果字符为‘0’——‘9’或者‘A’——‘F’或者‘a’——‘f’，则对他们所代表的16进制的数进行BIT倒序的操作，并转换为相应的大写字符。如字符为‘4’，为0100b，则翻转后为0010b，也就是2。转换后的字符为‘2’；&nbsp;如字符为‘7’，为0111b，则翻转后为1110b，也就是e。转换后的字符为大写‘E’。 &nbsp; 举例：输入str1为"dec"，str2为"fab"，合并为“decfab”，分别对“dca”和“efb”进行排序，排序后为“abcedf”，转换后为“5D37BF” 接口设计及说明： /* 功能:字符串处理 输入:两个字符串,需要异常处理 输出:合并处理后的字符串，具体要求参考文档 返回:无 */ void&nbsp;ProcessString(char*&nbsp;str1,char&nbsp;*str2,char&nbsp;*&nbsp;strOutput) { } &nbsp; &nbsp; &nbsp;</td> 
 </tr> 
 <tr> 
 <td>知识点:</td> 
 <td>&nbsp;字符串,排序,位运算&nbsp;</td> 
 </tr> 
 <tr> 
 <td>题目来源:</td> 
 <td>&nbsp;内部整理&nbsp;</td> 
 </tr> 
 <tr> 
 <td>练习阶段:</td> 
 <td>&nbsp;中级&nbsp;</td> 
 </tr> 
 <tr> 
 <td>运行时间限制:</td> 
 <td>10Sec</td> 
 </tr> 
 <tr> 
 <td>内存限制:</td> 
 <td>128MByte</td> 
 </tr> 
 <tr> 
 <td>输入:</td> 
 <td>&nbsp; 输入两个字符串 &nbsp;</td> 
 </tr> 
 <tr> 
 <td>输出:</td> 
 <td>&nbsp; 输出转化后的结果 &nbsp;</td> 
 </tr> 
 <tr> 
 <td>样例输入:</td> 
 <td> <pre>dec fab

</pre> </td> 
 </tr> 
 <tr> 
 <td>样例输出:</td> 
 <td> <pre>5D37BF

</pre> </td> 
 </tr> 
 </tbody> 
</table>

**关于二进制位的翻转问题参考：[二进制位的翻转][Link 1]**

根据“二进制位翻转”这篇文章可以得到如下 程序将要使用的、对4位二进制位的翻转，可以如下处理：

int main() {
 	unsigned int n;
 	cin >> n;
 	n = n & 0xf;
 	cout << hex << n << endl;
 	n = ((n & 0x5) << 1) | ((n & 0xa) >> 1);
 	n = ((n & 0x3) << 2) | ((n & 0xc) >> 2);
 	cout << n << endl;
 }

上面的程序将形如“1011”的二进制位序列翻转为“1101”。

解题如下：

#include <string>
 //#include <algorithm>
 #include <iostream>
 //#include <string.h>
 //#include <vector>
 //#include <cmath>
 #include <sstream>
 using namespace std;
 
 
 //变形的快排，对字符串分别排序其奇数下标字符、偶数下标字母
 int PartQuickSort(string &str, int pos1, int pos2) {
 		char pivot = str[pos1];
 		int low = pos1, high = pos2;
 		while (high - low > 1) {
 			while (high - low > 1 && str[high] >= pivot)
 				high -= 2;
 			str[low] = str[high];
 			while (high - low > 1&& str[low] <= pivot)
 				low += 2;
 			str[high] = str[low];
 		}
 		str[low] = pivot;
 		return low;
 }
 
 void QuickSort(string &str, int pos1, int pos2) {
 	if (pos2 - pos1 > 1) {
 		int part = PartQuickSort(str, pos1, pos2);
 		QuickSort(str, pos1, part - 2);
 		QuickSort(str, part + 2, pos2);
 	}
 }
 
 //按照题目要求对特定字符翻转其二进制位
 void process_str(string &str) {
 	char ch1, ch2 = 0;
 	bool flag = true;
 	int i;
 	for (i = 0; i < str.size(); i++) {
 		flag = true;
 		if (str[i] >= '0' && str[i] <= '9')
 			ch1 = str[i] - '0';
 		else if (str[i] >= 'a' && str[i] <= 'f')
 			ch1 = str[i] - 'a' + 10;
 		else if (str[i] >= 'A' && str[i] <= 'F')
 			ch1 = str[i] - 'A' + 10;
 		else
 			flag = false;
 		if (flag) {
 			//本题要注意这里将二进制位翻转的做法。
 			//例如11的二进制为1011，翻转后为1101
 			ch2 = 0;
 			ch2 |= (ch1 & (1 << 0)) << 3;
 			ch2 |= (ch1 & (1 << 1)) << 1;
 			ch2 |= (ch1 & (1 << 2)) >> 1;
 			ch2 |= (ch1 & (1 << 3)) >> 3;
 			if (ch2 < 10) {
 				str[i] = '0' + ch2;
 				//cout << str[i] << endl;
 			}
 			else {
 				str[i] = 'A' + ch2 - 10;
 				//cout << str[i] << endl;
 			}
 		}
 	}
 }
 
 int main() {
 	string str, str1, str2;
 	getline(cin, str);
 	stringstream stream(str);
 	stream >> str1 >> str2;
 	str1 += str2;
 	str2 = str1;
 
 	//分别对字符串的偶数下标、奇数下标排序
 	if (str1.size() % 2 != 0) {
 		QuickSort(str1, 0, str1.size() - 1);
 		QuickSort(str1, 1, str1.size() - 2);
 	}
 	else {
 		QuickSort(str1, 0, str1.size() - 2);
 		QuickSort(str1, 1, str1.size() - 1);
 	}
 
 	process_str(str1);
 	cout << str1 << endl;
 }

![Center][]

[Link 1]: http://blog.csdn.net/u013074465/article/details/45485959
[Center]: /images/20220805/0f4863c67eee458889c5ee63f0e8ee5c.png