最大映射_字节跳动笔试题

牛客148381号

http://blog.csdn.net/yang20141109/article/details/51284495

发表于 2016-04-29 22:06:13 回复(0)

牛客691810579号

<简单代码, 一看就懂> STL只用vector

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>

using namespace std;
typedef unsigned long long ULL;

ULL maxPrj(const vector<string> &sv){
    ULL max_sum = 0;
    vector<vector<ULL> > W (10,vector<ULL>(2,0));    

    /** Calculate the W of each character **/
    for(int i=0; i<sv.size(); i++){
        //Highest digit, mark it with 1, meaning 'it can't be 0'
        W[ sv[i][0]-'A' ][1] = 1;
        for(int j=0; j<sv[i].size();  j++){
            W[ sv[i][j]-'A' ][0] += pow(10, sv[i].size()-j-1);
        }
    }
    /** Generate coding strategy **/
    sort(W.begin(), W.end(), 
            [](const vector<ULL> &a, const vector<ULL> &b){return a[0]>b[0];} ); 
    //【Handle special cases】 
    int k;
    if( W.back()[1] == 1){
        // Start from the last elem, find the smallest weight with the mark 0
        for(k=W.size()-1; W[k][1] == 1; k--);
        // Set this character to 0  (=Erase this elem)
        W.erase(W.begin()+k);
    }
    //Calculate max_sum
    for(int i=0; i<W.size(); i++){
        if( W[i][0] != 0 ) max_sum += W[i][0]*(9-i);
        else break;
    }
    return max_sum;
}

int main(){
    int n;
    cin>>n;
    cin.ignore();                  
    vector<string> sv = vector<string> (n);

    for(int i=0; i<n; i++)
        getline(cin, sv[i]);
    cout << maxPrj(sv);
    return 0;
}

编辑于 2022-03-09 19:37:38 回复(0)

小目标，500题

#include <bits/stdc++.h>
using namespace std;

vector<string> v;
vector<char> helper = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'};
int zero[26];

unsigned long long get_sum(unordered_map<char, int> mp, int i = 0){
    unsigned long long sum = 0;
    if (i == v.size()) return sum;
    for (auto &ch : v[i])
        sum = sum * 10 + mp[ch];
    return sum + get_sum(mp, i + 1);
}

int cmp(char x, char y){
    return get_sum({{x, 1}, {y, 2}}) < get_sum({{x, 2}, {y, 1}});
}

int main(){
    string temp;
    unordered_map<char, int> mp;   //最终的映射结果
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)  {
        cin >> temp;
        zero[temp[0] - 'A'] = 1;  //首字母不能为0，标记左右首字母
        v.push_back(temp);
    }
    sort(helper.begin(), helper.end(), cmp); //排序
    if (zero[helper.back() - 'A']) {  //当最后一个字符不应该为0时，
        for (int i = (int)helper.size() - 1; i >= 0; i--){
            if (zero[helper[i] - 'A'] == 0) {  //找到一个可以为0的字符z位置i
                helper.push_back(helper[i]); //将helper[i]放到末尾，让他为0
                helper.erase(helper.begin() + i); //删除多余的helper[i]
                break;
            }
        }
    }
    for (int i = 0; i < (int)helper.size(); i++) { //构建目的映射
        mp[helper[i]] = 9 - i;
    }
    cout << get_sum(mp) << endl; //计算结果
    return 0;
}

发表于 2019-09-11 03:48:46 回复(0)

🎧关键词、

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

public class Main{
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n;
        while(s.hasNext()){
            n = s.nextInt();
            String[] str = new String[n];
            Element[] e = new Element[10];
            for(int i=0;i<10;i++){
                e[i] = new Element();
            }
            for(int i=0;i<n;i++){
                str[i] = s.next();
                int l=str[i].length();
                long base = 1;
                for(int j=l-1;j>=0;j--){
                    int idx=str[i].charAt(j)-'A';
                    //如果该字母出现在首部，则标记为不能为0；即flag标记为false
                    if(j==0){
                        e[idx].flag=false;
                    }
                    e[idx].weight+=base;
                    base*=10;
                }
            }
            Arrays.sort(e, new Comparator<Element>() {
                @Override
                public int compare(Element o1, Element o2) {
                    return o1.weight>o2.weight?1:(o1.weight==o2.weight?0:-1);
                }
            });
            long sum = 0;
            //权值最低且不能为0的情况
            if(!e[0].flag){
                int k=0;
                for(;k<10;k++){
                    if(e[k].flag){
                        break;
                    }
                }
                Element tmp=e[k];
                for(;k>0;k--){
                    e[k]=e[k-1];
                }
                e[0]=tmp;
            }
            //权值越大映射的值越大
            for(int i=9;i>=0;i--){
                sum+=e[i].weight*i;
            }
            System.out.println(sum);
        }
    }
    static class Element{
        //表示权值
        long weight=0;
        //表示该字母是否可以为0 false表不可以为0；true表可以为0
        boolean flag=true;
    }
}

