首页 > 资源分享 > 华为七月份机试题总结1-0707

华为七月份机试题总结1-0707

头像
lw_hnu
发布于 2021-08-03 05:16:26 APP内打开
赞 6 | 收藏 49 | 回复3 | 浏览5620
这些题目都是在牛客网上搜集的,也参考了一些大佬的代码。
对题目进行了详细的描述,并提供了输入输出示例,参考代码也更适合基础薄弱的参看。
希望大家可以一起交流学习,offer拿到手软!!!

/*
华为的机试题0707-1:
贪心做法
题目: 有n个事件,每个事件形式为(t,w),表示若在t时刻前完成该事件,获得w分数,每一个小时只能完成一个事件,求最大能获得的分数
事件数量<=1000000
输入: 
7
1 6
1 7
3 2
3 1
2 8
2 10
6 1
输出:21 
*/ 
#include<bits/stdc++.h>
using namespace std;

int main()
{
	auto cmp = [](const vector<int> &a, const vector<int> &b)
	{
//		if(a[0] == b[0]) return a[1]>b[1];
//		else return a[0]<b[0];
		return a[0]<b[0];
	};
	int N;
	cin>>N;
	vector<vector<int>> nums;
	vector<int> v_temp;
	int a, b;
	for(int i=0; i<N; i++)
	{
		cin>>a>>b;
		v_temp.push_back(a);
		v_temp.push_back(b);
		nums.push_back(v_temp);
		v_temp.clear();
	}
	sort(nums.begin(), nums.end(), cmp);  //按时刻进行排序,对于时刻相同的,分值大的优先(实际这个没必要,因为接下来会用小顶堆替换掉以前时刻分值小的) 
	for(int i=0; i<nums.size();i++)
	{
		cout<<nums[i][0]<<':'<<nums[i][1]<<endl; 
	}
	priority_queue<int,vector<int>, greater<int>> pq;  //就是为了解决出现时刻相同的情况,如果分值大,则会替换以前时刻的工作 
	pq.push(nums[0][1]);
	for(int i=1; i<nums.size(); i++)
	{
		cout<<"Top is"<<pq.top()<<endl;
		if(nums[i][0] == nums[i-1][0]) //出现了时刻相等,就要判断相等时刻的分值是否比以前的大,如果是则直接替换掉 
		{
			if(nums[i][1] > pq.top())
			{
				cout<<"Delete " <<pq.top()<<endl;
				pq.pop();
				pq.push(nums[i][1]);
			}
		}
		else  //对于不同时刻直接压入小顶堆就可以了 
		{
			pq.push(nums[i][1]);
		}
	}
	int result = 0;
	while(!pq.empty())
	{
		result += pq.top();
		pq.pop();	
	 } 
	 cout<<result<<endl;
	return 0;
}
 
/*
华为的机试题0707-2:
图搜素 
给定一个有向图以及一个起点,问是否只从起点出发就可以走到全部的点,如果可以,输出起点到其他点的最长距离
点数<=100, 边数<=5000,路径的长度小于100 
输入:
[1,2,15]
[1,3,14]
[3,4,9]
4
1

输出:23;  路线1-3-4.虽然不经过2,但是1可以到2,所以算能到达。
输入如上,前三行分别代表景点1到景点2之间有路,距离为15,景点1到景点3之间有路,距离为14,景点3到景点4之间有路,距离为9。
接下来输入一共有多少个景点,下一行是起始景点。问是否能逛完,可以的话求最长路径,否则输出-1.景点数小于100,路径长度小于100,两个景点间路径数小于5000.
*/ 
#include<bits/stdc++.h>

using namespace std;

vector<vector<int>> graph(100, vector<int>(100, 0));
vector<bool> visited(100, false);
int max_path = 0;


void dfs(int start, int N, int path)
{
	visited[start] = true;
	
	for(int i=0; i<N; i++)
	{
		if(graph[start][i]>0 && !visited[i])
		{
			path += graph[start][i]; //这才是在深度方向上相加 
			dfs(i, N, path);
			max_path = max(path, max_path);
			path -= graph[start][i];
		}
	}
	
}

int main()
{
	
	string s;
	int start;
	int N;
	while(getline(cin, s))
	{
//		cout<<"s="<<s<<endl;
		if(s[0] == '[')
		{
			s = s.substr(1, s.size()-2);
			int i, j, val;
			int pos = s.find(',');
			i = stoi(s.substr(0, pos));
			s = s.substr(pos+1);
			pos = s.find(',');
			j = stoi(s.substr(0, pos));
			s = s.substr(pos+1);
			val = stoi(s);
//			cout<<"i="<<i<<";j="<<j<<";val="<<val<<endl;
			graph[i-1][j-1] = val;
		}
		else
		{
			N = stoi(s);
			cin>>s;
			start = stoi(s)-1;
//			cout<<"N="<<N<<";start="<<start<<endl;
			break;
		}
	}
	dfs(start, N, 0);
	for(int i=0; i<N; i++)
	{
		if(!visited[i]) 
		{
			cout<<-1<<endl;
			return 0;
		}
	}
	cout<<max_path<<endl;
	return 0;
 } 
 
/*
华为的机试题0707-3:
dfs暴搜就可以 
题目: 题目大意:在中国象棋中,给出大小为m*n的棋盘,棋盘上有一些障碍点,以及一匹马在S处要到T点,
给出中国象棋中跳马的规则,问至少需要多少步才能跳到T点
数据范围m, n< = 150
输入: 对于输入的解释,4是行,5是列,#是障碍物,H是起始点,T是终止点 
4
5
***#*
*H***
**T#*
#****
输出:从H到T最小的步数 
4  
*/ 
#include<bits/stdc++.h>
using namespace std;

int min_val = INT_MAX;
vector<int> directions_x = {2, 2, -2, -2, 1, 1, -1, -1};
vector<int> directions_y = {1, -1, 1, -1, 2, -2, 2, -2};


void dfs(vector<vector<char>> &graph, vector<vector<bool>> &visited, int i, int j, pair<int, int> end, int step)
{
	if(i<0 || i>=graph.size() || j<0 || j>=graph[0].size() || visited[i][j] || graph[i][j] == '#')
	{
		return;
	}

	if(i == end.first && j == end.second)
	{
		min_val = min(step, min_val);
		return;
	}
	visited[i][j] = true;
	step++;
	for(int k=0; k<8; k++)
	{
		int x = i+directions_x[k];
		int y = j+directions_y[k];
		dfs(graph, visited, x, y, end, step);
	}
	visited[i][j] = false;
	step--;
}
	

int main()
{
	int m, n;
	cin>>m>>n;
	vector<vector<char>> graph(m, vector<char>(n, '*'));
	vector<vector<bool>> visited(m, vector<bool>(n, false));
	char temp;
	pair<int, int> start;
	pair<int, int> end;
	for(int i=0; i<m; i++)
	{
		for(int j=0; j<n; j++)
		{
			cin>>temp;
			graph[i][j] = temp;
			if(temp == 'H')
			{
				start.first = i;
				start.second = j;
			}
			if(temp == 'T')
			{
				end.first = i;
				end.second = j;
			}
		}
	}
	dfs(graph, visited, start.first, start.second, end, 0);
	if(min_val == INT_MIN)
	{
		cout<<-1<<endl;
	}
	else
	{
		cout<<min_val<<endl;
	}
	
	return 0;
}
 




3条回帖

回帖
加载中...
话题 回帖

相关热帖

资源分享近期热帖

近期精华帖

热门推荐