首页 > C++网易笔试8.8
头像
迷路的offer
编辑于 2020-08-08 16:44
+ 关注

C++网易笔试8.8

第一题
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

int getIndex(const string& str) {
	int mid = max(int(str.length() / 2 - 1), 0);
	int res = str.length() - 1;
	//mid为中点
	while (mid < str.length()) {
		int index = 0;
		while (index + 1 + mid < str.length() && mid - index >= 0) {
			if (str[mid + 1 + index] != str[mid - index]) break;
			++index;
		}
		if (mid + 1 + index == str.length())
			res = min(res, mid - index);
		if (res == -1) break;
		index = 0;
		while (index + mid + 1 < str.length() && mid - index - 1 >= 0) {
			if (str[mid + index + 1] != str[mid - index - 1]) break;
			++index;
		}
		if (index + mid + 1 == str.length())
			res = min(res, mid - index - 1);
		++mid;
		if (res == -1) break;
	}
	return res + 1;
}

string getRes(const string& str) {
	int index = getIndex(str);
	string tmp = str.substr(0, index);
	reverse(tmp.begin(), tmp.end());
	return str + tmp;
}


int main() {
	string str;
	cin >> str;
	cout << getRes(str) << endl;
}
第二题
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;

void reduce(vector<int>&nums,int index,int first,int second,int sum,int& res) {
	if (first == second)
		res = min(res, sum - first - second);
	if (index >= nums.size()) return;
	reduce(nums, index + 1, first + nums[index], second, sum, res);
	reduce(nums, index + 1, first, second + nums[index], sum, res);
	reduce(nums, index + 1, first, second, sum, res);
}

int getMinCost(vector<int>&nums) {
	int index = 0;
	int sum = 0;
	for (int i = 0; i < nums.size(); ++i) sum += nums[i];
	int res = sum;
	reduce(nums, index, 0, 0, sum, res);
	return res;
}

int main() {
	int t, n;
	cin >> t;
	while (t-- > 0) {
		cin >> n;
		vector<int>nums(n);
		for (int i = 0; i < n; ++i)
			cin >> nums[i];
		cout << getMinCost(nums) << endl;
	}
}
第三题
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;

int getMinCost(vector<int>a, vector<int>b) {
	vector<int>dp(a.size() + 1);
	dp[1] = a[0];
	for (int i = 2; i < dp.size(); ++i) {
		dp[i] = min(dp[i - 1] + a[i - 1], dp[i - 2] + b[i - 2]);
	}
	return dp.back();
}

string getTime(int cost) {
	int h = 8, m = 0, s = 0;
	s = cost % 60;
	cost /= 60;
	m += cost % 60;
	cost /= 60;
	h += cost % 24;
	bool flag = false;
	if (h > 12) {
		h -= 12;
		flag = true;
	}
	string sh = to_string(h);
	if (sh.size() < 2) sh = "0" + sh;
	string sm = to_string(m);
	if (sm.size() < 2) sm = "0" + sm;
	string ss = to_string(s);
	if (ss.size() < 2) ss = "0" + ss;
	return sh + ":" + sm + ":" + ss + " " + (flag ? "pm" : "am");

}

int main() {
	int m;
	cin >> m;
	while (m-- > 0) {
		int n;
		cin >> n;
		vector<int>a(n);
		vector<int>b(n);
		for (int i = 0; i < n; ++i) cin >> a[i];
		for (int i = 0; i < n - 1; ++i) cin >> b[i];
		int cost = getMinCost(a, b);
		cout << getTime(cost) << endl;
	}
	
}

第四题(超时,过50%)
#include<unordered_map>
#include<unordered_set>
#include<vector>
#include<iostream>
#include<stack>
using namespace std;

int getNum(int n,vector<vector<int>>&nums) {
	unordered_map<int, unordered_set<int>>graph;
	for (int i = 0; i < nums.size(); ++i) 
		graph[nums[i][0]].insert(nums[i][1]);
	unordered_map<int, unordered_set<int>>hashMap;
	for (int i = 0; i < n; ++i) {
		unordered_set<int>visited;
		stack<int>stack;
		visited.insert(i);
		stack.push(i);
		int m = 0;
		while (!stack.empty()) {
			int from = stack.top();
			stack.pop();
			if (graph.find(from) == graph.end()) continue;
			auto& ps = graph[from];
			for (auto& p : ps) {
				if (visited.find(p) != visited.end()) continue;
				visited.insert(p);
				stack.push(p);
				++m;
			}
		}
		hashMap[i] = visited;
	}
	int cnt = 0;
	for (auto& kv : hashMap) {
		int from = kv.first;
		auto& set = kv.second;
		for (auto& to : set) {
			if (hashMap.find(to) == hashMap.end()) continue;
			if (hashMap[to].find(from) == hashMap[to].end()) continue;
			if (to == from) continue;
			++cnt;
		}
	}
	return cnt / 2;
}

int main() {
	int n, m;
	cin >> n >> m;
	vector<vector<int>>nums(m);
	for (int i = 0; i < m; ++i) {
		vector<int>vec(2);
		cin >> vec[0] >> vec[1];
		vec[0] -= 1;
		vec[1] -= 1;
		nums[i] = vec;
	}
	cout << getNum(n,nums) << endl;
}




全部评论

(10) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