今日头条笔试题--最大映射

Posted on

问题描述

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

输入描述

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

输出描述

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

示例 1

输入

1
2
3
2
ABC
BCA

输出

1
1875

解题思路

我们可以通过计算权值，把权值最高的映射成9，次之映射成8，以此类推。

例如：
ABC
A的权值为100，B的权值为10，C的权值为1————①
BCA
B的权值为100，C的权值为10，A的权值为1————②
①②权值相加
A的权值为101，B的权值为110，C的权值为11
110 × 9 + 101 × 8 + 11 × 7 = 1875

但是我们要注意前导零。当把一个字符映射成0时，检查是否出现在最高位，如果出现则找上一个字符，直到找到权重最小的又不会出现在最高位的字符，把这个字符映射成0，其他字符按序映射。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
package main

import (
	"fmt"
	"math"
	"sort"
)

type node struct {
	key string
	val int64
}

type nodes []node

func (n nodes) Len() int {
	return len(n)
}

func (n nodes) Swap(i, j int) {
	n[i], n[j] = n[j], n[i]
}

func (n nodes) Less(i, j int) bool {
	return n[i].val > n[j].val
}

func main() {
	n := 0
	fmt.Scanf("%d", &n)
	m := make(map[string]int64)
	head := make(map[string]struct{})
	for i := 0; i < n; i++ {
		tmp := ""
		fmt.Scanf("%s", &tmp)
		head[string(tmp[0])] = struct{}{}
		for key, value := range tmp {
			m[string(value)] = m[string(value)] + int64(math.Pow10(len(tmp)-key-1))
		}
	}
	l := make(nodes, 0, 10)
	for i := range m {
		n := node{
			key: i,
			val: m[i],
		}
		l = append(l, n)
	}
	sort.Sort(l)
	p := []int64{9, 8, 7, 6, 5, 4, 3, 2, 1, 0}
	if len(l) == 10 {
		for i := len(l) - 1; i >= 0; i-- {
			_, ok := head[l[i].key]
			if ok {
				continue
			} else {
				p[i] = 0
				for k := i + 1; k < len(p); k++ {
					p[k] += 1
				}
				break
			}
		}
	}
	var ans int64 = 0
	for i := len(l) - 1; i >= 0; i-- {
		ans = ans + l[i].val*p[i]
	}
	fmt.Println(ans)
}