首页 > 试题广场 >

多多的字符变换

[编程题]多多的字符变换
  • 热度指数:5593 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解

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

  1. 交换任意两个相邻的字符,代价为0。
  2. 将任意一个字符a修改成字符b,代价为 |a - b|(绝对值)。
现在有两个长度相同的字符串X和Y,多多君想知道,如果要将X和Y变成两个一样的字符串,需要的最少的代价之和是多少。


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


输出描述:
共一行,一个整数,表示将X和Y变换成一样的字符串需要的最小的总代价。
示例1

输入

4
abca
abcd

输出

3

说明

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

输入

4
baaa
aabb

输出

1

说明

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

输入

3
abc
xyz

输出

69
l = int(input())
a = sorted(list(input()))
b = sorted(list(input()))
c = 0
for i in range(len(a)):
    c += abs(ord(a[i])-ord(b[i]))
print(c)
编辑于 2021-09-24 22:40:21 回复(1)
#include "iostream"
#include "string"
using namespace std;
int main()
{
    int len;
    string s1,s2;
    cin>>len>>s1>>s2;
    sort(s1.begin(),s1.end());
    sort(s2.begin(),s2.end());
    int num=0;
    for(int i=0;i<len;i++)
    {
        num=num+abs(s1[i]-s2[i]);
    }
    cout<<num<<endl; 
}
编辑于 2021-09-29 10:16:17 回复(0)
因为交换字符没有代价,所以将两个字符串分别排序然后逐位比较计算代价即可
#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;
    string a, b;
    cin >> a >> b;
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    int res = 0;
    for(int i = 0 ; i < n ; ++ i) {
        if(a[i] != b[i]) {
            int mu = abs(b[i] - a[i]);
            res += mu;
        }
    }
    
    cout<<res<<endl;
    return 0;
}


发表于 2021-05-10 19:52:56 回复(1)
转化成数字格式,对应指针遍历相减
n = int(input())
str_one = input()
str_two = input()
list_1 = [ord(i) for i in str_one]
list_2 = [ord(i) for i in str_two]
list_1.sort()
list_2.sort()
ans=0
for i in range(n):
    ans+=abs(list_1[i]-list_2[i])
print(ans)

发表于 2021-05-15 19:45:02 回复(1)
交换字符是不存在代价的,所以先将两个字符串的字符都修改为相同,然后再调整字符排列顺序就可以了,这个调整顺序的过程并不需要付出额外的代价。而字符串x中某个字符要修改为字符串y中的字符,代价最小的方式就是修改为排名相同的字符,即字符串x中字典序排名第k的字符修改为字符串y中字典序排名第k的字符,这样的修改才能使得整体代价最小,否则即使是这次修改为代价更小的字符,势必会造成另一个字符要付出更大的修改代价。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        char[] x = br.readLine().trim().toCharArray();
        char[] y = br.readLine().trim().toCharArray();
        Arrays.sort(x);
        Arrays.sort(y);
        int cost = 0;
        for(int i = 0; i < n; i++)
            cost += Math.abs(x[i] - y[i]);
        System.out.println(cost);
    }
}
scala版,scala运行得是真慢
import scala.io.StdIn

object Main {
    def main(args: Array[String]): Unit = {
        val n = StdIn.readInt
        val x = StdIn.readLine.trim.toCharArray.sorted
        val y = StdIn.readLine.trim.toCharArray.sorted
        var cost = 0
        for(i <- x.indices) cost += math.abs(x(i).toInt - y(i).toInt)
        println(cost)
    }
}

编辑于 2021-08-27 12:35:08 回复(0)
1.删除2个字符串中相等的字母
2.将两个字符串升序排序
3.循环相加代价:sum+=|s1[i]-s2[i]| 
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int getMinSum(string s1, string s2, int n) {
	if (n <= 0) return 0;
	/*
		1.找到两个字符串中相同的字母,
			将s1[i]='|', s2[j]='~'('|'>'z' '~'>'z')
			直接删除,还要大量移动元素,增加时间复杂度
			m:记录字母的个数
	*/
	int m = n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (s1[i] == s2[j]) {
				s1[i] = '|';
				s2[j] = '~';
				m--;
				break;
			}
		}
	}

	//2.将两个字符串升序排序
	sort(s1.begin(), s1.end());
	sort(s2.begin(), s2.end());

	//3.统计代价sum=sum+|s1[i]-s2[i]|, 0=<i<=m
	int sum = 0;
	for (int i = 0; i < m; i++) {
		int num = s1[i] - s2[i];
		sum += num > 0 ? num : (-num);
	}
	return sum;
}

int main() {
	int n;
	cin >> n;
	string s1, s2;
	cin >> s1;
	cin >> s2;
	int sum = getMinSum(s1, s2, n);
	cout << sum << endl;

	system("pause");
	return 0;
}