参考：https://blog.csdn.net/yylxid/article/details/51433911

发表于 2018-08-08 22:32:55 回复(0)

D_L

就是利用权重来计算

输入例子：

ABC

BCA

设 table = A B C D E F G H I J

个位权值为 1

十位权值为 10

百位权值为 100

依次类推，没有出现的字母权值为 0

则 A 的权重为 100 + 1 = 101

B 的权重为 10 + 100 = 110

C 的权重为 1 + 10 = 11

D - J 的权重为 0

即依照 table 的字母排列顺序，权重表为

weight = 101 110 11 0 0 0 0 0 0

进而得到

映射值表

ret = 8 9 7 0 0 0 0 0 0

将 (权重表 x 映射表)，然后再累加起来就是题目要的答案

则这些数的和为 (101 * 8) + (110 * 9) + (11 * 7) + 0 + ... + 0 = 1875

具体细节和实现代码如下

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <math.h>
#include <assert.h>
#include <cstring>
using namespace std;

typedef unsigned long long ULL; // 最大要计算 12 位的正整数，所以还是用一个大点的类型吧

// 依据权重表 weight, 得到映射表 ret (即: 排位)
// 比如：
//
// | table |  A     |    B     | C  | D      | E     | F    | G | H   | I   | J    |
// |-------|--------|----------|----|--------|-------|------|---|-----|-----|------|
// | weight|10000001| 1010001  | 20 | 100000 | 10000 | 1000 | 1 | 100 | 110 | 1000 |
// |-------|--------|----------|----|--------|-------|------|---|-----|-----|------|
// | ret   |  9     |   8      |  1 |    7   |   6   |   5  | 0 |  2  |  3  |   4  |
//
void map_weight(ULL* weight, int* ret, const int n = 10) {
    //
    // 排位算法：
    // 初值都为 9  
    // C(10, 2) : 从10个数中挑选两个数。
    // 比较这两个数：谁小谁减一，相等的话随便挑选一个减一
    //
    assert(n == 10);
    for (int i = 0; i < n; ++i) {
        ret[i] = 9;
    }

    for (int i = 0; i < n; ++i) {
        if (weight[i] == 0) {
            ret[i] = 0;
            continue;
        }
        for (int j = i + 1; j < n; ++j) {
            if (weight[j] == 0) { 
                ret[j] = 0;
                continue;
            }
            if (weight[i] < weight[j]) {
                ret[i]--;
            }
            else {
                ret[j]--;
            }
            // 因为映射不能重复，
            // 所以当 weight[i] == weight[j] 权重相等时，
            // 随意挑选一个减一即可。
            // 例如： 'A' 和 'B' 权重值相等，但不能都映射为 9
            // 此时，随意挑选一个使其映射值 减一 即可 9, 8
        }
    }
}

// 判断给定的字符 c 是否在 input 中有作为首字符出现
bool is_header(const char c, const vector<string>& input) {
    const size_t len = input.size();
    for (size_t i = 0; i < len; ++i) {
        if (c == input[i][0])
            return true;
    }
    return false;
}

// 依据给定的值，在映射表 ret 中查找对应的下标 (可进一步优化)
int get_pos(const int value, const int* ret, const int n = 10) {
    for (int i = 0; i < n; ++i) {
        if (value == ret[i])
            return i;
    }
    return -1;
}

