网站建设公司话术,河南企业网站排名优化价格,企业官网制作公司,c++语言做网站题目#xff1a; * 题目#xff1a; * 回文串#xff0c;是一种特殊的字符串#xff0c;它从左往右和从右往左读是一样的。 * 现在给你一个串#xff0c;它不一定是回文的#xff0c;请你计算最少的交换次数使得该串变为完美的回文回文串。 * 例如#xff1a;mamad * 第…题目 * 题目 * 回文串是一种特殊的字符串它从左往右和从右往左读是一样的。 * 现在给你一个串它不一定是回文的请你计算最少的交换次数使得该串变为完美的回文回文串。 * 例如mamad * 第一次交换mamda * 第二次交换madma * 第三次交换madam * * 输入格式 * 第一行输入整数n 表示字符串的长度n 8000 ) * 第二行输入字符串长度为n只包含小写字母 * * 输出格式 * 如果可能输出最少次数 * 否则输出Impossible * * 样列输入 * 5 * mamad * 样例输出 * 3 解题思路
输入处理数据输出
输入
Scanner sc new Scanner(System.in);int len sc.nextInt();String str sc.next();
处理数据多读题解题的关键 关键词提取 回文串 第一个与倒数第一一样 第二个与倒数第二一样 思考 什么是回文串 怎么判断它是回文串 结论 1根据回文串的定义我们需要俩个指针一个从左往右一个从右往左 2根据第一点我们可以定义一个指针从左往右遍历一个指针从右往左遍历找到相同的就将它丢到最后长度-- 如图当我们找到m后将m移动到最后m不可能再次被移动【回文串特性当前数据的第一个与当前数据的最后一个一样】 3第一个与最后一个位置确定那就可以缩短数组的长度 如果没有找到呢 按照刚才的思路如果没有找到我们不管它会出现什么样的情况 我们把c假装看不见跳过对后面的数据排列让它除掉c就是回文数最后只需要移动c即可 思路总结 这题最重要是思路是将左右移动的数据转换为只移动一个方向我们每一次假设左边得到的数据是已经排好序的从当前左边的数据中确定当前最后位置的数据 在这个过程中我们对数组的长度减少减少交换的可能次数保证数据只从一个方向移动所以可以作为最少移动次数 1、判断数据是否可以构成回文串 //判断是否为可成为回文串//将数据类型转换为数组减少charAt的调用char[] arr str.toCharArray();//1、判断长度是否符合if (len ! arr.length) {System.out.println(Impossible1);return;}//2、判断是否可以构成回文串int[] num new int[26];for (int i 0; i arr.length; i) {int k arr[i] - 97;num[k];}int ans 0;for (int i : num) {if (i % 2 1) {ans;}}if (ans 1) {System.out.println(Impossible2);return;}2、构建回文串记录回文数据 ans 0;//记录移动次数int end len - 1;for (int i 0; i (len1) / 2; i) {int j;for (j end; j i; j--) {if (arr[i] arr[j]) {while (j end) {char tmp arr[j];arr[j] arr[j 1];arr[j 1] tmp;j;ans;}
《《 长度-- 》》end--;break;}}if (i j) {ans (len-1) / 2 - i;}}
输出ans记录次数
System.out.println(ans);
完整代码《因为懒所以没有使用方法》
package LanQiao.text;import java.util.Scanner;/*** 题目* 回文串是一种特殊的字符串它从左往右和从右往左读是一样的。* 现在给你一个串它不一定是回文的请你计算最少的交换次数使得该串变为完美的回文回文串。* 例如mamad* 第一次交换mamda* 第二次交换madma* 第三次交换madam* p* 输入格式* 第一行输入整数n 表示字符串的长度n 8000 )* 第二行输入字符串长度为n只包含小写字母* p* 输出格式* 如果可能输出最少次数* 否则输出Impossible* p* 样列输入* 5* mamad* 样例输出* 3*/
public class 回文串 {public static void main(String[] args) {Scanner sc new Scanner(System.in);int len sc.nextInt();String str sc.next();//判断是否为可成为回文串//将数据类型转换为数组减少charAt的调用char[] arr str.toCharArray();//1、判断长度是否符合if (len ! arr.length) {System.out.println(Impossible1);return;}//2、判断是否可以构成回文串int[] num new int[26];for (int i 0; i arr.length; i) {int k arr[i] - 97;num[k];}int ans 0;for (int i : num) {if (i % 2 1) {ans;}}if (ans 1) {System.out.println(Impossible2);return;}ans 0;int end len - 1;for (int i 0; i (len1) / 2; i) {int j;for (j end; j i; j--) {if (arr[i] arr[j]) {while (j end) {char tmp arr[j];arr[j] arr[j 1];arr[j 1] tmp;j;ans;}end--;break;}}if (i j) {ans (len-1) / 2 - i;}}System.out.println(ans);}
}各位小伙伴有没有画图工具推荐~excle还是不顺手非常感谢
