题解 | 字符串合并处理

package main

import (
	"fmt"
	"sort"
	"strconv"
	"strings"
)

func main() {
	var s, t string
	fmt.Scan(&s, &t)

	result := processString(s, t)
	fmt.Println(result)
}

func processString(s, t string) string {
	// 合并阶段
	u := s + t

	// 分离奇偶位字符（按1开始的下标）
	var oddChars, evenChars []rune
	for i, char := range u {
		if (i+1)%2 == 1 { // 奇数位（下标从1开始）
			oddChars = append(oddChars, char)
		} else { // 偶数位
			evenChars = append(evenChars, char)
		}
	}

	// 按ASCII码排序
	sort.Slice(oddChars, func(i, j int) bool {
		return oddChars[i] < oddChars[j]
	})
	sort.Slice(evenChars, func(i, j int) bool {
		return evenChars[i] < evenChars[j]
	})

	// 重新组合：按奇偶位交替排列
	var uPrime strings.Builder
	maxLen := len(oddChars)
	if len(evenChars) > maxLen {
		maxLen = len(evenChars)
	}

	for i := 0; i < maxLen; i++ {
		if i < len(oddChars) {
			uPrime.WriteRune(oddChars[i])
		}
		if i < len(evenChars) {
			uPrime.WriteRune(evenChars[i])
		}
	}

	// 调整阶段
	var result strings.Builder
	for _, char := range uPrime.String() {
		if isHexChar(char) {
			// 转换为十进制
			decValue := hexToDecimal(char)

			// 转换为4位二进制
			binary := fmt.Sprintf("%04b", decValue)

			// 翻转二进制
			reversed := reverseString(binary)

			// 转换回十六进制并转为大写
			reversedDec, _ := strconv.ParseInt(reversed, 2, 64)
			hexResult := strings.ToUpper(fmt.Sprintf("%X", reversedDec))
			result.WriteString(hexResult)
		} else {
			// 非十六进制字符直接添加
			result.WriteRune(char)
		}
	}

	return result.String()
}

func isHexChar(char rune) bool {
	return (char >= '0' && char <= '9') ||
		(char >= 'a' && char <= 'f') ||
		(char >= 'A' && char <= 'F')
}

func hexToDecimal(char rune) int {
	if char >= '0' && char <= '9' {
		return int(char - '0')
	}
	if char >= 'a' && char <= 'f' {
		return int(char - 'a' + 10)
	}
	if char >= 'A' && char <= 'F' {
		return int(char - 'A' + 10)
	}
	return 0
}

func reverseString(s string) string {
	runes := []rune(s)
	for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
		runes[i], runes[j] = runes[j], runes[i]
	}
	return string(runes)
}

解题思路

算法分析

这道题的核心是字符串处理和进制转换。主要涉及：

字符串合并：简单拼接两个字符串
奇偶位分离排序：按位置分离字符并分别排序
十六进制字符识别：判断字符是否为0-9、a-f、A-F
进制转换：十六进制→十进制→二进制→翻转→十六进制

算法流程图

flowchart TD
    A[输入字符串s和t] --> B[合并: u = s + t]
    B --> C[分离奇偶位字符]
    C --> D[奇数位排序]
    D --> E[偶数位排序]
    E --> F[重新组合: u']
    F --> G[遍历u'中每个字符]
    G --> H{是否为十六进制字符?}
    H -->|否| I[直接添加到结果]
    H -->|是| J[转换为十进制]
    J --> K[转换为4位二进制]
    K --> L[翻转二进制]
    L --> M[转换为大写十六进制]
    M --> N[添加到结果]
    I --> O{还有字符?}
    N --> O
    O -->|是| G
    O -->|否| P[输出最终结果]

合并阶段详解

graph TD
    A[字符串s] --> C[合并u = s + t]
    B[字符串t] --> C
    C --> D[按位置分离]
    D --> E[奇数位: 1,3,5,...]
    D --> F[偶数位: 2,4,6,...]
    E --> G[ASCII排序]
    F --> H[ASCII排序]
    G --> I[重新组合u']
    H --> I

调整阶段详解

graph TD
    A[字符] --> B{十六进制字符?}
    B -->|否| C[保持原字符]
    B -->|是| D[十六进制→十进制]
    D --> E[十进制→4位二进制]
    E --> F[翻转二进制串]
    F --> G[二进制→十进制]
    G --> H[十进制→大写十六进制]
    C --> I[添加到结果]
    H --> I

进制转换过程

graph LR
    A[十六进制a] --> B[十进制10]
    B --> C[二进制1010]
    C --> D[翻转0101]
    D --> E[十进制5]
    E --> F[十六进制5]

代码实现思路

合并阶段：字符串拼接：u = s + t奇偶位分离：按下标(i+1)%2判断ASCII排序：使用sort.Slice()重新组合：奇数位在前，偶数位在后
调整阶段：十六进制判断：范围检查0-9、a-f、A-F进制转换：使用标准库函数二进制翻转：字符串反转算法结果拼接：使用strings.Builder

时间复杂度分析

时间复杂度：O(n log n)，主要是排序操作
空间复杂度：O(n)，用于存储分离的字符和结果

关键优化点

字符分离优化：一次遍历分离奇偶位
排序优化：使用Go标准库的高效排序
字符串构建优化：使用strings.Builder避免频繁内存分配
进制转换优化：使用标准库函数和格式化

边界情况处理

空字符串：合并后为空或单个字符
全十六进制字符：所有字符都需要转换
无十六进制字符：所有字符都保持原样
单字符字符串：只有奇数位或偶数位

测试用例分析

graph TD
    A[测试用例1: dec fab] --> B[u=decfab → u'=abcedf]
    C[测试用例2: abV CDw] --> D[u=abVCDw → u'=DCVbaw]
    E[测试用例3: 123 15] --> F[u=12315 → u'=11325]
    
    B --> G[全十六进制字符]
    D --> H[混合字符类型]
    F --> I[纯数字字符]
    
    G --> J[验证进制转换]
    H --> K[验证字符过滤]
    I --> L[验证排序逻辑]

算法特点

多阶段处理：合并阶段和调整阶段分离
复杂转换：涉及多种进制转换
字符分类：需要识别十六进制字符
位置相关：奇偶位分别处理

实现细节

graph TD
    A[奇偶位判断] --> B[(i+1)%2 == 1为奇数位]
    C[十六进制判断] --> D[0-9, a-f, A-F]
    E[二进制翻转] --> F[字符串首尾交换]
    G[大写转换] --> H[strings.ToUpper()]

这个问题的关键在于正确理解题目的两个阶段和准确实现进制转换过程，特别是二进制翻转和十六进制字符的识别处理。