发表于 2021-05-14 21:09:20 回复(1)
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

                //这一题理清思路,简单地把字符串排一下序然后就可以直接相互加减了
        int N = scanner.nextInt();
        String s1 = scanner.next();
        String s2 = scanner.next();

        char[] chars1 = s1.toCharArray();
        char[] chars2 = s2.toCharArray();

        Arrays.sort(chars1);
        Arrays.sort(chars2);

        int count = 0;
        for (int i = 0; i < N; i++) {
            count += Math.abs(chars1[i] - chars2[i]);
        }
        System.out.println(count);
    }
}

发表于 2021-07-01 16:33:25 回复(0)
js版本:
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;


void async function () {
    // Write your code here
    var arr=[];
    while(line = await readline()){
        arr.push(line)
        
    }
    // console.log("arr:",arr)
    const SeqX = Array.from(arr[1]).sort().join("")
    // console.log(SeqX);
    const SeqY = Array.from(arr[2]).sort().join("")
    // console.log(SeqY);
    var result=0;

    for(var i=0;i<arr[0];i++){
        result+=Math.abs(SeqX.charCodeAt(i)-SeqY.charCodeAt(i));
    }
    console.log(result)

}()


发表于 2023-02-22 11:33:01 回复(0)
交换字符没有代价,直接将字符串每一位字符ascall码向加,再把2个字符串的ascall码和相减取绝对值即可。但是代码过不了。。。
import java.util.Scanner;
 
public class Main
{
 
    public static void main(String[] args)
    {
        int a;
        Scanner in = new Scanner(System.in);
 
        a = in.nextInt();
        String str1 = in.next();
        String str2 = in.next();
 
        char[] cs1 = str1.toCharArray();
        char[] cs2 = str2.toCharArray();
 
        int result = 0;
        int l1 = 0;
        int l2 = 0;
        for (int i = 0; i < a; i++)
        {
            l1 += cs1[i];
            l2 += cs2[i];
        }
        result = Math.abs(l1 - l2);
        System.out.println(result);
    }
}


发表于 2022-04-25 20:58:54 回复(0)
非排序做法,用字典记录两个字符串的有差异的字符,在两个字符很大的时候复杂度会小很多。
n = int(input())
s1 = input()
s2 = input()
letter_dict = {}
for char in s1:
    letter_dict[char] = letter_dict.get(char, 0) + 1
for char in s2:
    letter_dict[char] = letter_dict.get(char, 0) - 1
i = j = 'a'
cost = 0
while i <= 'z' and j <= 'z':
    # i <= 'z' and
    while i not in letter_dict&nbs***bsp;letter_dict[i] <= 0:
        i = chr(ord(i) + 1)
        if i == '{':
            break
    while j not in letter_dict&nbs***bsp;letter_dict[j] >= 0:
        j = chr(ord(j) + 1)
        if j == '{':
            break
    if j <= 'z':
        cost += abs(ord(i) - ord(j))
        letter_dict[i] -= 1
        letter_dict[j] += 1
        
# print(letter_dict)
print(cost)


发表于 2022-04-08 21:22:55 回复(0)
有手就行  
importjava.util.*;
publicclassMain
{
    publicstaticvoidmain(String[] args)
    {
        Scanner input=newScanner(System.in);
        intlen=input.nextInt();
        char[] cs1=input.next().toCharArray();
        char[] cs2=input.next().toCharArray();
        Arrays.sort(cs1);
        Arrays.sort(cs2);
        intres=0;
        for(inti=0;i<len;i++)
        {
            if(cs1[i]==cs2[i]) continue;
            res+=Math.abs(cs1[i]-cs2[i]);
        }
         
        
         
        System.out.println(res);
    }
}

发表于 2022-03-09 16:02:03 回复(0)
Python3
import string
n=int(input())
s1=input()
s2=input()
d1={}
d2={}
for i in range(n):
    d1[s1[i]]=d1.get(s1[i],0)+1
    d2[s2[i]]=d2.get(s2[i],0)+1
total=0
rest=0
for letter in string.ascii_lowercase:
    rest+=d1.get(letter,0)-d2.get(letter,0)
    total+=abs(rest)
print(total)



发表于 2021-10-29 07:46:07 回复(0)

仔细观察题目,交换是不需要代价的,那么排序就行了

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

/**
 * 
 * @date 2021/8/29 - 20:52
 */
public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int N = cin.nextInt();
        cin.nextLine();
        String str1 = cin.nextLine();
        String str2 = cin.nextLine();
        char[] chars1 = str1.toCharArray();
        char[] chars2 = str2.toCharArray();
        Arrays.sort(chars1);
        Arrays.sort(chars2);
        int res = 0;
        for (int i = 0; i < chars1.length; i++) {
            res += Math.abs((int)(chars1[i]-chars2[i]));
        }
        System.out.println(res);


    }
}
发表于 2021-08-29 21:43:44 回复(0)
package main

import (
    "fmt"
    "sort"
)

func main(){
    n := 0
    s1 := ""
    s2 := ""
    fmt.Scan(&n)
    fmt.Scanln(&s1)
    fmt.Scanln(&s2)

    fmt.Println(getSum(s1, s2))
}

