华为OD机试 2024E卷题库疯狂收录中，刷题点这里
专栏导读
本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。
刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。
一、题目描述
如果一个字符串正读和反读都一样（大小写敏感），则称之为一个「回文串」，例如：
- level 是一个「回文串」，因为它的正读和反读都是 level；同理也是「回文串」
- art 不是一个「回文串」，因为它的反读 tra 与正读不同
- LeveL 不是一个「回文串」，因为它的反读 LeveL 与正读不同（因大小写敏感）
给你一个仅包含大小写字母的字符串，请用这些字母构造出一个最长的 回文串 Q，若有多个最长的，返回其中 字典序最小 的回文串。
字符串中的每个位置的字母最多备用一次，也可以不用。
二、输入描述
无
三、输出描述
无
四、测试用例
测试用例1：
1、输入
abczzcccdzz
2、输出
ccdzzadzzcc
3、说明
字符统计：a:1, b:1, c:4, d:1, z:4
左半部分：cczz（取2个c和2个z）
中间字符：a（字典序最小的单个字符）
右半部分：zzcc
最终回文串：cczz + a + zzcc = cczzazzcc
测试用例2：
1、输入
aabb
2、输出
abba
3、说明
字符统计：a:2, b:2
左半部分：ab
中间字符：无
右半部分：ba
最终回文串：ab + ba = abba
五、解题思路
- 统计字符频率：
- 遍历输入字符串，统计每个字符出现的次数。
- 由于字符串仅包含大小写字母，可以使用一个固定大小的数组（如52个元素，分别对应’A’-‘Z’和’a’-‘z’）来高效地记录每个字符的出现次数。
- 构造回文串的左半部分：
- 遍历所有字符，按照字典序从小到大处理。
- 对于每个字符，取其出现次数的一半（即能组成的字符对数），并将这些字符按顺序添加到回文串的左半部分。
- 这样确保左半部分是字典序最小的，同时也保证了回文串的最大长度。
- 选择回文串的中间字符（如果有）：
- 在所有字符中，选择字典序最小且出现次数为奇数的字符，作为回文串的中间字符。
- 这一步是为了在无法完全对称的情况下，尽可能地增加回文串的长度，同时保持字典序最小。
- 构造回文串的右半部分：
- 将左半部分进行逆序，得到右半部分。
- 最终的回文串由左半部分、中间字符（如果有）和右半部分组成。
- 综合拼接：
- 拼接左半部分、中间字符和右半部分，得到最终的回文串。
通过高效的频率统计和贪心算法，结合适当的数据结构（数组和StringBuilder），在保证回文串长度最大化的同时，确保了字典序的最小化。这种方法不仅满足了题目的所有要求，而且在时间和空间效率上都表现优异。
六、Python算法源码
# 导入所需的模块
import sysdef construct_longest_palindrome(s):# 创建一个大小为52的数组，前26个位置对应'A'-'Z'，后26个位置对应'a'-'z'count = [0] * 52for c in s:if 'A' <= c <= 'Z':count[ord(c) - ord('A')] += 1 # 统计大写字母elif 'a' <= c <= 'z':count[26 + ord(c) - ord('a')] += 1 # 统计小写字母left = [] # 回文串的左半部分middle = '' # 回文串的中间字符（如果有的话）# 遍历所有字符，按照字典序从小到大处理for i in range(52):pairs = count[i] // 2 # 计算当前字符可以使用的对数if pairs > 0:char = index_to_char(i) # 获取字符left.append(char * pairs) # 将字符对添加到左半部分count[i] -= pairs * 2 # 更新剩余的字符数# 查找可以作为中间字符的最小字符for i in range(52):if count[i] > 0:middle = index_to_char(i) # 选择字典序最小的字符作为中间字符break# 构造右半部分为左半部分的逆序right = ''.join(left)[::-1]# 拼接左半部分、中间字符和右半部分，得到最终的回文串palindrome = ''.join(left) + middle + rightreturn palindromedef index_to_char(index):if index < 26:return chr(ord('A') + index) # 转换为大写字母else:return chr(ord('a') + index - 26) # 转换为小写字母def main():# 读取输入字符串input_str = sys.stdin.read().strip()# 调用构造最长回文串的方法palindrome = construct_longest_palindrome(input_str)# 输出结果print(palindrome)if __name__ == "__main__":main()七、JavaScript算法源码
// 最长回文串构造程序/*** 构造最长回文串* @param {string} s 输入字符串* @return {string} 构造出的最长回文串*/
function constructLongestPalindrome(s) {// 创建一个大小为52的数组，前26个位置对应'A'-'Z'，后26个位置对应'a'-'z'let count = new Array(52).fill(0);for (let c of s) {if (c >= 'A' && c <= 'Z') {count[c.charCodeAt(0) - 'A'.charCodeAt(0)] += 1; // 统计大写字母} else if (c >= 'a' && c <= 'z') {count[26 + c.charCodeAt(0) - 'a'.charCodeAt(0)] += 1; // 统计小写字母}}let left = ''; // 回文串的左半部分let middle = ''; // 回文串的中间字符（如果有的话）// 遍历所有字符，按照字典序从小到大处理for (let i = 0; i < 52; i++) {let pairs = Math.floor(count[i] / 2); // 计算当前字符可以使用的对数if (pairs > 0) {let char = indexToChar(i); // 获取字符left += char.repeat(pairs); // 将字符对添加到左半部分count[i] -= pairs * 2; // 更新剩余的字符数}}// 查找可以作为中间字符的最小字符for (let i = 0; i < 52; i++) {if (count[i] > 0) {middle = indexToChar(i); // 选择字典序最小的字符作为中间字符break;}}// 构造右半部分为左半部分的逆序let right = left.split('').reverse().join('');// 拼接左半部分、中间字符和右半部分，得到最终的回文串let palindrome = left + middle + right;return palindrome;
}/*** 将索引转换为对应的字符* @param {number} index 字符索引（0-51）* @return {string} 对应的字符*/
function indexToChar(index) {if (index < 26) {return String.fromCharCode('A'.charCodeAt(0) + index); // 转换为大写字母} else {return String.fromCharCode('a'.charCodeAt(0) + index - 26); // 转换为小写字母}
}// 读取标准输入并处理
const readline = require('readline');const rl = readline.createInterface({input: process.stdin,output: process.stdout
});let input = '';rl.on('line', function(line) {input += line;
}).on('close', function() {// 调用构造最长回文串的方法let palindrome = constructLongestPalindrome(input.trim());// 输出结果console.log(palindrome);process.exit(0);
});八、C算法源码
#include <stdio.h>
#include <string.h>// 将索引转换为对应的字符
char index_to_char(int index) {if (index < 26) {return 'A' + index; // 转换为大写字母} else {return 'a' + index - 26; // 转换为小写字母}
}/*** 构造最长回文串* @param s 输入字符串* @return 构造出的最长回文串（需要调用者提供足够的缓冲区）*/
void construct_longest_palindrome(char *s, char *palindrome) {int count[52] = {0}; // 创建一个大小为52的数组，前26个位置对应'A'-'Z'，后26个位置对应'a'-'z'int len = strlen(s);for (int i = 0; i < len; i++) {char c = s[i];if (c >= 'A' && c <= 'Z') {count[c - 'A'] += 1; // 统计大写字母} else if (c >= 'a' && c <= 'z') {count[26 + c - 'a'] += 1; // 统计小写字母}}char left[1001] = ""; // 回文串的左半部分char middle = '\0'; // 回文串的中间字符（如果有的话）// 遍历所有字符，按照字典序从小到大处理for (int i = 0; i < 52; i++) {int pairs = count[i] / 2; // 计算当前字符可以使用的对数if (pairs > 0) {char current_char = index_to_char(i); // 获取字符for (int j = 0; j < pairs; j++) {strncat(left, ¤t_char, 1); // 将字符对添加到左半部分}count[i] -= pairs * 2; // 更新剩余的字符数}}// 查找可以作为中间字符的最小字符for (int i = 0; i < 52; i++) {if (count[i] > 0) {middle = index_to_char(i); // 选择字典序最小的字符作为中间字符break;}}// 构造右半部分为左半部分的逆序char right[1001] = "";int left_len = strlen(left);for (int i = left_len - 1; i >= 0; i--) {strncat(right, &left[i], 1);}// 拼接左半部分、中间字符和右半部分，得到最终的回文串strcpy(palindrome, left);if (middle != '\0') {int current_len = strlen(palindrome);palindrome[current_len] = middle;palindrome[current_len + 1] = '\0';}strcat(palindrome, right);
}int main() {char input[1001];// 读取输入字符串scanf("%s", input);char palindrome[2002] = ""; // 需要足够大的缓冲区存储回文串// 调用构造最长回文串的方法construct_longest_palindrome(input, palindrome);// 输出结果printf("%s\n", palindrome);return 0;
}九、C++算法源码
#include <bits/stdc++.h>
using namespace std;// 将索引转换为对应的字符
char index_to_char(int index) {if (index < 26) {return 'A' + index; // 转换为大写字母} else {return 'a' + index - 26; // 转换为小写字母}
}/*** 构造最长回文串* @param s 输入字符串* @return 构造出的最长回文串*/
string construct_longest_palindrome(const string &s) {int count[52] = {0}; // 创建一个大小为52的数组，前26个位置对应'A'-'Z'，后26个位置对应'a'-'z'for (char c : s) {if (c >= 'A' && c <= 'Z') {count[c - 'A'] += 1; // 统计大写字母} else if (c >= 'a' && c <= 'z') {count[26 + c - 'a'] += 1; // 统计小写字母}}string left = ""; // 回文串的左半部分string middle = ""; // 回文串的中间字符（如果有的话）// 遍历所有字符，按照字典序从小到大处理for (int i = 0; i < 52; i++) {int pairs = count[i] / 2; // 计算当前字符可以使用的对数if (pairs > 0) {char current_char = index_to_char(i); // 获取字符left += string(pairs, current_char); // 将字符对添加到左半部分count[i] -= pairs * 2; // 更新剩余的字符数}}// 查找可以作为中间字符的最小字符for (int i = 0; i < 52; i++) {if (count[i] > 0) {middle += index_to_char(i); // 选择字典序最小的字符作为中间字符break;}}// 构造右半部分为左半部分的逆序string right = left;reverse(right.begin(), right.end());// 拼接左半部分、中间字符和右半部分，得到最终的回文串string palindrome = left + middle + right;return palindrome;
}int main(){string input;// 读取输入字符串cin >> input;// 调用构造最长回文串的方法string palindrome = construct_longest_palindrome(input);// 输出结果cout << palindrome << endl;return 0;
}🏆下一篇：华为OD机试真题 - 简易内存池（Python/JS/C/C++ 2024 E卷 200分）
🏆本文收录于，华为OD机试真题（Python/JS/C/C++）
刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。
