2021/3/6 字节跳动2017后端工程师实习生笔试题——最大映射

题目描述

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

输入描述

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

输出描述

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

输入示例

2
ABC
BCA

输出示例

1875

解题思路

1. 为所有的英文字母根据位置先后赋予权重，再加起来，方便后面根据排序。若在个位，则权重为 1，若在十位，则权重为 10，百位则 100，以此类推。
2. 根据排序的字母的权重，从 9 开始与权重相乘，再到 8，以此类推，最终获得结果。
3. 注意不要让 0 出现在最前面，可以存储在集合中，检查字符串的头部是否会出现 0（当出现了 10 个不同的字符时，权重最小的那个字符就会是 0）。

Java代码实现

import java.util.Scanner;
import java.util.HashSet;
import java.util.HashMap;
import java.util.Map;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int len = in.nextInt();    // 接收的行数
        String[] array = new String[len];    // 接收的所有字符串
        for (int i = 0; i < len; ++i) {
            array[i] = in.next();
        }
        long[] weight = getWeight();    // 预先计算权重，减少每次实时计算的开销
        System.out.println(getSum(weight, array));    // 得出结果
    }

    private static long[] getWeight() {
        // 因为最多有 12 位字母，所以权重也有 12 位
        // 权重从左到右依次为 {1 * 10 ^ 11, 1 * 10 ^ 10, ..., 1}
        long[] weight = new long[12];
        long priority = 1;
        weight[11] = 1;
        for (int i = 10; i >= 0; --i) {
            priority *= 10;
            weight[i] = priority;
        }
        return weight;
    }

    private static long getSum(long[] weight, String[] array) {
        HashSet<Character> head = new HashSet<Character>(); // 记录所有字符串的第一个字符，防止第一个字符数字为 0
        HashMap<Character, Long> map = new HashMap<Character, Long>(); // 字符-权重映射表
        for (int i = 0; i < array.length; ++i) {
            head.add(array[i].charAt(0));    // 记录第一个字符
            int charLen = array[i].length();    // 当前字符串长度
            int temp = 12;
            for (int j = charLen - 1; j >= 0; --j) {    // 从最后往前遍历字符
                char curChar = array[i].charAt(j);    // 当前字符
                long curWeight = weight[--temp];    // 当前权重
                if (map.containsKey(curChar)) {
                    curWeight += map.get(curChar);
                }
                map.put(curChar, curWeight);
            }
        }
        // 接下来按照权重对映射表进行排序
        ArrayList<Map.Entry<Character, Long>> list = new ArrayList<>(map.entrySet());
        Collections.sort(list, new Comparator<Map.Entry<Character, Long>>(){
            public int compare(Map.Entry<Character, Long> o1, Map.Entry<Character, Long> o2) {
                return o1.getValue() > o2.getValue() ? -1 : 1;
            }
        });

        // 如果出现了 10 个字母，那么说明必定会有 1 个字母是 0，防止这个字母出现在字符串最前面
        if (list.size() == 10) {
            int index = 9;
            while (head.contains(list.get(index).getKey())) { // 如果他在字符串最前面，就找一个没有在最前面出现过的字符放在 0 这个位置，而且尽量选择权重小的字符
                --index;
            }
            list.remove(index); // 删除了，相当于这个权重乘以 0
        }

        long sum = 0;
        int temp = 9;
        for (Map.Entry<Character, Long> entry : list) {
            sum += entry.getValue() * temp;
            --temp;
        }
        return sum;
    }
}