2020年ICPC辽宁省赛- 最长回文串（Java）题目描述算法分析代码展示

66 阅读 0 评论 44 点赞

我是靠谱客的博主快乐书本，最近开发中收集的这篇文章主要介绍2020年ICPC辽宁省赛- 最长回文串（Java）题目描述算法分析代码展示，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

最长回文串

题目描述
算法分析
代码展示

题目描述

链接：ICPC辽宁省赛复现赛

题目描述：
回文串是反转后与自身完全相同的字符串
比如：“ABA”,“ACMMCA”,“A”。
给出一系列长度相同的字符串，请按序进行如下操作构造出最长的回文串:

1.舍弃一些字符串
2.重新排列剩余的每个字符串内字符的顺序，重新排列后的结果可以与原字符串相同
3.重新排列剩余字符串的顺序
4.将剩余字符串按序首尾连接组成回文串

输入描述:

第一行输入两个整数 n 和 m (1≤n≤100,1≤m≤50)，表示字符串的数量和每个字符串的长度。
接下来 n 行每行包含一个长度为m的字符串，每个字符串由小写英文字母组成。

输出描述:

每组数据输出一个整数，表示经过以上四次操作你能够得到的最长回文串的长度。

算法分析

贪心算法：我们如何选择，可以使新组成的字符串长度最大

我们可以考虑到一下情况：

当一个字符串（不考虑字符顺序）出现偶数次，那么我们便可以将它平均放到新字符串的两边，可以重组为回文串
如：“abc” “acb”，（不考虑字符顺序）等同于 “abc” 出现两次，可以重新排列为 “abc cba”，即回文串。
当一个字符串（不考虑字符顺序）出现奇数次，那么我们便可以将它的 （出现次数-1）即：偶数次平均放到新字符串的两边，可以继续重组为回文串
那么该字符串最后剩下的一个，如果该字符串本身是 回文串的话，我们就可以将它放在中间，从而不影响新字符串的整体回文性
注意：放在中间的只能有一个字符串，且该字符串必须是回文的，否则便舍弃

例如

“aab” “aab” “aab”
“aac”“aac”“aac”“aac”“aac”

将"aab" "aac"偶数次个分别放在两边，组成新字符串：

“aab aac aac caa caa baa”

那么还剩下一个"aab" “aac”，我们需要判断这两个字符串是否是回文串
将任意一个回文串放在中间就行
若两个都不是回文串，就全都舍弃。

“aab aac aac aca caa caa baa”
or
“aab aac aac aba caa caa baa”

代码展示

判断字符串是否可以通过重新排列字符顺序组成回文串，我们只需要统计不同字符出现的次数即可。
若出现奇数次的字符，超过1个，那其必定不能重构成回文串。这里请自行举例思考。

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        sc.nextLine();  // 缓冲上面的 n
        
        Map<String, Integer> map = new HashMap<>();
        // 统计重复的字符串个数，因为字符串顺序可以改变，因此我们将所有的字符串升序排序，加入map中
        while (n-- > 0) {
            char[] c = sc.nextLine().toCharArray();
            Arrays.sort(c);
            String s = new String(c);
            map.put(s, map.getOrDefault(s, 0)+1);
        }
        
        int res = 0;
        boolean flag = false;  // 标志位，判断是奇数次字符串，是否是回文串
        
        for (String s: map.keySet()) {
        	// 如果出现偶数次，直接要
            if ((map.get(s)&1) == 0) {
                res += (s.length() * map.get(s));
                
            } else {
                if (check(s))
                    flag = true;
                // 如果出现奇数次，只要 偶数次
                res += ((map.get(s)-1) * m);
            }
        }
        // 如果出现奇数次的字符串中有回文串，任意一个放中间即可，所以加一个字符串长度 m
        if (flag)
            res += m;
            
        System.out.println(res);
    }
    
    // 判断是否可以重构成回文串
    public static boolean check(String s) {
        Map<Character, Integer> map = new HashMap<>();
        // 统计词频
        for (char c: s.toCharArray())
            map.put(c, map.getOrDefault(c, 0)+1);
        // 统计奇数次字符个数
        int k = 0;
        
        // 遍历 map
        for (char c: map.keySet()) {
            if ((map.get(c)&1) == 1)
                k++;
        }
        return k < 2;
    }
}