2020.4.29华为笔试【华为校园招聘 软件】
### 1.给定一个字符串（最多包含8个字符），可能包含重复的字母，返回有多少种不同的排列组合。
**输入样例**：abc
**输出**：6
**tips**：如果字符串为空，输出0。
**思路**：类似于leetcode47题，枚举每一个字符所在的位置。为了不重复，需要保证相同字符的相对位置不变。因此，如果后面的字符跟当前字符相同，后面的字符必须在当前字符的后面；如果不相同，随便放。
只通过了百分之90，不知道哪里错了。
#include<bits/stdc++.h>
using namespace std;
void dfs(int num,int step, string &s, int &cnt,vector<int> &jd) {
if (num == s.size()) {
cnt++;
return;
}
for (int i = step; i < s.size(); ++i) {
if (jd[i] == 0) {
jd[i] = 1;
if (num <(s.size()-1) && s[num] == s[num + 1])
dfs(num + 1, i + 1, s, cnt, jd);
else
dfs(num + 1, 0, s, cnt, jd);
jd[i] = 0;
}
}
return;
}
int main() {
string s;
int cnt = 0;
getline(cin, s);
if (s.size() == 0) {
cout << cnt << endl;
return 0;
}
vector<int> jd(s.size(), 0);
dfs(0, 0, s, cnt, jd);
cout << cnt << endl;
return 0;
} ### 2.给定一个字符串M和一个整数k，可以删除M中任意k个字符，返回字典序最小的那一个结果。
**输入样例**：bacaa
1
**输出**：acaa
**思路**：遍历这个字符串，类似于冒泡算法不断比较相邻的字符。如果遇到逆序对就删掉第一个字符，k--，然后继续比较剩余的字符；如果全部逆序对都删除了k仍然大于0，就删掉后面的剩余字符；
如果当前枚举的字符串比当前最优ans要大就不需要比较了，直接返回。这题AC
#include<bits/stdc++.h>
using namespace std;
void dfs(int num, int k, string M, string &ans) {
if (k == 0) {
ans = min(ans, M);
return;
}
int i;
for (i = num; i < M.size() - 1; ++i) {
if (M[i] > M[i + 1]) {
string temp = M;
M = M.erase(i, 1);
if (num == 0 && M < ans)
dfs(num, k - 1, M, ans);
else if (M < ans)
dfs(num-1, k - 1, M, ans);
M = temp;
}
}
if (i == M.size() - 1 && k > 0)
dfs(num, 0, M.erase(M.size() - k), ans);
}
int main() {
string M, ans;
int k;
cin >> M >> k;
ans = M;
dfs(0, k, M, ans);
cout << ans << endl;
return 0;
} ### 3.A要去B的城市找他玩，但是去B的城市有很多路径，A身上的钱也有限，请你帮他找到去B的城市的最短路径，路费也要足够。城市之间有单向的路径，每条路径有一定的路费。这题默认A在1号城市，B在N号城市。输出最短路径。
输入第一行为A身上的钱；
第二行为N，表示有N座城市；
第三行表示有R条路径；
接下来R行表示路径的信息：出发城市、到达城市、路径长度、路费；
**输入样例**：
5 6 7 1 2 2 4 2 4 3 3 3 4 2 4 1 3 4 1 4 6 2 1 3 5 2 0 5 4 3 2
**输出**：11（1->3->5->4->6）
**思路**：感觉是一道Floyd变体，直接暴力没想到过了，惊讶。更新路径的过程中比较路费，如果路费不足就不更新了，反正都不够钱走。time也许不需要，就是多次执行Floyd。这题AC
#include<bits/stdc++.h>
using namespace std;
/*
5
6
7
1 2 2 4
2 4 3 3
3 4 2 4
1 3 4 1
4 6 2 1
3 5 2 0
5 4 3 2
11
*/
int main() {
int coin, city, road, ans = 0x3f, time = 2;
cin >> coin >> city >> road;
vector<vector<vector<int>>> wh(city + 1, vector<vector<int>>(city + 1, vector<int>(2, 0x3f)));
for (int i = 0; i < road; ++i) {
int start, end, path, pay;
cin >> start >> end >> path >> pay;
wh[start][end][0] = path;
wh[start][end][1] = pay;
}
while (time--) {
for (int k = 1; k < wh.size(); ++k)
for (int i = 1; i < wh.size(); ++i)
for (int j = 1; j < wh.size(); ++j)
if (wh[k][i][0] + wh[i][j][0] < wh[k][j][0] && wh[k][i][1] + wh[i][j][1] <= coin) {
wh[k][j][0] = wh[k][i][0] + wh[i][j][0];
wh[k][j][1] = wh[k][i][1] + wh[i][j][1];
}
}
if (wh[1][city][0] <= ans && wh[1][city][1] <= coin)
cout << wh[1][city][0] << endl;
else
cout << -1 << endl;
return 0;
}
，敢不敢来