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; }