华为机试总结 2020-0409

华为2020.0409机试总结，通过0.9-1-0.9题目回忆如下：

1.给定一个字符串，求组成字符串（由小写字母构成）所有字母的全部排列，返回组合的数量；字符串长度小于8，字符串为0，返回0.

输入：aab

输出：3

以下代码通过0.9，和群里小伙伴交流发现少限制了字符串长度小于8的条件，个人理解是题目保证小于8所以没限制。。

//思路：逐个交换字母，遍历搜索全部可能的结果，最后去重

void dfsFind(string &str, int beg, int end, vector<string> &ret);
void delteChong(vector<string> &ret);

int main()
{
    string input;
    while (getline(cin, input))
    {
        if (input.size() == 0)
        cout << 0 << endl;
        vector<string> ret;

        dfsFind(input, 0, input.size(),ret);
        delteChong(ret);
        cout << ret.size() << endl;
    }

return 0;
}
//交换  求出所有可能的情况
void dfsFind(string &str, int beg, int end,vector<string> &ret)
{    
    if (beg == end)
        ret.push_back(str);

    for (int i = beg; i < end; ++i)
    {
        swap(str[beg], str[i]);
        dfsFind(str, beg + 1, end,ret);
        swap(str[beg], str[i]);
    }
}

//在中间去重
void delteChong(vector<string> &ret)
{
    sort(ret.begin(), ret.end());
    ret.erase(unique(ret.begin(), ret.end()), ret.end());
}

2.求秘钥，给定一个字符串，给定一个整数k，在字符串中去掉k个字母，使最后的字符串字节序最小。

输入：abcca 1(换行)

输出:acca

以下代码AC，思路是比较前后两个字符，如果前一个字符大于后一个字符，则删掉前边的字符可以使得字节序变小，删除函数执行k次即可

void deleteChar(string &str, int k, string &rem);
int main()
{
    string input;
    int k = 0;
    while (getline(cin, input))
    {
        cin >> k;
        cin.ignore();
        string rem;
        deleteChar(input, k, rem);
        if (rem.size())
            cout << rem << endl;
        else
        {
            cout << endl;
        }
    }

    return 0;
}

void deleteChar(string &str, int k,string &rem)
{
    if (k == 0)
    {
        rem = str;
        return;
    }
    int flag = 0;
    for (auto it = str.begin(); it != str.end() - 1; ++it)
    {
        if ((*it) <= (*(it + 1)))
            continue;
        if ((*it) > (*(it + 1)))
        {
            str.erase(it);
            flag = 1;
            break;
        }
    }
    if (flag == 0)
        str.erase(str.end() - 1);
    deleteChar(str, k - 1, rem);
}

3.求城市1到城市N的最短路径，给定每条路的长度，要求长度最短且需要钱够用。

以下代码通过89.9%，后来发现代码中判断钱数那块儿写错了，应该是k>=0。看别人代码，有说城市之间有多条路的，应该要优选才能放入vecR。
代码中是带记忆的BFS，写了dfs懒得改了

#define MAXVAL (int)(0xFFFF)
void dfs(int now, int k, int end, int path, vector<int> &pathSum, vector<vector<pair<int, int>>> &vecR);
int main()
{
    int K = 0, N = 0, R = 0;//输入钱数、城市数、路的数量（单向）
    while (cin >> K >> N >> R)
    {
        vector<vector<pair<int,int>>> vecR;
        vector<pair<int, int>> temp;
        //建立路的matrix
        pair<int, int> pa;
        pa.first = MAXVAL; pa.second = 0;    //pair first存放需要花的钱数，second存放路的长度
        for (int i = 0; i < N; ++i)
            temp.push_back(pa);
        for (int i = 0; i < N; ++i)
            vecR.push_back(temp);
        int S, D, L, T;
        for (int i = 0; i < R; ++i)    //建立城市-城市之间的路
        {
            cin.ignore();
            cin >> S >> D >> L >> T;
            S -= 1;
            D -= 1;
            vecR[S][D].first = T;
            vecR[S][D].second = L;
        }
        vector<int> pathSum;
        dfs(0, K, N-1, 0, pathSum, vecR);    //寻找所有在钱的限制下，可以到达的路
        if (pathSum.size() == 0)
            cout << -1 << endl;
        else
        {
            sort(pathSum.begin(), pathSum.end());    //找到路径最短的
            cout << pathSum[0] << endl;
        }

    }
    return 0;
}

void dfs(int now,int k,int end,int path, vector<int> &pathSum, vector<vector<pair<int, int>>> &vecR)
{
    if (now == end || k<0)
    {
        if(k>0)    //钱没花完  应该是k>=0的   写错了
            pathSum.push_back(path);    
        return;
    }
    for (int i = 0; i <= end; ++i)
    {
        if (vecR[now][i].first != MAXVAL)
        {
            int val = vecR[now][i].first;
            vecR[now][i].first = MAXVAL;//防止有环
            dfs(i, k - val, end, path + vecR[now][i].second, pathSum, vecR);    //更新当前城市，继续搜索能走的路
            vecR[now][i].first = val;    //恢复
        }
    }

}