题目描述
详细描述：
将输入的两个字符串合并。
对合并后的字符串进行排序，要求为：下标为奇数的字符和下标为偶数的字符分别从小到大排序。这里的下标意思是字符在字符串中的位置。
对排序后的字符串进行操作，如果字符为‘0’——‘9’或者‘A’——‘F’或者‘a’——‘f’，则对他们所代表的16进制的数进行BIT倒序的操作，并转换为相应的大写字符。如字符为‘4’，为0100b，则翻转后为0010b，也就是2。转换后的字符为‘2’； 如字符为‘7’，为0111b，则翻转后为1110b，也就是e。转换后的字符为大写‘E’。
举例：输入str1为"dec"，str2为"fab"，合并为“decfab”，分别对“dca”和“efb”进行排序，排序后为“abcedf”，转换后为“5D37BF”
接口设计及说明：
/*
功能:字符串处理
输入:两个字符串,需要异常处理
输出:合并处理后的字符串，具体要求参考文档
返回:无
*/
void ProcessString(char* str1,char *str2,char * strOutput)
{
}
输入描述:
输入两个字符串
输出描述:
输出转化后的结果
示例1
输入
dec fab
输出
5D37BF
思路
常规想法就是创建2个数组，把索引为奇数的放到一起，索引偶数放到的一起，然后对这两数组分别排序，再合并起来。
然后对合并后的字符串的每一个字符求二进制位，并求出倒序的值，再转换成对应的十六进制。
代码
方法一
第一次优化，我们采用步长为2的排序来直接对字符串排序，无须创建辅助的2个数组。所以我们可以采用步长为2的冒泡，插入，选择等等。但是这样就必须对字符串进行2次排序，第一次排序的初始值为0，第二次排序的初始值为1。还能优化吗，当然可以，希尔排序！直接进行一次步长为2的希尔排序就可以解决问题。
package com.special.improve;
import java.util.Scanner;
/**
*
* @author special
* @date 2017年9月27日 下午6:16:46
*/
public class Pro29Improve1 {
/**
* 数组元素交换
* @param ch
* @param i
* @param j
*/
private static void swap(char[] ch, int i, int j){
char temp = ch[i];
ch[i] = ch[j];
ch[j] = temp;
}
/**
* 希尔排序，其实就是步长为2的插入排序
* @param ch
* @param step
*/
private static void shell(char[] ch, int step){
int length = ch.length;
/**
* 注意i的初始值，i的增长
* 注意j的初始值，为什么j取i,而不是i + 1呢？
* 1.因为i的判断条件确保了他不会越界，所以我们j取i值一定不会越界
* 2.如果我们j取i+1,我们就会错过i的正确排序！
* 同时注意j的判断条件和步长
* j>=step 是为了防止数组下界越界！
*/
for(int i = step; i < length; i++){
for(int j = i; j >= step; j -= step){
if(ch[j] < ch[j - step]) swap(ch,j,j - step);
}
}
}
/**
* 插入排序的另一个版本，可以减少交换的次数
* 但要注意i，j的取值，同时注意内循环比较的条件！
* @param ch
* @param step
*/
private static void improveShell(char[] ch, int step){
int length = ch.length;
for(int i = step; i < length; i++){
char temp = ch[i];
int j = i - step;
for(; j >= 0; j -= step){
if(ch[j] > temp) ch[j + step] = ch[j];
else break;
}
ch[j + step] = temp;
}
}
/**
* 对单个字符进行处理
* @param ch
* @return
*/
private static char solve(char ch){
StringBuilder binary = new StringBuilder();
int result = 0;
if(ch >= '0' && ch <= '9')
result = ch - '0';
else if(ch >= 'A' && ch <= 'F')
result = ch - 'A' + 10;
else if(ch >= 'a' && ch<= 'f')
result = ch - 'a' + 10;
else
return ch;
while(result != 0){
int temp = result & 1;
binary.append(temp);
result >>= 1;
}
binary.append("0000");
String binaryStr = binary.substring(0, 4);
int ans = 0;
for(int i = 0; i < 4; i++)
ans = ans * 2 + (binaryStr.charAt(i) - '0');
if(ans >= 10)
ch = (char) ('A' + (ans - 10));
else
ch = (char) ('0' + (ans - 0));
return ch;
}
public static String ProcessString(String str1,String str2){
String mergeString = str1 + str2;
int length = mergeString.length();
char[] mergeArr = mergeString.toCharArray();
improveShell(mergeArr,2);
System.out.println(mergeArr);
for(int i = 0; i < length; i++){
mergeArr[i] = solve(mergeArr[i]);
}
return new String(mergeArr);
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
while(input.hasNext()){
String str1 = input.next();
String str2 = input.next();
String result = ProcessString(str1,str2);
System.out.println(result);
}
}
}
方法二
继续优化！既然考察的字符这么少，为何不打表，利用映射呢！也就是我们暴力枚举出所有的情况，利用2个平行的数组来模拟字符表，这样先在第一个数组中找到相应的索引，然后在第二数组中利用以上得出的索引找到变换的值。
package com.special.improve;
import java.util.Scanner;
/**
* 利用映射表啊！！字符转换首先应该想到的
* 同时利用希尔排序
* @author special
* @date 2017年9月27日 下午6:58:41
*/
public class Pro29Improve2 {
private static final String charTable = "0123456789ABCDEFabcdef";
private static final String mapCharTable = "084C2A6E195D3B7F5D3B7F";
/**
* 数组元素交换
* @param ch
* @param i
* @param j
*/
private static void swap(char[] ch, int i, int j){
char temp = ch[i];
ch[i] = ch[j];
ch[j] = temp;
}
/**
* 希尔排序，其实就是步长为2的插入排序
* @param ch
* @param step
*/
private static void shell(char[] ch, int step){
int length = ch.length;
/**
* 注意i的初始值，i的增长
* 注意j的初始值，为什么j取i,而不是i + 1呢？
* 1.因为i的判断条件确保了他不会越界，所以我们j取i值一定不会越界
* 2.如果我们j取i+1,我们就会错过i的正确排序！
* 同时注意j的判断条件和步长
* j>=step 是为了防止数组下界越界！
*/
for(int i = step; i < length; i++){
for(int j = i; j >= step; j -= step){
if(ch[j] < ch[j - step]) swap(ch,j,j - step);
}
}
}
/**
* 插入排序的另一个版本，可以减少交换的次数
* 但要注意i，j的取值，同时注意内循环比较的条件！
* @param ch
* @param step
*/
private static void improveShell(char[] ch, int step){
int length = ch.length;
for(int i = step; i < length; i++){
char temp = ch[i];
int j = i - step;
for(; j >= 0; j -= step){
if(ch[j] > temp) ch[j + step] = ch[j];
else break;
}
ch[j + step] = temp;
}
}
public static String ProcessString(String str1,String str2){
String mergeString = str1 + str2;
int length = mergeString.length();
char[] mergeArr = mergeString.toCharArray();
shell(mergeArr,2);
/**
* 字符转换常用的方法，利用映射表
*/
for(int i = 0; i < length; i++){
int index = charTable.indexOf(mergeArr[i]);
if(index != -1)
mergeArr[i] = mapCharTable.charAt(index);
}
return new String(mergeArr);
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
while(input.hasNext()){
String str1 = input.next();
String str2 = input.next();
String result = ProcessString(str1,str2);
System.out.println(result);
}
}
}