func getSum(s1 string, s2 string) int {
    arr1 := []int{}
    for i := 0; i < len(s1); i ++ {
        arr1 = append(arr1, int(s1[i] - 'a'))
    }
    sort.Ints(arr1)

    arr2 := []int{}
    for i := 0; i < len(s2); i ++ {
        arr2 = append(arr2, int(s2[i] - 'a'))
    }
    sort.Ints(arr2)

    sum := 0
    for i := 0; i < len(arr1); i ++ {
        sum += abs(arr1[i], arr2[i])
    }

    return sum
}

func abs(x int, y int) int {
    if x > y {
        return x - y
    }

    return y - x
}
发表于 2021-08-22 16:06:17 回复(0)
还算比较简单,直接字符排序,计算差值
while True:
    try:
        length = int(input())
        str1 = [i for i in input()]
        str2 = [i for i in input()]
        str1.sort()
        str2.sort()
        ans = 0
        for i in range(length):
            ans+=abs(ord(str1[i])-ord(str2[i]))
        print(ans)
    except:
        break

发表于 2021-08-17 17:20:34 回复(0)
算法思想:利用贪心思想,他们肯定能通过若干次交换后,让他们全部都是从小到大进行排序,最后在求他们差值绝对值
import java.util.Scanner;
import java.util.Arrays;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        in.nextLine();
        String a = in.nextLine();
        String b = in.nextLine();
        char[] chA = a.toCharArray();
        char[] chB = b.toCharArray();
        Arrays.sort(chA);
        Arrays.sort(chB);
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += Math.abs(chA[i] - chB[i]);
        }
        System.out.println(sum);
    }
}


发表于 2021-08-11 18:09:24 回复(0)
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int n; int sum = 0;
    cin >> n;
    vector<char> a;
    vector<char> b;

    for (int i = 0; i < n; i++) {
        char s1;
        cin >> s1;
        a.push_back(s1);
        
    }
    for (int i = 0; i < n; i++) {
        char s2;
        cin >> s2;
        b.push_back(s2);

    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    for (int i = 0; i < n; i++) {
        if (a[i] != b[i]) {
            sum = sum + abs(a[i] - b[i]);
        }
    }
    cout<<sum;


    return 0;
}

发表于 2021-07-25 16:34:06 回复(0)
由于只包含小写字母,利用桶排序,创建两个长度为26的数组记录每个字母的个数,比调用Arrays.sort()快
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] str1 = new int[26];
        int[] str2 = new int[26];
        String s1 = in.next(), s2 = in.next();
        for(int i=0; i<n; ++i){
            str1[s1.charAt(i)-'a']++;
            str2[s2.charAt(i)-'a']++;
        }
        int loc1 = 0, loc2 = 0;
        int ans = 0;
        while(n>0){
            while(str1[loc1]==0) loc1++;
            while(str2[loc2]==0) loc2++;
            while(str1[loc1]>0&&str2[loc2]>0){
                ans += Math.abs(loc1-loc2);
                --str1[loc1];
                --str2[loc2];
                --n;
            }
        }
        System.out.println(ans);
        in.close();
    }
}

发表于 2021-07-17 09:58:38 回复(0)
1、将字符串转为char数组
2、用Arrays数组工具类给两个char数组排序
3、比较两个char数组,相同的字符代价为0(因为可以通过交换位置变换得到),不相同的字符取绝对值
import java.util.Scanner;
import java.util.Arrays;
public class Main{
    public static void main(String[]  args){
        Scanner input = new Scanner(System.in);
        int num = input.nextInt();
        String str1 = input.next();
        String str2 = input.next();
        if(num <= 0){
            return;
        }
        int zdj = 0;
        if(str1.length() == str2.length() && num == str1.length() ){
            char[] ch1 = str1.toCharArray();
            char[] ch2 = str2.toCharArray();
            if(str1.equals(str2)){
                System.out.println(zdj);
                return;
            }
            Arrays.sort(ch1);
            Arrays.sort(ch2);
            for(int i=0;i<num;i++){
                if(ch1[i] != ch2[i]){
                    zdj += Math.abs(ch1[i]-ch2[i]);
                }
            }
        }
        System.out.println(zdj);
    }
}

发表于 2021-06-29 16:44:19 回复(0)
不知道为什么升序就不用删除相等元素了?
public class CharChange {
    public static void main(String[] args) {
        /**
         * 因为交换字符没有代价,所以将两个字符串分别排序然后逐位比较计算代价即可
         * 为什么升序就不用删除相等元素了???
         */
        Scanner sc = new Scanner(System.in);
        int anInt = Integer.parseInt(sc.nextLine());
        String line = sc.nextLine();
        String otherStr = sc.nextLine();
        if (line.equals(otherStr)) {
            System.out.println("0");
        }
        char[] chars = line.toCharArray();
        char[] otherChars = otherStr.toCharArray();
        Arrays.sort(chars);
        Arrays.sort(otherChars);
        int sum = 0;
        for (int i=0;i<anInt;i++) {
            sum+=Math.abs(chars[i]-otherChars[i]);
        }
        System.out.println(sum);
    }
}


发表于 2021-06-21 19:50:48 回复(0)

热门推荐

通过挑战的用户