首页 > 华为七月份机试题总结3-0721
头像
lw_hnu
发布于 2021-08-06 06:57
+ 关注

华为七月份机试题总结3-0721

这些题目都是在 牛客 网上搜集的,也参考了一些大佬的代码。
对题目进行了详细的描述,并提供了输入输出示例,参考代码也更适合基础薄弱的参看。
希望大家可以一起交流学习,offer拿到手软!!!
/*
华为的机试题0721-1:
贪心做法
题目: 第一行输入 [车站数,乘客数],
后面每一行输入 [上车时间,上车车站,下车车站]。
道路为环形道路,按最短路径行驶。比如车站0到车站10(共11个车站)选择0-10-9的路径。每一站路耗时5分钟,问路上最多同时有几辆车?
输入: 
11 3
1 3 10
1 5 6
7 2 4
输出: 
思路:因为这道题是要求在路上同时有多少辆车,也就是车在路上的时间间隔的最大重叠个数。
比如 乘客1:[5, 10], 乘客2 [6, 11],那么他们两个在[6,10]这个时间段都会在路上
因此只需要将上车时间,上车车站,下车车站转换为在路上的时间间隔就可以了
剩下的就是求重叠区间的问题了,和leetcode上射气球,合并重叠区间这类问题就相似了 
*/ 
#include<bits/stdc++.h>

using namespace std;

int main()
{
	auto cmp =[](const vector<int> &a, const vector<int> &b)
	{
		return a[0] < b[0];
	};
	int m, n;
	cin>>m>>n;
	int a, b, c;
	vector<vector<int>> nums; 
	for(int i=0; i<n; i++)
	{
		//将原始输入转换为在路上的时刻区间
		cin>>a>>b>>c;
		vector<int> temp;
		temp.push_back(a);
		int time = 5 *(min(abs(b-c), m-(abs(b-c)))) + a;
		temp.push_back(time);
		nums.push_back(temp);
	}
	sort(nums.begin(), nums.end(), cmp);
	for(int i=0; i<nums.size();i++)
	{
		cout<<nums[i][0]<<':'<<nums[i][1]<<endl; 
	}
	int r_bound = nums[0][1];
	int max_val = 0;
	int val = 1;
	for(int i=1; i<nums.size(); i++)
	{
		if(nums[i][0] < r_bound)
		{
			val++;
			r_bound = min(r_bound, nums[i][1]);
		}
		else
		{
			val = 1;
			r_bound = nums[i][1];
		}
		max_val = max(val, max_val);
	}
	cout<<max_val<<endl;
	return 0;
 } 
/*
华为的机试题0721-2:
贪心做法
题目: 有N个机器,K个任务。一个机器只能完成一个任务,
接下来输入K行,代表K个任务,第一个数字代表任务花费的时间,第二个数字代表任务的优先级。
优先级越小越优先,同优先级情况下花费时间越长越优先。问搞完这一批任务需要多长时间?
输入: 
3 5
3 2
4 1
5 3
6 4
1 5
输出: 9
*/ 
#include<bits/stdc++.h>

using namespace std;

int main()
{
	int n, k;
	cin>>n>>k;
	vector<vector<int>> nums;
	for(int i=0; i<k; i++)
	{
		int a, b;
		cin>>a>>b;
		nums.push_back({a, b});
	}
	auto cmp=[](const vector<int> &a, vector<int> &b){
		return a[1] < b[1];
	};
	sort(nums.begin(), nums.end(), cmp);  //按照优先级进行排序 
	int i=0;
	//先将前n个任务加入小顶堆中,该小顶堆维护的是n台机器 
	priority_queue<int, vector<int>, greater<int>> pq; 
	for(; i<n; i++)
	{
		pq.push(nums[i][0]);
	}
	while(i<nums.size())  //将剩下的任务依次加入小顶堆的最小值中 
	{
		int temp = pq.top() + nums[i][0];
		pq.pop();
		pq.push(temp);
		i++;
	}
	int res=0; //小顶堆中的最大值即为所要花费的最长时间
	while(!pq.empty())
	{
		res = max(res, pq.top());
		pq.pop();
	 } 
	 cout<<res<<endl;
	return 0;
 } 