// 因为不能有 0 开头的数字，所以要修正一下映射表 ret
void fixed_ret(int *ret, char *table, const vector<string>& input, 
        const int n = 10) {
    int pos_0 = get_pos(0, ret);
    assert(pos_0 >= 0);

    if (! is_header(table[pos_0], input)) return;
    // 当前序列需调整

    // 依次查找 最小非开头的映射值 i
    int opt_pos = -1;
    for (int i = 1; i < n; ++i) {
        int pos = get_pos(i, ret);
        assert(pos >= 0);
        if (! is_header(table[pos], input)) {
            // 找到了最小的不是 table[pos] 打头的值 i 了
            // 记下下标即可
            opt_pos = pos;
            break;
        }
    }
    if (opt_pos == -1) { 
        // 没有找到合适的值。（用例有问题）
        return; 
    }

    // 调整开始
    //  比 ret[opt_pos] 小的值都加1，最后再将 ret[opt_pos] 置 0
    for (int i = 0; i < n; ++i) {
        if (ret[i] < ret[opt_pos]) {
            ret[i]++;
        }
    }
    ret[opt_pos] = 0;
}

template<typename T>
void show(const T& arr) {
    for (auto& v : arr) {
        cout << v << ' ';
    }
    cout << endl;
}

void check(const string& input_str) {
    for (auto& s : input_str) {
        assert(s >= 'A' && s <= 'J');
    }
}

int main() {
    int n;
    cin >> n;
    assert(n > 0 && n <= 50);
    vector<string> input(n);
    
    for (int i = 0; i < n; ++i) {
        cin >> input[i];
        const size_t len = input[i].size();
        assert(len <= 12);
        check(input[i]);
    }
    // 输入完毕，并完成合法性检查

    
    char table[] = {'A', 'B', 'C', 'D', 'E', 
                    'F', 'G', 'H', 'I', 'J'};
    ULL weight[10] = {0}; // 权重表：A - J 每个字母的权重

    // 遍历 input[], 统计权重 
    // 算法：
    //
    // 设
    // 个位权值 为 1
    // 十位权值 为 10
    // 百位权值 为 100
    // 依次类推， 没有出现的字母权值为 0
    //
    // 统计每个字母的累计权重值
    //
    // 例如输入两组数据：
    //
    // ABC
    // BCA
    //
    // 则 A 的权重为 100 + 1  = 101
    // B 的权重为    10 + 100 = 110
    // C 的权重为    1 + 10   = 11
    // D - J 的权重为   0
    //
    //
    for (int i = 0; i < n; ++i) {
        ULL w = pow(10, input[i].size() -1);
        for (auto& v : input[i]) {
            weight[v - 'A'] += w;
            w /= 10;
        }
    }

#ifdef DEBUG
    cout << endl << "weight = ";
    show(weight);
#endif //DEBUG

    // 依据权重高低依次映射 9 ~ 0
    //
    // 将统计而来的 权重表进行 排位，最高权重的映射为 9， 
    // 最小权重的映射为 0。
    int ret[10];
    map_weight(weight, ret, 10);

#ifdef DEBUG
    cout << "ret = ";
    show(ret);
#endif //DEBUG

    // 修正 映射表， 因为 不能有 0 开头的数字
    //
    // 算法：检查当前映射表中 ret ，映射为 0 的字母是否在 input 中打头
    // 若不打头什么也不做；
    // 若打头，则将不打头的最小映射值 变更为 0， 
    // 比刚才发现的最小映射值小的所有映射值加 1
    //
    // 比如 映射表为 9 1 0 7 8 6 2 5 4 3
    // 此时 0 对应的字母是 talble[2] 即 'C'
    // 如果 'C' 有当过头字母，则需要修正映射表，
    // 再如， 'B' 也出现过打头，但 'G' 没有出现过打头的情况，则映射表修正如下
    // 9 2 1 7 8 6 0 5 4 3
    //
    fixed_ret(ret, table, input);

#ifdef DEBUG
    cout << "after fixed:\nret = ";
    show(ret);
#endif //DEBUG

    // 计算结果
    //
    // 将 (权重表 x 映射表)，然后再累加起来就是题目要的答案
    //
    // 例如
    //
    // 输入例子：
    // ABC
    // BCA
    //
    // 设 table = A B C D E F G H I J
    //
    // 则
    // 权重表
    // weight = 101 110 11 0 0 0 0 0 0 0
    // 进而得到
    // 映射值
    // ret    = 8    9   7 0 0 0 0 0 0 0
    //
    // 则这些数的和为
    //
    //  (101 * 8) + (110 * 9) + (11 * 7) = 1875 
    //
    ULL sum = 0;
    for (int i = 0; i < 10; ++i) {
        sum += ((ULL)weight[i] * (ULL)ret[i]);
    }

    cout << sum << endl;

    return 0;
}

