字符串合并处理

朴灿烈づ我的快乐病毒、 2023-07-02 12:24 9阅读 0赞

[https://www.nowcoder.com/practice/d3d8e23870584782b3dd48f26cb39c8f?tpId=37&tqId=21253&tPage=2&rp=&ru=%2Fta%2Fhuawei&qru=%2Fta%2Fhuawei%2Fquestion-ranking][https_www.nowcoder.com_practice_d3d8e23870584782b3dd48f26cb39c8f_tpId_37_tqId_21253_tPage_2_rp_ru_2Fta_2Fhuawei_qru_2Fta_2Fhuawei_2Fquestion-ranking]

**目录**

一、题目描述

二、代码实现

1、使用查表法实现十六进制字符的逆转

2、不使用额外存储空间实现十六进制字符的逆转

3、采用希尔排序实现排序算法

--------------------

## 一、题目描述 ##

按照指定规则对输入的字符串进行处理。

**详细描述**：

将输入的两个字符串合并。

对合并后的字符串进行排序，要求为：下标为奇数的字符和下标为偶数的字符分别从小到大排序。这里的下标意思是字符在字符串中的位置。

对排序后的字符串进行操作，如果字符为‘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”

## 二、代码实现 ##

### 1、使用查表法实现十六进制字符的逆转 ###

使用Map存储映射关系

import java.util.Scanner;
    import java.util.HashMap;
    import java.util.Arrays;
    public class Main {
        public static HashMap<Character,Character> map = null;
        public static void main(String[] args) {
            map = new HashMap<Character,Character>(){
       {
                put('0', '0');
                put('1', '8');
                put('2', '4');
                put('3', 'C');
                put('4', '2');
                put('5', 'A');
                put('6', '6');
                put('7', 'E');
                put('8', '1');
                put('9', '9');
                put('a', '5');
                put('b', 'D');
                put('c', '3');
                put('d', 'B');
                put('e', '7');
                put('f', 'F');
                put('A', '5');
                put('B', 'D');
                put('C', '3');
                put('D', 'B');
                put('E', '7');
                put('F', 'F');
            }};
            Scanner sc = new Scanner(System.in);
            
            while (sc.hasNext()) {
                String str1 = sc.next();
                String str2 = sc.next();
                String str = str1 + str2;
                String result = processString(str);
                System.out.println(result);
            }
        }
        
        public static String processString(String str) {
            StringBuilder sb1 = new StringBuilder();
            StringBuilder sb2 = new StringBuilder();
            for (int i=0; i<str.length(); i++) {
                if ((i & 1) == 0) {
                    sb1.append(str.charAt(i));
                } else {
                    sb2.append(str.charAt(i));
                }
            }
            
            String str1 = sort(sb1.toString());
            String str2 = sort(sb2.toString());
            
            StringBuilder sb3 = new StringBuilder();
            int i = 0, j = 0;
            while (j < str2.length()) {
                char ch1 = str1.charAt(i);
                char ch2 = str2.charAt(j);
                
                if ((ch1>='0' && ch1<='9') || (ch1>='A' && ch1<='F') || (ch1>='a' && ch1<='f')) {
                    sb3.append(map.get(ch1));
                } else {
                    sb3.append(ch1);
                }
                if ((ch2>='0' && ch2<='9') || (ch2>='A' && ch2<='F') || (ch2>='a' && ch2<='f')) {
                    sb3.append(map.get(ch2));
                } else {
                    sb3.append(ch2);
                }
                
                //
                //sb3.append(map.getOrDefault(ch1));
                //sb3.append(map.getOrDefault(ch2));
                //error: no suitable method found for getOrDefault(char)
                //
                //sb3.append(map.getOrDefault(Character.valueOf(ch1)));
                //sb3.append(map.getOrDefault(Character.valueOf(ch2)));
                //
                //sb3.append(map.getOrDefault((Character)ch1));
                //sb3.append(map.getOrDefault((Character)ch2));
                //
                //sb3.append(map.getOrDefault(new Character(ch1)));
                //sb3.append(map.getOrDefault(new Character(ch2)));
                //error: no suitable method found for getOrDefault(Character)
                //method Map.getOrDefault(Object,Character) is not applicable
                //
                //sb3.append(map.getOrDefault((Object)ch1));
                //sb3.append(map.getOrDefault((Object)ch2));
                //
                //sb3.append(map.getOrDefault(ch1, ch1));
                //sb3.append(map.getOrDefault(ch2, ch2));
                
                i++;
                j++;
            }        
            if (i == str1.length()-1) {
                char ch1 = str1.charAt(i);
                
                if ((ch1>='0' && ch1<='9') || (ch1>='A' && ch1<='F') || (ch1>='a' && ch1<='f')) {
                    sb3.append(map.get(ch1));
                } else {
                    sb3.append(ch1);
                }
                
                //
                //sb3.append(map.getOrDefault(ch1, ch1));
            }
            return sb3.toString();
        }
        
        public static String sort(String str) {
            char[] arr = str.toCharArray();
            Arrays.sort(arr);
            
            /*
            for (int i=0; i<=arr.length-2; i++) {
                int min = i;
                for (int j=i+1; j<=arr.length-1; j++) {
                    if (min < arr[j]) {
                        min = j;
                    }
                }
                char temp = arr[i];
                arr[i] = arr[min];
                arr[min] = temp;
            }
            */
            
            return new String(arr);
        }
        
    }

使用字符串存储映射关系

使用switch查找映射关系

import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.Arrays;
    public class Main {
    
        static String helper1 = "0123456789abcdefABCDEF";//原始字符
        static String helper2 = "084C2A6E195D3B7F5D3B7F";//相应的转换后的字符
        public static void main(String[] args) throws IOException {
            BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            String str;
            while ((str = bf.readLine()) != null) {
                String[] split = str.split(" ");//两个字符串
                String s = split[0] + split[1];
                int len = s.length();
                char[] odd = new char[(len + 1) / 2];//存储偶数下边的字符
                char[] even = new char[len / 2];
                int p1 = 0, p2 = 0;
                for (int i = 0; i < len; i++) {
                    char c = s.charAt(i);
                    if (i % 2 == 0) {
                        odd[p1++] = c;
                    } else {
                        even[p2++] = c;
                    }
                }
                Arrays.sort(odd);//对索引为偶数的进行排序
                Arrays.sort(even);//对索引为奇数下边的进行排序
                p1 = 0;//odd的指针
                p2 = 0;//even的指针
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < len; i++) {
                    char c = i % 2 == 0 ? odd[p1++] : even[p2++];
                    /*
                    if ((c >= '0' && c <= '9') || (c >= 'a' && c <= 'f') || (c >= 'A' && c <= 'F')) {
                        c = helper2.charAt(helper1.indexOf(c));
                    }
                    */
                    c = reverseChar(c);
                    
                    sb.append(c);
                }
                System.out.println(sb.toString());
            }
        }
        
        public static char reverseChar(char ch) {
            switch(ch) {
                case '0':
                    ch = '0';
                    break;
                case '1':
                    ch = '8';
                    break;
                case '2':
                    ch = '4';
                    break;
                case '3':
                    ch = 'C';
                    break;
                case '4':
                    ch = '2';
                    break;
                case '5':
                    ch = 'A';
                    break;
                case '6':
                    ch = '6';
                    break;
                case '7':
                    ch = 'E';
                    break;
                case '8':
                    ch = '1';
                    break;
                case '9':
                    ch = '9';
                    break;
                case 'a':
                case 'A':
                    ch = '5';
                    break;
                case 'b':
                case 'B':
                    ch = 'D';
                    break;
                case 'c':
                case 'C':
                    ch = '3';
                    break;
                case 'd':
                case 'D':
                    ch = 'B';
                    break;
                case 'e':
                case 'E':
                    ch = '7';
                    break;
                case 'f':
                case 'F':
                    ch = 'F';
                    break;
                default:
                    //其他情况不用转换
                    break;
            }
            
            return ch;
        } 
        
    }

