2020/9/6 20:00 腾讯笔试

虽然题目上说链表，但是可以用数组，而且已经排好序了，遍历一遍就可

//1.

100代码

typedef long long ll;

int main() {
	//ios::sync_with_stdio(false);
	//freopen("in.txt", "r", stdin);
	int n; cin >> n;
	deque<int>a(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	int m; cin >> m;
	deque<int>b(m);
	for (int i = 0; i < m; i++) cin >> b[i];
	int i = 0, j = 0;
	while (i < a.size() && j < b.size()) {
		if (a[i] == b[j]) cout << a[i] << ' ';
		else if (a[i] < b[j]) i--;
		else if (a[i] > b[j]) j--;
		i++, j++;
	}
	cout << endl;
}

并差集模板

//2.

100代码

typedef long long ll;

const int maxn = 1e5 + 5;
int ran[maxn];
int f[maxn];
void init() {
	for (int i = 0; i < maxn; i++) {
		f[i] = i;
	}
}
int fin(int x) {
	return f[x] = f[x] == x ? x : fin(f[x]);
}
void meg(int x, int y) {
	int a = fin(x);
	int b = fin(y);
	if (ran[a] < ran[b]) {
		f[a] = b;
	}
	else {
		f[b] = a;
		if (ran[a] == ran[b]) {
			ran[a]++;
		}
	}
}
bool same(int x, int y) {
	return fin(x) == fin(y);
}

int main() {
	//ios::sync_with_stdio(false);
	//freopen("in.txt", "r", stdin);
	int m, n; cin >> n >> m;
	init();
	for (int i = 0; i < m; i++) {
		int num; cin >> num;
		int vis; cin >> vis;
		num--;
		int t;
		while (num--) {
			cin >> t;
			if (!same(vis, t)) {
				meg(vis, t);
			}
		}
	}
	int ans = 0;
	int anst = fin(0);
	for (int i = 0; i < maxn; i++) {
		if (fin(i) == anst) ans++;
	}
	cout << ans << endl;
}

使用map计数

再转换到vector上，

使用自定义的cmp排序，

输出前k个

//3.

100代码

typedef long long ll;
typedef pair<string, int> psi;

bool cmp1(psi a, psi b) {
	if (a.second == b.second) return a.first < b.first;
	return a.second < b.second;
}
bool cmp2(psi a, psi b) {
	if (a.second == b.second) return a.first < b.first;
	return a.second > b.second;
}

int main() {
	//ios::sync_with_stdio(false);
	//freopen("in.txt", "r", stdin);
	int n, k; cin >> n >> k;
	unordered_map<string, int>mp;
	string s;
	for (int i = 0; i < n; i++) {
		cin >> s;
		mp[s]++;
	}
	vector<psi>v1;
	for (auto it = mp.begin(); it != mp.end(); it++)
		v1.emplace_back(psi{ it->first,it->second });
	auto v2 = v1;;
	sort(v1.begin(), v1.end(), cmp1);
	sort(v2.begin(), v2.end(), cmp2);
	for (int i = 0; i < k; i++)
		cout << v2[i].first << ' ' << v2[i].second << endl;
	for (int i = 0; i < k; i++)
		cout << v1[i].first << ' ' << v1[i].second << endl;
}

其实答案就两个，

先复制原数组

对一个排序变成新数组

遍历原数组，判断在新数组的左边还是右边

左边就输出新数组靠右的中位数

右边就输出新数组靠左的中位数

//4.

100代码

typedef long long ll;

int main() {
	//ios::sync_with_stdio(false);
	//freopen("in.txt", "r", stdin);
	int n; cin >> n;
	vector<int>s(n);
	for (int i = 0; i < n; i++) cin >> s[i];
	auto t = s;
	sort(s.begin(), s.end());
	int mid = n >> 1;
	for (int i = 0; i < n; i++) {
		int it = lower_bound(s.begin(), s.end(), t[i]) - s.begin();
		if (it < mid) cout << s[mid] << endl;
		else cout << s[mid - 1] << endl;
	}
}

第五题，没思路，我用了冒泡插入选择，都是5%，而且我觉得交什么都是5%（有一次交的别的代码，也是5%），手动狗头。

#笔试题目##腾讯#