微软笔试题《Arithmetic Puzzles》- 题解

这个题是hiho一下第73周的一个题目，微软的一个笔试题，题目链接：点这里.

这题代码量大，时间也挺短的，而且还要想出几种剪枝，要求挺高的.
　
　
题目：

给定一个由字母组成的等式，其中每一个字母表示一个数字。不同字母表示的数字一定不同。问字母和数字之间是否存在一一对应关系，使得等式成立。若存在多种方案输出按字母顺序排列后字典序最小的解。

比如 SEND+MORE=MONEY 的一个解为 9567+1085=10652。

解析：

首先明确下思路，这题只能暴力搜索搞，问题是解的组合最多有10！，搜索肯定就超时了，因此需要剪枝，这题的精髓也就在这里.这个题还融合了大整数加减法在递归中，确实有些难度.

从题目中可以看出下面两个判定条件：

• 字母种类大于10，无解
• 单词长度大于1，首字母不能为0

于是有下面两个函数,一个得到这串等式中字母种类数，一个得到取值不能为0的字母集合：

int getAlphaNumber(string str)
{
    set<char> se;
    for (decltype(str.size()) i = 0; i < str.size(); i++) {
        if (str[i] != '=' && str[i] != '+')
            se.insert(str[i]);
    }
    return (int)se.size();
}

void getIsLeadZero(vector<bool> &isLeadZero, vector<string> words)
{
    for (decltype(words.size()) i = 0; i < words.size(); i++)
        isLeadZero[words[i][0] - 'A'] = !isLeadZero[words[i][0] - 'A'] ? false : words[i].size() == 1 ? true : false;
}

然后我们要得到各个单词，最直接的想法就是，把等式两边都算一下，最后比较是否相等，这样做有一个不好的地方，就是等式两边都要全部计算完后才能判断，那有没有一种方法可以在计算的过程中就判断是否合法，如果不合法就直接不计算了呢，有的，把单词全移到等式的一边，就变成了AA+BB-CC=0，这样，我们在手算大整数加法的时候只需要判断当前位的所有数字全部加起来的和是否为0，如果不为0那就不合法，最后在递归终点的时候再判断下进位是不是0，如果不是0，那也不合法；

但是这样做又带来了新的问题，我们手算大整数加减法的时候是个位开始的，而这个题要输出字典序最小的答案，很矛盾啊，但是仔细想想，这种剪枝确实有效，如果不这样搞，我们要把所有答案递归完才知道可不可能，而这么搞可以在递归答案过程中快速去掉不合法的答案，所以还是很有效的，至于字典序最小，我们可以去维护一个字典序最小的答案嘛.

下面一个函数的功能是提取单词和加减号，因为等式移边是要变号的：

void getWordsAndOperator(vector<string> &words, vector<int> &ope, string strs)
{
    decltype(strs.size()) equalCharPos = strs.find("="), src = 0;
    for (; ;) {
        decltype(src) des = strs.find("+", src);
        if (des > equalCharPos || des == string::npos) {
            des = equalCharPos;
            words.push_back(strs.substr(src, des - src));
            ope.push_back(1);
            src = des + 1;
            break;
        }
        words.push_back(strs.substr(src, des - src));
        ope.push_back(1);
        src = des + 1;
    }

    for (; ;) {
        decltype(src) des = strs.find_first_of("+", src);
        if (des == string::npos)
            break;
        words.push_back(strs.substr(src, des - src));
        ope.push_back(-1);
        src = des + 1;
    }
    words.push_back(strs.substr(src));
    ope.push_back(-1);
}

最后一个剪枝，我是没有注意到这个剪枝的，这还是参考了官方的解析。

考虑这么一种情况，ABBBBB +D+E= CBBBBBB + D.

这里D和B取任何值对等式都是没有影响的，我们叫它无用字母(官方解释这么叫的)，因此我们枚举的时候可以不枚举这两个字母，令它们的值为0，这样，可以快速跳过很多递归，如果这样搞最后答案是合法的，那我们就在没有用完的数字集合中依次选择最小的数字填充这两个字母就好了.

那问题来了，这些字母如何求啊，我一开始也没想到很好的求法，总是会漏很多这样的字母，但是感觉又没办法解决，后来究其根本原因是我把这些字母放在了整个字符串中去考虑，正解应该是把这些字母放在某一位上去考虑，每一位的这些字母都是独立的.

什么意思呢，看这种情况，ABC+C=C+BB.你能说C是无用字母吗？不能，如果你不枚举C，那么ABC怎么办，你能说B不是无用字母吗？也不能，在枚举十位上的数字时，B确实没有用处啊(两个B消去了)。