### 2、不使用额外存储空间实现十六进制字符的逆转 ###

只需要注意两点：

1）‘0’——‘9’或者‘A’——‘F’或者‘a’——‘f’之外的字符不做任何改变

2）对于‘0’——‘9’、‘A’——‘F’、‘a’——‘f’，将其转换成二进制字符串，如果字符串长度不够4位，则需要在前面补4个0然后再从后往前截取4位。如，‘4’转为二进制后为"100"，则需要变成“0000100”然后再从后往截取得到“0100”，再将“0100”反转得到“0010”，转为十进制后为‘2’。

import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.Arrays;
    import java.math.BigInteger;
    public class Main {
    
        static String helper1 = "0123456789abcdefABCDEF";//原始字符
        static String helper2 = "084C2A6E195D3B7F5D3B7F";//相应的转换后的字符
        public static void main(String[] args) throws IOException {
            BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            String str;
            while ((str = bf.readLine()) != null) {
                String[] split = str.split(" ");//两个字符串
                String s = split[0] + split[1];
                int len = s.length();
                char[] odd = new char[(len + 1) / 2];//存储偶数下边的字符
                char[] even = new char[len / 2];
                int p1 = 0, p2 = 0;
                for (int i = 0; i < len; i++) {
                    char c = s.charAt(i);
                    if (i % 2 == 0) {
                        odd[p1++] = c;
                    } else {
                        even[p2++] = c;
                    }
                }
                Arrays.sort(odd);//对索引为偶数的进行排序
                Arrays.sort(even);//对索引为奇数下边的进行排序
                p1 = 0;//odd的指针
                p2 = 0;//even的指针
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < len; i++) {
                    char c = i % 2 == 0 ? odd[p1++] : even[p2++];
                    /*
                    if ((c >= '0' && c <= '9') || (c >= 'a' && c <= 'f') || (c >= 'A' && c <= 'F')) {
                        c = helper2.charAt(helper1.indexOf(c));
                    }
                    */
                    c = reverseChar(c);
                    
                    sb.append(c);
                }
                System.out.println(sb.toString());
            }
        }
        
        public static char reverseChar(char ch) {
            String binaryStr = "";
            if (ch>='0' && ch<='9') {
                //binaryStr = Integer.toBinaryString(ch - '0');
                binaryStr = Integer.toBinaryString(ch - 48);
            } else if (ch>='a' && ch<='f') {
                //binaryStr = Integer.toBinaryString(ch - 'a' + 10);
                binaryStr = Integer.toBinaryString(ch - 87);
            } else if (ch>='A' && ch<='F') {
                //binaryStr = Integer.toBinaryString(ch - 'A' + 10);
                binaryStr = Integer.toBinaryString(ch - 55);
            } else {
                //其他字符
                return ch;
            }
            
            //非其他字符
            //if (binaryStr != "") {    
                char result = ' ';
                /*
                binaryStr = "0000" + binaryStr;
                binaryStr = binaryStr.substring(binaryStr.length()-4);
                */
                while (binaryStr.length() < 4) {
                    binaryStr = "0" + binaryStr;
                }
                StringBuffer sb = new StringBuffer(binaryStr);
                binaryStr = sb.reverse().toString();
                /*
                int num = Integer.parseInt(binaryStr, 2);
                if (num < 10) {
                    result = (char)(num + 48);
                } else {
                    result = (char)(num + 55);
                }
                */
                BigInteger bi = new BigInteger(binaryStr, 2);
                String hexString = Integer.toHexString(bi.intValue()).toUpperCase();
                result = hexString.charAt(0);
            //}
            return result;
        }
        
        public static char reverseChar2(char ch) {
            int num = -1;
            if (ch>='0' && ch<='9') {
                num = ch - '0';
            } /*else if (ch>='a' && ch<='f') {
                num = ch - 'a' + 10;
            } else if (ch>='A' && ch<='F') {
                num = ch - 'A' + 10;
            }*/
            else if ((ch>='a' && ch<='f') || (ch>='A' && ch<='F')) {
                //Character.toLowerCase(char)  Character.toUpperCase(char)
                num = Character.toLowerCase(ch) - 'a' + 10;
            }
            
            //char result = '';
            //error: empty character literal
            //
            char result = ' ';
            if (num == -1) {
                //其他字符，无需处理，直接返回本身即可
                return ch;
            }
            /*
            int[] bits = new int[4];
            for (int i=0; i<4 && num!=0; i++) {
                bits[i] = num % 2;
                num /= 2;
            }
            num = bits[0]*8 + bits[1]*4 + bits[2]*2 + bits[3]*1;
            */
            int temp = num;
            num = 0;
            int i = 8;
            while(temp != 0) {
                num += (temp % 2) * i;
                temp /= 2;
                i /= 2;
            }
            if (num>=0 && num<=9) {
                //result = '0' + num;
                //error:  incompatible types: possible lossy conversion from int to char
                //
                result = (char)('0' + num);
            } else if (num>=10 && num<=15) {
                result = (char)('A' + num - 10);
            }
            
            return result;
        }
        
    }

