HJ30. 字符串合并处理
题目描述
给定两个字符串 s1、s2（由大小写字母和数字构成，下标从 1 开始）。
【合并阶段】
- 将 s1、s2 合并得到新串 str2。
- 将 str2 中奇数位字符按 ASCII 码升序排序，偶数位字符也按 ASCII 码升序排序，得到 str3。
【调整阶段】 从左到右遍历 str3 的每个字符：
- 若字符不是合法十六进制字符（0-9、a-f、A-F），原样保留；
- 否则转十进制数，转成四位二进制（高位补 0），翻转二进制，再转回大写十六进制。
输入格式
- 一行两个字符串 s1 s2（用空格分隔）。
输出格式
- 处理后的最终字符串。
示例
示例 1
输入：
dec fab
输出：
5D37BF
说明：
合并得 decfab，奇数位排序后与偶数位排序交错得到 dcefba，再逐个十六进制反转：d→B、c→3、e→7、f→F、b→D、a→5 → 5D37BF。
示例 2
输入：
abV CDw
输出：
B3VD5w
解题思路
第一步：理解问题本质
分为两个阶段：先做奇偶位分离排序，再对十六进制字符做二进制反转。
第二步：暴力解法（逐字符排序拼接）
合并后用一个循环模拟奇数位、偶数位分别提取再排序。
问题：下标（1 基）容易混淆，需要仔细对齐奇数位/偶数位。
第三步：优化解法（切片分离 + sorted）
利用切片 [0::2] 和 [1::2] 直接提取所有奇数位（1 基奇数位 = 0 基偶数下标）和偶数位，分别 sorted() 后再交错拼回。
odd = sorted(merged[0::2]) # 1基奇数位 = 0基偶数
even = sorted(merged[1::2]) # 1基偶数位 = 0基奇数
inter = []
for i in range(len(merged)):
inter.append(odd[i // 2] if i % 2 == 0 else even[i // 2])
str3 = ''.join(inter)
第四步：最优解法（十六进制转换）
调整阶段对每个字符：用 int(ch, 16) 判断是否为合法十六进制字符（非法会抛异常），合法则转四位二进制、反转、再转回大写十六进制。
def transform(ch: str) -> str:
try:
val = int(ch, 16) # 非法十六进制会抛异常
except ValueError:
return ch
rev = format(val, '04b')[::-1] # 转四位二进制、反转
return hex(int(rev, 2))[2:].upper()
完整代码实现
算法可视化 · 逐帧回放这道题的代码9 帧 · 录制输入
import sys
def transform(ch: str) -> str:
"""调整阶段：十六进制字符反转二进制后转回大写十六进制，非十六进制字符保留"""
try:
val = int(ch, 16) # 非法十六进制会抛异常
except ValueError:
return ch
# 转四位二进制、反转、再转回十六进制大写
rev = format(val, '04b')[::-1]
return hex(int(rev, 2))[2:].upper()
def solve() -> None:
"""主求解函数"""
s1, s2 = sys.stdin.readline().split()
merged = s1 + s2
# 合并阶段：奇数位、偶数位分别按 ASCII 升序排序后交错拼回（下标从 1 开始）
odd = sorted(merged[0::2]) # 1基奇数位 = 0基偶数
even = sorted(merged[1::2]) # 1基偶数位 = 0基奇数
inter = []
for i in range(len(merged)):
inter.append(odd[i // 2] if i % 2 == 0 else even[i // 2])
str3 = ''.join(inter)
# 调整阶段
print(''.join(transform(c) for c in str3))
if __name__ == "__main__":
solve()
示例推演
以示例 1 dec fab 为例：
合并阶段：
- 合并
dec+fab=decfab - 奇数位（1 基）：d、c、f（0 基下标 0、2、4）→ 排序后
c d f - 偶数位（1 基）：e、a、b（0 基下标 1、3、5）→ 排序后
a b e - 交错拼回：
d c e f a b对应位置取值 →d c e f a b，即dcefab
（注：排序后奇数位为 c,d,f，偶数位为 a,b,e，交错到 1 基奇/偶位得到 d c e f a b → dcefab）
调整阶段：
| 字符 | 合法十六进制? | 二进制 | 反转 | 十六进制 |
|---|---|---|---|---|
| d | 是 | 1101 | 1011 | B |
| c | 是 | 1100 | 0011 | 3 |
| e | 是 | 1110 | 0111 | 7 |
| f | 是 | 1111 | 1111 | F |
| a | 是 | 1010 | 0101 | 5 |
| b | 是 | 1011 | 1101 | D |
拼接结果：B 3 7 F 5 D → 5D37BF。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 逐字符模拟排序 | O(L log L) | O(L) | 排序开销，下标易错 |
| 切片 + 转换 | O(L log L) | O(L) | 切片与 sorted 简洁 |
L 为合并后字符串长度
易错点总结
1. 奇偶位下标
题目下标从 1 开始，1 基奇数位对应 0 基偶数下标，容易混淆。
2. 非十六进制字符保留
只有合法十六进制字符（0-9、a-f、A-F）才做二进制反转，其余（如 g、Z、V）原样保留。
3. 二进制补位与反转
十六进制转二进制要补足 4 位，反转后再转回十六进制，注意输出大写。
4. 排序按 ASCII 升序
奇数位、偶数位分别按 ASCII 码升序排序，不是按字符对应的数值。
扩展思考
- 用
int(ch, 16)判断合法性并取值，巧妙复用了异常处理。 - 十六进制与二进制的转换可借助 Python 的
format与int(x, base)完成，注意 4 位补零。