2020/4/29 华为通用软件开发机考（全程暴力）

第一题、求字符串（可能有重复字母）的全排列有多少种？

这一题只用了几十秒吧，之前看了leetcode的解法，选择用了库函数next_permutation,但是不知道为啥只过了90%。。。。。求大佬解答。

#include <bits/stdc++.h>

using namespace std;

int main() {
	string s;
    
    while(cin >> s) {
        sort(s.begin(), s.end());
        string tmp(s);
        
        int cnt = 0;
        
        do{
          cnt++;
          next_permutation(tmp.begin(), tmp.end());
        }while(tmp != s);
        cout << cnt << endl;
        
        cout << tmp << endl;
    }

	return 0;
}

第二题、输入一个非空字符串，每次删除一个字符（直到删空），并使得当前字典序最小，问最后删除的字符是什么？

不好意思，摆上我丑陋的代码，字典序想了半天，忘了这个概念了，所以最后没办法，我就只能把两个字符串比大小，从中得到最小的。用了暴力法，但是没想到竟然AC了，一脸懵逼。

#include <bits/stdc++.h>

using namespace std;


void del(string &s) {
	string str(s);
	
	string ans(s);
	ans.erase(ans.begin());
	
	for(int i = 1; i < s.size(); ++i) {
		str = s;
		str.erase(i + str.begin());
		if(str < ans) {
			ans = str;
		}
	}
	s = ans;
}

string _erase(string &s, int k) {
	
	for(int i = 0; i < k; ++i) {
		del(s);
	}
	return s;
}

int main() {
	
	string s;
    int k;
    while(cin >> s >> k) {
        if(s.size() <= k)    continue;
        
        _erase(s, k);
        cout << s << endl;
    }
	return 0;
}

第三题、大概是个求最短路径的问题，给的是有向图，城市1~N，然后还有过路费，问只带了k个硬币的情况下，找到从城市1到城市N的最短路径，如果不存在通路，打印-1。

我是忘了迪杰斯特拉咋写了，很难受，最后又是想到暴力法，DFS加剪枝。可能代码问题比较多，示例都没通过。。。但是提交后竟然有55.56%。感觉代码的问题很多，我自己都看的不是很明白。。。

#include <bits/stdc++.h>

using namespace std;

vector<int> holder(1,1);



void dfs(int start, int N, int K, int &dis, int &cost, map<pair<int, int>, pair<int, int>> &hasRoad, int &MIN_dis) {
    
    if(cost > K)	return;
    
    if(start == 6 && !holder.empty() && holder.back() == 6) {
    	MIN_dis = min(MIN_dis,dis);
		return; 
	}

    
    for (int i = start; i <= N; ++i) {
    	if(hasRoad.find({start, i}) == hasRoad.end())	continue;
    	
    	holder.push_back(i); 
		dis += hasRoad[{start, i}].first;
		cost += hasRoad[{start, i}].second;
    	dfs(i, N, K, dis, cost, hasRoad, MIN_dis);
    	holder.pop_back();
    	dis -= hasRoad[{start, i}].first;
		cost -= hasRoad[{start, i}].second;
	}
    
}

int main() {
	int K;
    int N;
    int R;
    while(cin >> K >> N >> R) {
    	int MIN_dis = INT_MAX;
    	int dis = 0;
    	int cost = 0;
    	
        map<pair<int, int>, pair<int, int>> hasRoad;
        vector<int> S(R, 0);
        vector<int> D(R, 0);
        vector<int> L(R, 0);
        vector<int> T(R, 0);
        
        for (int i = 0; i < R; ++i) {
            cin >> S[i] >> D[i] >> L[i] >> T[i];
            hasRoad[{S[i], D[i]}] = {L[i], T[i]};
        }
        
        dfs(1, N, K, dis, cost, hasRoad, MIN_dis);
        if(MIN_dis == INT_MAX)	cout << -1 << endl;
        else cout << MIN_dis << endl;
        
    }
	return 0;
}

#华为笔试##华为##笔试题目#