### 3、采用希尔排序实现排序算法 ###

import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.Arrays;
    import java.math.BigInteger;
    public class Main {
    
        public static void main(String[] args) throws IOException {
            BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            String str;
            while ((str = bf.readLine()) != null) {
                String[] split = str.split(" ");//两个字符串
                String s = split[0] + split[1];
                char[] arr = s.toCharArray();
                
                sort(arr);
                
                int len = s.length();
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < len; i++) {
                    char ch = reverseChar(arr[i]);
                    sb.append(ch);
                }
                System.out.println(sb.toString());
            }
        }
    
        /*
        //希尔排序
        public static void sort(char[] arr) {
            //希尔排序的增量
            int add = arr.length;
            while (add > 1) {
                //每次折半
                add = add / 2;
                
                for (int i=0; i<add; i++) {
                    for (int j=i+add; j<arr.length; j=j+add) {
                        char temp = arr[j];
                        int k = j - add;
                        for (; k>=0 && arr[k]>temp; k=k-add) {
                            arr[k+add] = arr[k];
                        }
                        arr[k+add] = temp;
                    }
                }
                
            }
        }
        */
    
        public static void sort(char[] arr) {
            //希尔排序的增量
            int add = 2;
            
            for (int i=0; i<add; i++) {
                for (int j=i+add; j<arr.length; j=j+add) {
                    char temp = arr[j];
                    int k = j - add;
                    for (; k>=0 && arr[k]>temp; k=k-add) {
                        arr[k+add] = arr[k];
                    }
                    arr[k+add] = temp;
                }
            }
        }
    
        public static char reverseChar(char ch) {
            String binaryStr = "";
            if (ch>='0' && ch<='9') {
                //binaryStr = Integer.toBinaryString(ch - '0');
                binaryStr = Integer.toBinaryString(ch - 48);
            } else if (ch>='a' && ch<='f') {
                //binaryStr = Integer.toBinaryString(ch - 'a' + 10);
                binaryStr = Integer.toBinaryString(ch - 87);
            } else if (ch>='A' && ch<='F') {
                //binaryStr = Integer.toBinaryString(ch - 'A' + 10);
                binaryStr = Integer.toBinaryString(ch - 55);
            } else {
                //其他字符
                return ch;
            }
            
            //非其他字符
            //if (binaryStr != "") {    
                char result = ' ';
                /*
                binaryStr = "0000" + binaryStr;
                binaryStr = binaryStr.substring(binaryStr.length()-4);
                */
                while (binaryStr.length() < 4) {
                    binaryStr = "0" + binaryStr;
                }
                StringBuffer sb = new StringBuffer(binaryStr);
                binaryStr = sb.reverse().toString();
                /*
                int num = Integer.parseInt(binaryStr, 2);
                if (num < 10) {
                    result = (char)(num + 48);
                } else {
                    result = (char)(num + 55);
                }
                */
                BigInteger bi = new BigInteger(binaryStr, 2);
                String hexString = Integer.toHexString(bi.intValue()).toUpperCase();
                result = hexString.charAt(0);
            //}
            return result;
        }
        
    }

[https_www.nowcoder.com_practice_d3d8e23870584782b3dd48f26cb39c8f_tpId_37_tqId_21253_tPage_2_rp_ru_2Fta_2Fhuawei_qru_2Fta_2Fhuawei_2Fquestion-ranking]: https://www.nowcoder.com/practice/d3d8e23870584782b3dd48f26cb39c8f?tpId=37&tqId=21253&tPage=2&rp=&ru=%2Fta%2Fhuawei&qru=%2Fta%2Fhuawei%2Fquestion-ranking