多多的字符变换（拼多多2021笔试真题集）_多多君在研究十六进制字符串的翻转关系_A_Zhong20的博客-程序员宝宝

技术标签：算法 java 面试题数据结构

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

1.交换任意两个相邻的字符，代价为0。
2. 将任意一个字符a修改成字符b，代价为 |a - b|（绝对值）。

现在有两个长度相同的字符串X和Y，多多君想知道，如果要将X和Y变成两个一样的字符串，需要的最少的代价之和是多少。

输入描述:

共三行，第一行，一个整数N，表示字符串的长度。
（1 <= N <= 2,000）
接下来两行，每行分别是一个字符串，表示字符串X和Y。
（字符串中仅包含小写字母）

输入例子1:

4
abca
abcd

输出例子1:

3

例子说明1:

其中一种代价最小的变换方案：
都修改为abcd，那么将第一个字符串X最后一个字符a修改为d，代价为|a - d| = 3。

输入例子2:

4
baaa
aabb

输出例子2:

1

例子说明2:

其中一种代价最小的变换方案：
首先将第一个字符串通过交换相邻的字符：baaa -> abaa -> aaba，代价为0。
然后将第二个字符串修改最后一个字符b：|b - a| = 1。
两个字符都修改为aaba，所以最小的总代价为1。

输入例子3:

3
abc
xyz

输出例子3:

69

实现思路：

将输入的字符串转为字符数组，然后调用Arrays中的sort排序方法对字符数组进行升序排序，这样，得到两个已经排好序的字符数组。通过for循环遍历这两个字符数组，用包装类型Integer将每个字符数组的字符转成对于的ASCII码值，然后做减法，即得出了最小代价。

代码实现：

import java.util.Arrays;
import java.util.Scanner;

public class Main{
    
    public static void main(String args[]) {
    
        Scanner sc = new Scanner(System.in);
        //输入字符串的长度length
        int length = Integer.parseInt(sc.nextLine());
        //输入字符串x
        String x = sc.nextLine();
        //输入字符串y
        String y = sc.nextLine();

        //首先判断x，y的长度是否=输入字符串的长度
        if (x.length() != y.length() || x.length() != length || y.length() != length) {
    
            System.out.println("输入错误！");
            return ;
        }

        //将x变换成y一样的字符串
        /*
            将输入的字符串转为字符数组，然后对其进行排序
         */
        int count = 0;
        //将输入的字符串转为字符数组
        char[] xArray = x.toCharArray();
        char[] yArray = y.toCharArray();
        //对字符数组其进行排序
        Arrays.sort(xArray);
        Arrays.sort(yArray);
        for (int i = 0; i < length; i++) {
    
            count += Math.abs(Integer.valueOf(xArray[i]) - Integer.valueOf(yArray[i]));
        }
        System.out.println(count);

        return;
}
}

牛客网原题：https://www.nowcoder.com/question/next?pid=30579184&qid=1712511&tid=44707421

本文链接：https://blog.csdn.net/A_Zhong20/article/details/117510526

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

向程序添加任意shellocde代码_ThatAllOver的博客-程序员宝宝

#define _CRT_SECURE_NO_WARNINGS#include <stdio.h>#include <string.h>#include <windows.h>#define ADD_SIZE 1024//添加节区的大小#define SEC_NAME ".new"//添加节区的名字//这一段shellocde的作用就是弹出一个...

ORA-01918: user hr does not exist 解决办法_青栀zjl的博客-程序员宝宝

ORA-01918: user hr does not exist 解决办法查看Oracle中自带的事例用户hr的表结构时登陆Oracle的客户端system身份登陆，打开命令窗口 SQL&gt;alter user hr identified by h111;//修改用户密码，自带用户的密码不知道可修改密码user alteredSQL&gt;alter user hr account unlo...

【算法】用动态规划求解背包问题_动态规划算法背包问题_小松不菜的博客-程序员宝宝

【算法】用动态规划求解背包问题

创建po的bapi BAPI_PO_CREATE1 刚刚sophie提起搜索相关_shiyanghua的博客-程序员宝宝

*/--------- 採購單表頭資訊LOOP AT ITAB_PO_HEADER . POHEAD-COMP_CODE = ITAB_PO_HEADER-BUKRS . " 公司 POHEAD-DOC_TYPE = ITAB_PO_HEADER-BSART . " 單據類別 POHEAD-CREAT_DATE = SY-DATUM .

Android--recovery备份系统，并做成卡刷包_chaoyu168的博客-程序员宝宝

首先说备份系统：进入recovery菜单，选择backup and restore（backup是备份，restore是还原）选择backup，然后等几分钟，就备份完成了想找到这个备份的文件很简单有两个路径（有些人可以在第一个路径找到，但有些人却要在第二个路径才能找到），但必须用re管理器。第一个路径：直接在sdcard/clockworkmod的文件夹下可以找到。第二个路径：在根目录dat

vue-router.esm.js?8c4f:1905 TypeError: Cannot read property ‘$route‘ of undefined_D.U.S.Tべ的博客-程序员宝宝

**场景：页面刷新出现空白，控制台报错：vue-router.esm.js?8c4f:1905 TypeError: Cannot read property ‘$route’of undefined**首先打开百度搜了一圈，很多说是语法错误，路由嵌套里面，子路由的component多了一个s。但我这里的问题都不是，一开始以为是token刷新后消失了没有保存，后来定位到了是导航守卫的问题。代码中用到了路由导航守卫：翻看官方文档：官方文档中对于beforeEnter的介绍，并没有看到我想