字符变换"/>

拼多多——多多的字符变换

多多的字符变换

• 题目
• 思路
• 代码
• 结果

题目

多多君最近在研究字符串之间的变换，可以对字符串进行若干次变换操作:

交换任意两个相邻的字符，代价为0。
将任意一个字符a修改成字符b，代价为 |a - b|（绝对值）。
现在有两个长度相同的字符串X和Y，多多君想知道，如果要将X和Y变成两个一样的字符串，需要的最少的代价之和是多少。
题目传送门

思路

1、变换任意两个相邻的字符，代价为0。也就是说，我们可以通过无限次变换，来获得我们想要获得的字符串顺序。
2、修改字符，当然是两个离得越近的字符去修改越好！
3、基于以上两点，先统计出各个字符串的字母个数【题目中说到，字符串皆为小写字符】。
4、然后去除掉两个字符串相同的字母
5、再找他们不同字母的字符进行转化即可。

代码

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner reader=new Scanner(System.in);int N=reader.nextInt();//接收字符串长度reader.nextLine();// 消除上面输入数字后回车符带来的影响String a=reader.next();String b=reader.next();int a_num[]=new int[26];int b_num[]=new int[26];// 计算 字符串 a b两个字符for (int i=0;i<N;++i){++a_num[((int)a.charAt(i)-97)];++b_num[((int)b.charAt(i)-97)];}for (int i=0;i<26;++i){int min=Math.min(a_num[i],b_num[i]);a_num[i]-=min;b_num[i]-=min;}int i=0;int j=0;int ans=0;while (i<26 && j<26){while (a_num[i]==0){++i;if (i>=26)break;}while (b_num[j]==0){++j;if (j>=26)break;}if (i>=26 || j>=26)break;// 找出来两个数组的不为0的字母if (a_num[i]>b_num[j]) // a的字母多{ans+=Math.abs(i-j)*b_num[j];a_num[i]-=b_num[j];b_num[j]=0;}else  if (b_num[j]>=a_num[j])// b的字母多{ans+=Math.abs(i-j)*a_num[i];b_num[j]-=a_num[i];a_num[i]=0;}}System.out.println(ans);}
}

结果

AC了，这道题不算很难，就是要把思路一遍捋清楚，有点小麻烦！自己写代码的能力还是差，眼高手低，有思路，但是要想真正实现思路，就很难！