发表于 2016-06-04 17:43:12 回复(5)

loolroco

#include<iostream>
#include<vector>
#include<string>
#include<set>
#include<algorithm>
#include<map>
using namespace std;

bool cmp(pair<char, long>a, pair<char, long>b){
    return a.second > b.second;
}

int main(){
    int n;
    while(cin>>n){
        map<char, long long>m;
        set<char> f; //保存首字母
        for(int i=0;i<n;i++){
            string s;
            cin>>s;
            long long b = 1;
            for(string::reverse_iterator i=s.rbegin();i<s.rend();i++){
                m[*i] += b;
                b *= 10;
            }
            f.insert(s[0]);
        }
        vector<pair<char, long long> >v(m.begin(), m.end());
        sort(v.begin(), v.end(), cmp);
        int i = v.size() - 1;
        // 所有字母出现时，找到没有出现在首字母中权重最小的字母
        while(v.size()==10 && i>=0 && f.find((v[i]).first)!=f.end()){
            i--;
        }
        unsigned long long res = 0;
        if(i!=(v.size()-1)){
            // 最小字母赋值0，删除即可
            v.erase(v.begin() + i);
        }
        int b = 9;
        for(int i=0;i<v.size();i++){
            res += b * v[i].second;
            b--;
        }
        cout<<res<<endl;
    }
    return 0;
}

发表于 2016-08-16 11:25:10 回复(2)

Alex-大伟

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Scanner;

public class DailyNews1 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner = new Scanner(System.in);
		while (scanner.hasNext()) {
			int n = scanner.nextInt();
			String[] strs = new String[n];
			for (int i = 0; i < n; i++) {
				strs[i] = scanner.next();
			}
			System.out.println(maxSum(n, strs));
		}
	}

	public static long maxSum(int n, String[] strs) {
		long sum = 0; // 返回的最大和
		HashMap<Character, Long> map = new HashMap<Character, Long>();
		ArrayList<Character> headList = new ArrayList<Character>();
		for (int i = 0; i < n; i++) {
			setWeight(strs[i], map, headList);
		}
		// 按照各个字符的权重进行排序
		ArrayList<Map.Entry<Character, Long>> list = new ArrayList<Map.Entry<Character, Long>>(map.entrySet());
		Collections.sort(list, new Comparator<Map.Entry<Character, Long>>() {

			@Override
			public int compare(Entry<Character, Long> arg0, Entry<Character, Long> arg1) {
				// TODO Auto-generated method stub
				return arg0.getValue() > arg1.getValue() ? -1 : 1; // 根据字符的权重进行从大到小排序
			}
		});
		int number = 9;// 最大的数字
		// 除去头元素为0的情况 办法：将权重最小的且不是头元素的第一个字符放置在映射值为0的位置
		if (list.size() == 10) {
			for (int i = 9; i >= 0; i--) {
				if (!headList.contains(list.get(i).getKey())) {// 满足权重最小的且不是头元素的第一个字符
					list.remove(i); // 去除就相当于放置在映射值为0的位置
					break;
				}
			}
		}
		for (Entry<Character, Long> entry : list) {
			sum += entry.getValue() * number;
			number--;
		}
		return sum;
	}

	// 设置每个字符串中每个字符的权重，并保存首字符
	public static void setWeight(String string, HashMap<Character, Long> map, ArrayList<Character> headList) {
		char[] cs = string.toCharArray();
		long init = 1;
		for (int i = cs.length - 1; i >= 0; i--) {
			if (map.containsKey(cs[i])) {
				map.put(cs[i], map.get(cs[i]) + init);
			} else {
				map.put(cs[i], init);
			}
			init *= 10;
		}
		headList.add(cs[0]);
	}
}

发表于 2016-10-02 17:31:44 回复(3)

Corvey

题意
给n（不超过50）个字符串，每个字符串（长度不超过12）由A-J的大写字符组成。要求将每个字符映射为0-9，使得每个字符串可以看作一个整数（不能有前导零），求这些字符串映射后得到数字的最大和值。（数据保证至少有一个字符不是任何字符串的首字母）

