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

**输出**：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行表示路径的信息：出发城市、到达城市、路径长度、路费；

**输入样例**：

**输出**：11（1->3->5->4->6）

**思路**：感觉是一道Floyd变体，直接暴力没想到过了，惊讶。更新路径的过程中比较路费，如果路费不足就不更新了，反正都不够钱走。time也许不需要，就是多次执行Floyd。这题AC

2020.4.29华为笔试【华为校园招聘 软件】

全站热榜

2020.4.29华为笔试【华为校园招聘软件】