所以啊，我们对每一位都维护一个无用字母集合，当且仅当当前位的字母在当前无用字母集合中时才不枚举当前字母。。。我自己都觉得拗口，这样就完美解决了这个问题，看看啊，在个位，B不是无用字母，因此要枚举，在十位，B是无用字母，因此不用枚举，这样在整个大整数加减法递归完后，B是有值的，因此用B的值去填充十位上的B(十位上的B的值可以任意嘛).

下面是完成这个剪枝功能的预处理函数：

void getNotVisitAlpha(vector<string> words, vector<int> ope, vector<set<char> > &notVisitAlpha, int maxLen, int wordsNum)
{
    for (int j = 0; j < maxLen; j++) {
        map<char, int> mp;
        for (int i = 0; i < wordsNum; i++) {
            if (j >= words[i].size())
                continue;
            mp[words[i][words[i].size() - 1 - j]] += ope[i];
        }
        for (auto element : mp) {
            if (element.second == 0)
                notVisitAlpha[j].insert(element.first);
        }
    }
}

下面的这个dfs就是大整数加法枚举计算了，没什么技巧，注意细节就是了，不要搞蒙了，变量确实多.

bool dfs(vector<string> &words, vector<int> &ope, vector<bool> &isLeadZero, vector<set<char> > &notVisitAlpha,
        int row, int col, int sum,
        map<char, int> &ans, vector<bool> &used,
        const int maxLen, const int wordsNum, string strs)
{
    if (col == maxLen) {
        if (!sum) {
            string nowString = strs;
            vector<bool> tmpUsed(used);
            map<char, int> theAns(ans);
            for (auto &element : nowString) {
                if (theAns.find(element) != theAns.cend())
                    element = theAns[element] + '0';
            }
            if (fillTheString(theAns, tmpUsed, isLeadZero, nowString, 0)) {
                if (theAnsString == "" || nowString < theAnsString)
                    theAnsString = nowString;
                return true;
            }
            return false;
        } else
            return false;
    }
    if (row == wordsNum) {
        if (sum % 10)
            return false;
        return dfs(words, ope, isLeadZero, notVisitAlpha, 0, col + 1, sum / 10, ans, used, maxLen, wordsNum, strs);
    }
    signed char alpha = col >= words[row].size() ? -1 : words[row][words[row].size() - 1 - col];
    if (notVisitAlpha[col].find(alpha) != notVisitAlpha[col].cend())
        alpha = -1;
    if (alpha == -1)
        return dfs(words, ope, isLeadZero, notVisitAlpha, row + 1, col, sum, ans, used, maxLen, wordsNum, strs);

    if (ans.find(alpha) != ans.cend())
        return dfs(words, ope, isLeadZero, notVisitAlpha, row + 1, col, sum + ope[row] * ans[alpha], ans, used, maxLen, wordsNum, strs);

    bool ret = false;
    for (int num = isLeadZero[alpha - 'A'] ? 0 : 1; num < 10; num++) {
        if (used[num])
            continue;

        used[num] = true;
        ans[alpha] = num;
        bool tmp = dfs(words, ope, isLeadZero, notVisitAlpha, row + 1, col, sum + ope[row] * num, ans, used, maxLen, wordsNum, strs);
        ans.erase(alpha);
        used[num] = false;

        if (tmp)
            ret = true;
    }
    return ret;
}

做到这里，这个题基本就过了，但是自己却写了挺久的，究其原因还是STL不会调试，得补补STL源码了，最后调试还是我一个一个打印出来的.

完整代码：

#include <bits/stdc++.h>

using namespace std;

string theAnsString;

int getAlphaNumber(string str)
{
    set<char> se;
    for (decltype(str.size()) i = 0; i < str.size(); i++) {
        if (str[i] != '=' && str[i] != '+')
            se.insert(str[i]);
    }
    return (int)se.size();
}

void getWordsAndOperator(vector<string> &words, vector<int> &ope, string strs)
{
    decltype(strs.size()) equalCharPos = strs.find("="), src = 0;
    for (; ;) {
        decltype(src) des = strs.find("+", src);
        if (des > equalCharPos || des == string::npos) {
            des = equalCharPos;
            words.push_back(strs.substr(src, des - src));
            ope.push_back(1);
            src = des + 1;
            break;
        }
        words.push_back(strs.substr(src, des - src));
        ope.push_back(1);
        src = des + 1;
    }

    for (; ;) {
        decltype(src) des = strs.find_first_of("+", src);
        if (des == string::npos)
            break;
        words.push_back(strs.substr(src, des - src));
        ope.push_back(-1);
        src = des + 1;
    }
    words.push_back(strs.substr(src));
    ope.push_back(-1);
}

void getIsLeadZero(vector<bool> &isLeadZero, vector<string> words)
{
    for (decltype(words.size()) i = 0; i < words.size(); i++)
        isLeadZero[words[i][0] - 'A'] = !isLeadZero[words[i][0] - 'A'] ? false : words[i].size() == 1 ? true : false;
}