思路
根据字符所在的位置，累积统计每个字符的权值，从右到左权值分别为1, 10, 100, 1000.....
然后排序，从权值最小的到权值最大的依次映射为0-9，求和即为答案。

注意
由于每个字符串映射后得到的数字不能有前导零，因此需要记录哪些字符成为过首字母，成为过首字母的字符最终不能映射为0。所以排序后需要判断权值最小的字符是否成为过首字母，若是则需要从权值小到权值大找到第一个不为首字母的字符X，将它映射为0。在权值比X小的则依次晋级。

举例

	A	B	C	D	E	F	G	H	I	J
首字母	F	F	T	F	T	T	F	T	T	T
权值	100	90	80	70	60	50	40	30	20	10
映射	9	8	7	6	5	4	3	2	1	0

由于 J 成为过首字母，因此不能映射为 0

所以最终结果应为

	A	B	C	D	E	F	H	I	J	G
首字母	F	F	T	F	T	T	T	T	T	F
权值	100	90	80	70	60	50	30	20	10	40
映射	9	8	7	6	5	4	3	2	1	0

发表于 2018-03-24 12:41:27 回复(0)

LittleBaby

给字符串中的每个字符一个权重，比如：字符串 ABC ，则 A 的权重为 100 ， B 的权重为 10 ， C 的权重为 1 ，其实就是按照它们所在位置设定权重的。这样的话，经过多个字符串，每个字符就会得到多个权值，然后把每个字符串的权值加起来，最后按权值对每个字符从大到小排序。例如： ABC 和 BCA 两个字符串：

ABC ： A=100 ， B=10 ， C=1

BCA ： B=100 ， C=10 ， A=1

累加： A=100+1=101 ， B=10+100=110 ， C=1+10=11 ，按权值从大到小排序后得 B ： 110 ， A ： 101 ， C ： 11 ，可以认为有 110 个 B ，有 101 个 A ，有 11 个 C ，那么映射 B 为 9 ， A 为 8 ， C 为 7 ，则最后结果为 9*110+8*101+7*11=1875.

#include <iostream>

#include <string>

#include <cstring>

#define MAX 10// 最大字母个数

using namespace std;

string input[50];// 输入字符串

long long nums[12] = {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000,100000000000};// 权重数组

struct CountStruc{// 计数结构

char alpha;// 字母

long long count;// 权重

int num;// 映射后的数字

}countArr[MAX];

int cmp( const void *a, const void *b)// 快速排序的比较函数

{

struct CountStruc *aa = ( struct CountStruc *)a;

struct CountStruc *bb = ( struct CountStruc *)b;

return (aa->count < bb->count) ? 1 : -1;// 从大到小排序

}

int main()