/*
华为的机试题0721-3(dfs):
图搜索,感觉和 0707-3基本一样,只不过数据处理比较麻烦,并且也没有告诉节点的个数。 
题目: 就是给个有向图,无环,求最长路径。
n个点(n<=200)
输入: 
[[1,2,5],[1,3,5],[2,3,10]]
输出: 15
*/ 
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> graph(201, vector<int>(201, 0));
int max_val = INT_MIN;

void dfs(vector<vector<int>> &graph, int s, unordered_set<int> u_s, int res)
{

	for(auto &t:u_s)
	{
		if(graph[s][t] != 0)
		{
			res += graph[s][t];
			max_val = max(max_val, res);
			dfs(graph, t, u_s, res);
			res -= graph[s][t];
		}
	}
}

int main()
{
	vector<vector<int>> graph(201, vector<int>(201, 0));
	unordered_set<int> us;  //用于存放节点值 
	string s;
	cin>>s;
	//字符串的处理 
	while(s.size()>3)
	{
		int pos1 = s.find(']');
		string temp = s.substr(2, pos1-2);
		
		int a, b, c;
		int pos2 = temp.find(',');
		a = stoi(temp.substr(0, pos2));
		temp = temp.substr(pos2+1);
		us.emplace(a-1); 
		
		
		pos2 = temp.find(',');
		b = stoi(temp.substr(0, pos2));
		temp = temp.substr(pos2+1);
		us.emplace(b-1);
		
		c = stoi(temp);
		graph[a-1][b-1] = c;
//		cout<<"a="<<a<<"b="<<b<<"c="<<c<<endl;
		s = s.substr(pos1+1);
	}
	for(auto &s:us) //这里有个疑问,就是节点是不是连续的从1-N,如果是直接传入us.size()就可以了 
	{
		dfs(graph, s, us, 0);
	}
	cout<<max_val<<endl;
	return 0;
}
/*
华为的机试题0721-3(bfs):
图搜索,感觉和 0707-3基本一样,只不过数据处理比较麻烦,并且也没有告诉节点的个数。 
题目: 就是给个有向图,无环,求最长路径。
n个点(n<=200)
输入: 
[[1,2,5],[1,3,5],[2,3,10]]
输出: 15
*/ 
#include<bits/stdc++.h>
using namespace std;
int max_val = INT_MIN;

void bfs(vector<vector<int>> &graph, int start, unordered_set<int> &us)
{
		queue<pair<int, int>> q;
		q.push(make_pair(start, 0));
		while(!q.empty())
		{
			pair<int, int> cur = q.front();
			q.pop();
			for(auto &t2:us)
			{
				if(graph[cur.first][t2] !=0)
				{
					pair<int, int> add_val = make_pair(t2, graph[cur.first][t2] + cur.second);
					max_val = max(max_val, add_val.second);
					q.push(add_val);
				}
			}
			
		}
}

int main()
{
	vector<vector<int>> graph(201, vector<int>(201, 0));
	vector<bool> visited(201, false);
	

	unordered_set<int> us;  //用于存放节点值 
	string s;
	cin>>s;
	//字符串的处理 
	while(s.size()>3)
	{
		int pos1 = s.find(']');
		string temp = s.substr(2, pos1-2);
		
		int a, b, c;
		int pos2 = temp.find(',');
		a = stoi(temp.substr(0, pos2));
		temp = temp.substr(pos2+1);
		us.emplace(a-1); 
		
		
		pos2 = temp.find(',');
		b = stoi(temp.substr(0, pos2));
		temp = temp.substr(pos2+1);
		us.emplace(b-1);
		
		c = stoi(temp);
		graph[a-1][b-1] = c;
//		cout<<"a="<<a<<"b="<<b<<"c="<<c<<endl;
		s = s.substr(pos1+1);
	}
	for(auto &t1:us) //这里有个疑问,就是节点是不是连续的从1-N,如果是直接传入us.size()就可以了 
	{
		bfs(graph, t1, us);
	}
	cout<<max_val<<endl;
	return 0;
}





全部评论

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

推荐话题

相关热帖

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

近期精华帖

热门推荐