void getNotVisitAlpha(vector<string> words, vector<int> ope, vector<set<char> > &notVisitAlpha, int maxLen, int wordsNum)
{
    for (int j = 0; j < maxLen; j++) {
        map<char, int> mp;
        for (int i = 0; i < wordsNum; i++) {
            if (j >= words[i].size())
                continue;
            mp[words[i][words[i].size() - 1 - j]] += ope[i];
        }
        for (auto element : mp) {
            if (element.second == 0)
                notVisitAlpha[j].insert(element.first);
        }
    }
}

bool fillTheString(map<char, int> ans, vector<bool> used, vector<bool> &isLeadZero, string &str, string::size_type index)
{
    bool ret = true;
    for (string::size_type i = 0; i < str.size(); i++) {
        if (isalpha(str[i]) && ans.find(str[i]) == ans.cend()) {
            bool isOk = false;
            for (int j = 0; j < 10; j++) {
                if ((j == 0 && isLeadZero[str[i] - 'A'] && !used[j]) || (j > 0 && !used[j])) {
                    ans[str[i]] = j;
                    used[j] = true;
                    str[i] = j + '0';
                    isOk = true;
                    break;
                }
            }
            if (!isOk) {
                ret = false;
                break;
            }
        } else if (isalpha(str[i]) && ans.find(str[i]) != ans.cend())
            str[i] = ans[str[i]] + '0';
    }
    return ret;
}

bool dfs(vector<string> &words, vector<int> &ope, vector<bool> &isLeadZero, vector<set<char> > &notVisitAlpha,
        int row, int col, int sum,
        map<char, int> &ans, vector<bool> &used,
        const int maxLen, const int wordsNum, string strs)
{
    if (col == maxLen) {
        if (!sum) {
            string nowString = strs;
            vector<bool> tmpUsed(used);
            map<char, int> theAns(ans);
            for (auto &element : nowString) {
                if (theAns.find(element) != theAns.cend())
                    element = theAns[element] + '0';
            }
            if (fillTheString(theAns, tmpUsed, isLeadZero, nowString, 0)) {
                if (theAnsString == "" || nowString < theAnsString)
                    theAnsString = nowString;
                return true;
            }
            return false;
        } else
            return false;
    }
    if (row == wordsNum) {
        if (sum % 10)
            return false;
        return dfs(words, ope, isLeadZero, notVisitAlpha, 0, col + 1, sum / 10, ans, used, maxLen, wordsNum, strs);
    }
    signed char alpha = col >= words[row].size() ? -1 : words[row][words[row].size() - 1 - col];
    if (notVisitAlpha[col].find(alpha) != notVisitAlpha[col].cend())
        alpha = -1;
    if (alpha == -1)
        return dfs(words, ope, isLeadZero, notVisitAlpha, row + 1, col, sum, ans, used, maxLen, wordsNum, strs);

    if (ans.find(alpha) != ans.cend())
        return dfs(words, ope, isLeadZero, notVisitAlpha, row + 1, col, sum + ope[row] * ans[alpha], ans, used, maxLen, wordsNum, strs);

    bool ret = false;
    for (int num = isLeadZero[alpha - 'A'] ? 0 : 1; num < 10; num++) {
        if (used[num])
            continue;

        used[num] = true;
        ans[alpha] = num;
        bool tmp = dfs(words, ope, isLeadZero, notVisitAlpha, row + 1, col, sum + ope[row] * num, ans, used, maxLen, wordsNum, strs);
        ans.erase(alpha);
        used[num] = false;

        if (tmp)
            ret = true;
    }
    return ret;
}

int main()
{
    // freopen("in", "r", stdin);

    int T;
    for (cin >> T; T-- ; ) {
        theAnsString = "";
        string strs;
        cin >> strs;

        if (getAlphaNumber(strs) > 10) {
            cout << "No Solution" << endl;
            continue;
        }

        vector<string> words;
        vector<int> ope;
        vector<bool> isLeadZero(26, true);

        getWordsAndOperator(words, ope, strs);
        getIsLeadZero(isLeadZero, words);

        int maxLen = 0, wordsNum = words.size();
        for (auto element : words)
            maxLen = max(maxLen, (int)element.size());

        vector<set<char> > notVisitAlpha(maxLen);
        getNotVisitAlpha(words, ope, notVisitAlpha, maxLen, wordsNum);

        map<char, int> ans;
        vector<bool> used(10, false);
        if (dfs(words, ope, isLeadZero, notVisitAlpha, 0, 0, 0, ans, used, maxLen, wordsNum, strs)) {
            cout << theAnsString << endl;
        } else {
            cout << "No Solution" << endl;
        }
    }
    return 0;
}

参考：

• 官方解析，参考[这儿].