首页 > 试题广场 >

最大映射

[编程题]最大映射

热度指数：4995 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

有 n 个字符串，每个字符串都是由 A-J 的大写字符构成。现在你将每个字符映射为一个 0-9 的数字，不同字符映射为不同的数字。这样每个字符串就可以看做一个整数，唯一的要求是这些整数必须是正整数且它们的字符串不能有前导零。现在问你怎样映射字符才能使得这些字符串表示的整数之和最大？

输入描述:

每组测试用例仅包含一组数据，每组数据第一行为一个正整数 n ，接下来有 n 行，每行一个长度不超过 12 且仅包含大写字母 A-J 的字符串。 n 不大于 50，且至少存在一个字符不是任何字符串的首字母。

输出描述:

输出一个数，表示最大和是多少。

示例1

输入

2
ABC
BCA

输出

算法知识视频讲解

Java

kakifuu

import java.util.*;

public class Main {

    private void sln() {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long sum = 0;
        // 两个元素分别对应 总权重、是否作过首字母
        long[][] rec = new long[10][2];
        for (int i = 0; i < n; i++) {
            String str = sc.next();
            char[] chars = str.toCharArray();
            // 从低位看到高位
            for (int j = 1; j <= chars.length; j++) {
                int index = chars[chars.length - j] - 'A';
                long weight = (long) Math.pow(10, j - 1);
                rec[index][0] += weight;
                if (j == chars.length) rec[index][1] = 1;
            }
        }
        // 按总权重排序
        Arrays.sort(rec, Comparator.comparing(a -> a[0]));
        // 要分配的数字 0-9
        int[] digits = new int[10];
        for (int i = 0; i < 10; i++) digits[i] = i;
        // 作过首字母的话就把0和后面数字交换
        for (int i = 0; i < 10; i++) {
            if (rec[i][1] == 1) {
                int temp = digits[i];
                digits[i] = digits[i + 1];
                digits[i + 1] = temp;
            } else break;
        }
        // 每个字母的总权重 乘上 对应数字
        for (int i = 0; i < 10; i++) {
            sum += rec[i][0] * digits[i];
        }
        System.out.println(sum);
    }

    public static void main(String[] args) {
        new Main().sln();
    }
}

编辑于 2019-08-09 17:05:37 回复(0)

Java

菜包子的噪声

import java.util.*;

public class Main{
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
scan.nextLine();

String[] strings = new String[n];
HashSet<Character> set = new HashSet<>();
HashMap<Character, Long> map = new HashMap<>(n+1, 1);
for(int i=0; i<n; i++){
strings[i] = scan.nextLine();
long val = 1;
for(int j=strings[i].length()-1; j>=0; j--){
char tmp = strings[i].charAt(j);
map.put(tmp, map.get(tmp)==null?val:map.get(tmp)+val);
val*=10;
if(j==0){
set.add(tmp);
}
}
}

ArrayList<Map.Entry<Character, Long>> list = new ArrayList<>(map.entrySet());
Collections.sort(list, (a, b)-> a.getValue()<b.getValue()?1:-1);

if(set.contains(list.get(list.size()-1).getKey())){
int i=list.size()-2;
while(i>=0 && set.contains(list.get(i).getKey())){
i--;
}
while(i>=0 && i<list.size()-1){
Map.Entry<Character, Long> tmp = list.get(i+1);
list.set(i+1, list.get(i));
list.set(i, tmp);
i++;
}
}

long[] dict = new long[10];
for(int i=0; i<list.size(); i++){
dict[list.get(i).getKey()-'A'] = 9-i;
}

long sum=0, val=0;
for(int i=0; i<n; i++){
val=0;
for(int j=strings[i].length()-1; j>=0; j--){
sum += dict[strings[i].charAt(j) - 'A']* Math.pow(10, val++);
}
}
System.out.println(sum);
}
}

发表于 2019-01-10 14:55:57 回复(0)