蓝桥杯 BASIC-19 VIP试题 完美的代价 贪心算法

举报
2002 发表于 2022/02/25 19:17:48 2022/02/25
【摘要】 试题 基础练习 完美的代价提交此题   评测记录  资源限制时间限制:1.0s   内存限制:512.0MB问题描述  回文串,是一种特殊的字符串,它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串,它不一定是回文的,请你计算最少的交换次数使得该串变成一个完美的回文串。  交换的定义是:交换两个相邻的字符  例如mamad  第一次交换 ad : mamda  第二...

试题 基础练习 完美的代价

资源限制
时间限制:1.0s   内存限制:512.0MB
问题描述
  回文串,是一种特殊的字符串,它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串,它不一定是回文的,请你计算最少的交换次数使得该串变成一个完美的回文串。
  交换的定义是:交换两个相邻的字符
  例如mamad
  第一次交换 ad : mamda
  第二次交换 md : madma
  第三次交换 ma : madam (回文!完美!)
输入格式
  第一行是一个整数N,表示接下来的字符串的长度(N <= 8000)
  第二行是一个字符串,长度为N.只包含小写字母
输出格式
  如果可能,输出最少的交换次数。
  否则输出Impossible
样例输入
5
mamad
样例输出
3

分析:
首先判断字符串是否能构成回文串:
不能构成回文串的话直接输出Impossible。

只要只出现奇数次的字母个数多于1个就不能构成回文串。

能构成回文串的话再用递归的方法统计需要移动的最小次数。

代码如下


import java.util.Scanner;

public class Main {
    public static boolean IsPossible(String str) { // 判断字符串是否能构成回文串
        boolean flag = true;
        char[] s = str.toCharArray();
        int[] num = new int[26];

        for (int i = 0; i < str.length(); i++) {
            num[s[i] - 'a']++;
        }

        int count = 0;
        for (int i = 0; i < 26; i++) {
            if (num[i] % 2 == 1)
                count++;
        }
        if (count > 1)
            return false;
        return flag;
    }

    public static int getCount(String str) { // 调换成回文串需要交换的次数
        if (str.length() == 1 || str.length() == 2)
            return 0;
        int temp = str.lastIndexOf(str.charAt(0));
        if (temp == 0) {
            return str.length() / 2 + getCount(str.substring(1, str.length()));
        } else {
            // temp不为0说明首字符有匹配的字母,移除首字母及其对应字母
            // 返回将temp位置的字符移动到末位置的次数(str.length()- temp - 1)
            // 递归调用getResult()方法
            StringBuilder sb = new StringBuilder(str);
            sb.deleteCharAt(temp);
            sb.deleteCharAt(0);
            return str.length() - temp - 1 + getCount(sb.toString());
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String str = sc.next();

        if (IsPossible(str)) {
            System.out.println(getCount(str));
        } else {
            System.out.println("Impossible");
        }

        sc.close();
    }
}

演示效果如下--

希望能对大家有所帮助!

谢谢大家!



【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。