{

int n;

while (cin>>n)

{

//first[] 为 hash 表，用于快速查找某个字母是否为首字母 , 因为首字母映射后不能为 0

bool first[MAX] = { false };

for ( int i=0;i<n;i++)

{

cin>>input[i];

int size = input[i].size();

for ( int j=0;j<size;j++)// 统计每个字母的权值

countArr[input[i][j]- 'A' ].alpha = input[i][j], countArr[input[i][j]- 'A' ].count += nums[size-j-1];

first[input[i][0]- 'A' ] = true ;//hash 一下

}

qsort(countArr,MAX, sizeof (countArr[0]),cmp);// 按权重排序

int zero = -1;// 标记 countArr 中哪个字母不是字符串的首字母

if (countArr[MAX-1].count>0)

{//10 个字母全部用到了

if (first[countArr[MAX-1].alpha- 'A' ])

{// 如果权值最小的字母是首字母，则需要将其向前移动

for (zero=MAX-2;zero>=0;zero--)// 找到不是首字母的字母

if (first[countArr[zero].alpha- 'A' ]== false ) break ;

countArr[zero].num = 0;// 将不是首字母的字母映射到 0

countArr[MAX-1].num = 1;// 相应地，权值最小的字母向前移一位，即映射到 1

}

for ( int i=0,k=MAX-1;i<MAX;i++)// 映射其他字母

if (countArr[i].count==0) break ;

else if (i!=zero) countArr[i].num = k--;

long long sum = 0;

for ( int i=0;i<MAX;i++)// 累加和

sum += countArr[i].count*countArr[i].num;

cout<<sum<<endl;

memset(countArr,0, sizeof (countArr));// 一定要清空

}

return 0;

}

发表于 2016-09-01 23:57:29 回复(1)

牛客143360074号

也来贴一个Python3的代码：

coeffs = [[0, 0] for _ in range(10)]
for _ in range(int(input())):
    card = input()
    coeffs[ord(card[0]) - ord('A')][1] = 1
    for i, c in enumerate(card[::-1]):
        coeffs[ord(c) - ord('A')][0] += 10 ** i
coeffs.sort()
if coeffs[0][1] == 1:
    for i in range(1, len(coeffs)):
        if coeffs[i][1] == 0:
            coeffs[i][0] = 0
            break
print(sum(i*c[0] for i, c in enumerate(sorted(coeffs))))

加和可以表示为 $\sum\limits_{i=0}^9 x_i t, \ t \in \{A,B,\cdots,J\}$
coeffs 为记录 A - J 的参数、是否可在首位的二元组。第一个循环对其进行赋值后排序，这样排在首位、末位的二元组第一个元素对应 A、J 的系数，但排在首位的二元组第二个元素可能为 1，也就是说这个元素不能映射成 0，需要与后续元素对调，依次向后循环找到二元组第二个元素为 0 的元素即可。

发表于 2022-01-27 23:42:08 回复(0)

keeplaceforme

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<string> vs(n);
    for (int i = 0; i < n; ++i) {
        cin >> vs[i];
    }
    
    unordered_map<char, long long> cnt;
    unordered_map<char, bool> isHead;
    
    for (auto& s : vs) {
        int m = s.size();
        isHead[s[0]] = 1;
        
        long long j = 1;
        for (int i = m - 1; i >= 0; --i) {
            cnt[s[i]] += j;
            j *= 10;
        }
    }
    
    string s = "ABCDEFGHIJ";
    sort(s.begin(), s.end(), [&](char l, char r) {
        return cnt[l] > cnt[r];
    });
    
    if (s[9] > 0 && isHead[s[9]]) {
        int i;
        for (i = 8; i >= 0; --i) {
            if (!isHead[s[i]]) {
                break;
            }
        }
        string s1 = s.substr(0, i);
        string s2 = s.substr(i + 1, 9 - i);
        s2.append(1, s[i]);
        s = s1 + s2;
    }
    
    long long ans = 0;
    long long k = 9;
    for (auto c : s) {
        ans += k * cnt[c];
        k --;
    }
    cout << ans<< endl;
    return 0;
}

发表于 2021-08-18 20:56:27 回复(0)

jeffcheng

#include <iostream>
#include <vector> 
#include <algorithm>
#include <map>
#include <unordered_set>
using namespace std; 
typedef long long ll; 

bool cmp(pair<char, ll> a, pair<char, ll> b){
    return a.second > b.second; 
}
    

int main(){
    int n ; 
    cin >> n; 
    vector<string> v; 
    vector<pair<char, ll>> collection; 
    unordered_set<char> head; 
    
    while(n --) {
        string s; 
        cin >> s; 
        v.push_back(s); 
    }
    
    map<char, ll> hash; 
    
    for(auto &i : v) head.insert(i[0]);  
    
    for(auto &x : v) {
        auto tmp = x ;
        reverse(tmp.begin(), tmp.end()); 
        ll weight = 1;
        for(auto& c : tmp) {
            hash[c] += weight;
            weight *= 10; 
        }
    }
    
    for(auto x : hash) 
        collection.push_back({x.first, x.second}) ;
    
    sort(collection.begin(), collection.end(), cmp); 
    
    
    if(hash.size() == 10) {
        int index = 9; 
        while(head.count(collection[index].first)) index--; 
        collection[index].second = 0;
        
        
    }
    sort(collection.begin(), collection.end(), cmp); 

    ll res = 0, start = 9; 
    
    for(int i = 0; i < collection.size(); i++) {
            res += start * collection[i].second; 
            start--;
    }
    
    
    cout << res;
}

发表于 2021-03-06 15:41:39 回复(0)

无味的辣椒酱

import java.math.BigInteger;
import java.util.*;

/**
 * @author Erwei
 * @create 2020/7/15 at 9:38
 */

