当前位置： 首页 > article >正文

华为OD机试 - 最长回文字符串 - 贪心算法（Python/JS/C/C++ 2024 E卷 100分）

article 2025/2/24 9:27:01

在这里插入图片描述

华为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

五、解题思路

  1. 统计字符频率：
    • 遍历输入字符串，统计每个字符出现的次数。
    • 由于字符串仅包含大小写字母，可以使用一个固定大小的数组（如52个元素，分别对应’A’-‘Z’和’a’-‘z’）来高效地记录每个字符的出现次数。
  2. 构造回文串的左半部分：
    • 遍历所有字符，按照字典序从小到大处理。
    • 对于每个字符，取其出现次数的一半（即能组成的字符对数），并将这些字符按顺序添加到回文串的左半部分。
    • 这样确保左半部分是字典序最小的，同时也保证了回文串的最大长度。
  3. 选择回文串的中间字符（如果有）：
    • 在所有字符中，选择字典序最小且出现次数为奇数的字符，作为回文串的中间字符。
    • 这一步是为了在无法完全对称的情况下，尽可能地增加回文串的长度，同时保持字典序最小。
  4. 构造回文串的右半部分：
    • 将左半部分进行逆序，得到右半部分。
    • 最终的回文串由左半部分、中间字符（如果有）和右半部分组成。
  5. 综合拼接：
    • 拼接左半部分、中间字符和右半部分，得到最终的回文串。

通过高效的频率统计和贪心算法，结合适当的数据结构（数组和StringBuilder），在保证回文串长度最大化的同时，确保了字典序的最小化。这种方法不仅满足了题目的所有要求，而且在时间和空间效率上都表现优异。

六、Python算法源码

# 导入所需的模块
import sys

def construct_longest_palindrome(s):
    # 创建一个大小为52的数组，前26个位置对应'A'-'Z'，后26个位置对应'a'-'z'
    count = [0] * 52
    for 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 + right
    return palindrome

def 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, &current_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在线答疑。

在这里插入图片描述


http://www.kler.cn/a/328042.html

相关文章：

  • ZYNQ： GPIO 之 MIO 控制 LED 实验
  • Qt(9.28)
  • 深入理解 `strtok()` 函数：字符串分割的艺术
  • go语言 常用的web框架
  • Ansible学习之ansible-pull命令
  • LLaMA: 开源大语言模型的革新者
  • react是一种语言？
  • PHP中的PEAR是什么
  • Metasploit渗透测试之服务端漏洞利用
  • 【基于spring-cloud-gateway实现自己的网关过滤器】
  • 通过 IPv6 进行远程 ADB 调试
  • 《RabbitMQ篇》基本概念介绍
  • 用于多模态MRI重建的具有空间对齐的深度展开网络|文献速递--基于多模态-半监督深度学习的病理学诊断与病灶分割
  • 基于C++和Python的进程线程CPU使用率监控工具
  • 【Linux 报错】“make: ‘xxxx‘ is up to date.” 解决办法
  • 红米k60至尊版工程固件 MTK芯片 资源预览 刷写说明 与nv损坏修复去除电阻图示
  • 第四届高性能计算与通信工程国际学术会议(HPCCE 2024)
  • 工程安全监测分析模型与智能算法模型方案
  • Shp2pb：Shapefile转Protocol Buffers的高效工具
  • 深度学习：DCGAN