蓝桥杯 BASIC-19 VIP试题 完美的代价 贪心算法
试题 基础练习 完美的代价
交换的定义是:交换两个相邻的字符
例如mamad
第一次交换 ad : mamda
第二次交换 md : madma
第三次交换 ma : madam (回文!完美!)
第二行是一个字符串,长度为N.只包含小写字母
否则输出Impossible
mamad
分析:
首先判断字符串是否能构成回文串:
不能构成回文串的话直接输出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();
}
}
演示效果如下--
希望能对大家有所帮助!
谢谢大家!
- 点赞
- 收藏
- 关注作者
评论(0)