public class Main{

    private static class Com implements Comparator<Map.Entry<Character, Long>> {
        @Override
        public int compare(Map.Entry<Character, Long> o1, Map.Entry<Character, Long> o2) {
            return o1.getValue() > o2.getValue() ? 1 : -1;
        }
    }
    static Map<Character, Long> count;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        try {
            while (in.hasNext()) {
                int n = in.nextInt();
                in.nextLine();
                ArrayList<String> ary = new ArrayList<>();
                ArrayList<Character> zero = new ArrayList<>();
                Map<Character, Integer> map = new HashMap<>();
                count = new HashMap<>();
                init();
                for (int i = 0; i < n; i++) {
                    String s = in.nextLine();
                    zero.add(s.charAt(0));
                    ary.add(s);
                }

                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < ary.get(i).length(); j++) {
                        count.replace(ary.get(i).charAt(j), count.get(ary.get(i).charAt(j)) + (long) Math.pow(10,(double)(ary.get(i).length() - j)));
                    }
                }

                List<Map.Entry<Character,Long>> list = new ArrayList<>();
                list.addAll(count.entrySet());

                Com com = new Com();
                Collections.sort(list,com);

                Iterator<Map.Entry<Character,Long>> it = list.iterator();
                for (int i = 0; it.hasNext();) {
                    Map.Entry<Character, Long> c = it.next();
                    Character cha = c.getKey();
                    if (!zero.contains(cha)){
                        map.put(cha,i);
                        list.remove(c);
                        break;
                    }
                }

                Iterator<Map.Entry<Character,Long>> its = list.iterator();
                for (int i = 1; its.hasNext(); i++) {
                    map.put(its.next().getKey(),i);
                }

                BigInteger sum = new BigInteger("0");
                for (int i = 0; i < n; i++) {
                    String s = "";
                    for (int j = 0; j < ary.get(i).length(); j++) {
                        s += map.get(ary.get(i).charAt(j)).toString();
                    }
                    BigInteger big = new BigInteger(s);
                    sum = sum.add(big);
                }
            }
        }catch (Exception e){
            e.printStackTrace();
        }
    }

    public static void init() {
        count.put('A',0L);
        count.put('B',0L);
        count.put('C',0L);
        count.put('D',0L);
        count.put('E',0L);
        count.put('F',0L);
        count.put('G',0L);
        count.put('H',0L);
        count.put('I',0L);
        count.put('J',0L);
    }

}

编辑于 2020-07-15 10:38:01 回复(1)

人生要有trycatch

<p>能想到的比较简单的思路就是创建几个数组，依次存放不同单位的字符串，然后根据字符串中某字符出现次数，按照频率以及数组本身代表单位，按照9-1的顺序赋值</p>

发表于 2020-07-13 12:05:15 回复(0)

C/C++

NIMEI583

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <utility>
#include <algorithm>
#include <set>

using namespace std;

bool compare(const pair<char,long long> &p1, const pair<char, long long> &p2){
    return p1.second>p2.second;
}

int main()
{
    int N;
    cin>>N;
//    vector<string> vs;
    set<char> zero;
    map<char,long long> times;
    for(int i = 0; i < N; ++i){
        string temp;
        cin>>temp;
        zero.insert(temp[0]);
        long long factor=1;
        for(int j = temp.size()-1; j >= 0; --j){
            times[temp[j]]+=factor;
            factor*=10;
        }
    }
    vector<pair<char,long long>> vp(times.begin(),times.end());
    sort(vp.begin(),vp.end(),compare);
    int index=vp.size()-1;
    bool pre_zero=false;
    for(; index >= 0; --index){
        if(zero.find(vp[index].first) != zero.end()){
            pre_zero=true;
            continue;
        }
        break;
    }
    if(pre_zero && index != -1){
        auto temp=vp[index];
        vp.erase(vp.begin()+index);
        vp.push_back(temp);
    }
    int sz=vp.size();
    long long result = 0;
    long long cnt=9;
    for(int i = 0;i < sz; ++i){
        long long temp = cnt*vp[i].second;
        result += temp;
        --cnt;
    }
    cout<<result;
    return 0;
}

发表于 2019-09-15 10:10:14 回复(0)

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)

海贼宅～

参考了前面大佬的思路，才想到权重
python3.x实现
去掉注释，感觉代码量还是很少的

# 权重映射字典，记录每个字符的总权重
weight_dict = {
    'A': 0, 'B': 0, 'C': 0,
    'D': 0, 'E': 0, 'F': 0,
    'G': 0, 'H': 0, 'I': 0,
    'J': 0
}
# 生成9-0依次递减的数组
nums = list(range(10))[::-1]

def make_weight(*args):
    """
    生成每个字符的权重
    :param args: 输入的字符串列表
    思路：
        1 把字符串翻转，翻转后的下标对应权重幂数
            >> ABC --> CBA
            >> 012     012
            A的权重：10^2
            B的权重：10^1
            C的权重：10^0
        2 分别计算每个字符串中，每个字符的权重，
            用字典键的唯一性作为索引
            累加每个字符的权重
    """
    for str_i in args:
        new_str = str_i[::-1]
        for i,letter in enumerate(new_str):
            weight_dict[letter] += pow(10,i)

def get_max_val():
    """
    利用权重计算最大值
    :return:
    """
    val = 0
    # 把权重按从大到小排列
    values = list(weight_dict.values())
    values.sort(reverse=True)
    #
    for i, num in enumerate(values):
        val += num * nums[i]
    return val


if __name__ == "__main__":
    # 提示用户输入
    n = input("请输入行数n: ")
    args = []
    count = 1
    while int(n) >= count:
        args.append(input("请输入第一行字符串：").upper())
        count += 1
    # 生成权重获，获取最大值
    make_weight(*args)
    result = get_max_val()
    print(weight_dict)
    print(result)

发表于 2019-08-08 17:03:39 回复(0)

努力搬砖的小辉

这个测试是不是有问题呀，系统说不通过的用例，我在自己编译器运行结果和系统说的正确输出一样。两道题都是这样。

发表于 2019-05-05 17:09:41 回复(0)

司马元朗

//将字符abcdefghij映射为0 ~ 9数字 让字符adcdefghij位置固定不变，变换0~9数字与之去匹配 
//在首字母不能是0的情况下 最终选出累加和最大的
//生成0~9的全排列 就是字符映射成数值的所有情况 
//在所有全排列中排除首字母为0的 然后去计算每种情况下的累加和 选出最大的
//超时 这种思想只能过百分之30

#include <iostream>
#include <vector>
#include <string>
#include <assert.h>

using std::vector;
using std::string;

long long ComputeMappingSum(const vector<int>& digits, const vector<string>& strs)
{
    //abcdefghij ~ digitsIdx(0 ~ 9)
    assert(digits.size() == 10 && !strs.empty());
    int zeroIdx = -1;
    for (int i = 0; i < digits.size(); ++i)
    {
        zeroIdx = digits[i] == 0 ? i : -1;
    }
    //assert(zeroIdx != -1);
    for (const auto& str : strs)
    {
        if (str[0] - 'A' == zeroIdx)
        {
            return -1;
        }
    }
    long long sum = 0;
    for (const auto& str : strs)
    {
        long long num = 0;
        for (char ch : str)
        {
            num = num * 10 + digits[ch - 'A'];
        }
        sum += num;
    }
    return sum;
}

long long MappingProcess(vector<int>& digits, int i, const vector<string>& strs)
{
    if (i == digits.size())
    {
        return ComputeMappingSum(digits, strs);
    }
    long long maxSum = 0;
    for (int s = i; s < digits.size(); ++s)
    {
        std::swap(digits[s], digits[i]);
        maxSum = std::max(maxSum, MappingProcess(digits, i + 1, strs));
std::swap(digits[s], digits[i]);
    }
    return maxSum;
}

long long MaxMapping(const vector<string>& strs)
{
    vector<int> digits(10);
    for (int i = 0; i < 10; ++i)
    {
        digits[i] = i;
    }
    return MappingProcess(digits, 0, strs);
}

int main(void)
{
    int n;
    std::cin >> n;
    vector<string> strs(n);
    for (int i = 0; i < n; ++i)
    {
        std::cin >> strs[i];
    }
    std::cout << MaxMapping(strs) << std::endl;

    return 0;
}

发表于 2019-05-04 14:47:17 回复(0)

Python

W²²

发表于 2019-04-19 05:52:46 回复(0)

最大映射

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题