华为OD机试 2O22Q4 A卷

三道题 100分+100分+200分 150分就可以过 每道题是 分数为总分*测试用例通过比例,我这里过了2 3题 100%通过率，每道题大概讲一下题目.

第一题

给定一个数组nums,将元素分为若干个组，使得每组和相等，求出满足条件的所有分组中，组内元素和的最小值 第一行输入 m 接着输入m个数，表示此数组 数据范围:1<=M<=50, 1<=nums[i]<=50 这道题我这里没做出来，没有什么思路

第二题

求单项链表中间的节点值，如果奇数个节点去中间，偶数个取偏右边的那个值 输入： 第一行 链表头节点地址 后续输入的节点数n 后续输入没行表示一个节点，格式 节点地址 节点值 下一个节点地址(-1表示空指针) 输入保证链表不会出现环并且可能存在一些节点不属于链表 测试用例:

00010 4
00000 3 -1
00010 5 12309
11451 6 00000
12309 7 11451

输入:

6

思路:hashmap构建链表，先遍历一次记录链表长度size,再找下标为size/2的节点，不会超时 c++代码：

#include <iostream>
#include <unordered_map>
using namespace std;
struct ListNode {
	int val;
	int next;
	ListNode(int val, int next) {
		this->val = val;
		this->next = next;
	}
};
int main() {
	unordered_map<int, ListNode*> mp;
	int headAddr = 0, n = 0;
	cin >> headAddr >> n;
	for (int i = 0; i < n; i++) {
		int addr, val, next;
		cin >> addr >> val >> next;
		mp[addr] = new ListNode(val, next);
	}
	int size = 1, cur = 0;
	ListNode* head = mp[headAddr];
	ListNode* thead = head;
	while (thead->next != -1) {
		size++;
		thead = mp[thead->next];
	}
	while (head->next != -1) {
		if ((size / 2) == cur) {
			cout << head->val;
			return 0;
		}
		head = mp[head->next];
		cur++;
	}
	return 0;
}

第三题

给一个无向图染色，可以填红黑两种颜色，必须保证相邻两个节点不能同时为红色,输出有多少种不同的染色方案 第一行输入M(图中节点数) N(边数) 后续N行格式为:V1 V2表示一个V1到V2的边 数据范围:1<=M<=15,0<=N=<M*3,不能保证所有节点都是连通的 思路：这道题本来想用DFS遍历节点然后，但是不怎么会写，后来想到另一个思路，因为有N个节点，且N<=15用一个N位长的数字表示节点的染色方案,用一个vector存储所有的边，然后从0遍历到2^N-1判断每个方案是否合法就可以。 c++代码:

#include<iostream>
#include<utility>
#include<vector>
using namespace std;
typedef pair<int, int> pii;

int main() {
	int m, n;
	cin >> m >> n;
	int ans = 0;
	vector<pii> edges;
	for (int i = 0; i < n; i++) {
		int first, second;
		cin >> first >> second;
		edges.emplace_back(first, second);
	}
	for (int i = 0; i < (1 << m); i++) {
		bool flag = 1;
		for (pii p : edges) {
			if (((i >> p.first) & 1) && ((i >> p.second) & 1)) {
				flag = false;
				break;
			}
		}
		if(flag)ans++;
	}
	cout << ans;
}

评价一下 第一题和别人讨论过，感觉属于是个HARD题，2题最简单，模拟就行，3感觉考察DFS,BFS，这样的话就是一道比较常规的hard题。今天出结果了300分，感觉还行，本来目标是350+的。

2012/12/09

更新一下，一面没问什么，上来就手撕代码，题目为 leetcode 22.括号生成，dfs+回溯。 二面问了比较多再目前公司做的一些项目，八股问了一个concurrentHashMap(部门主要用的Java，虽然我刷题用的C++)手撕代码为leetcode 面试10.01合并排序数组，跟面试官说了一下思路然后面试官让用原地合并。

目前已经拿到offer,华为云,14级，15k，本科刚毕业而且目前工作没啥技术含量，所以没敢要太多。跟在华为的朋友了解了一下情况，他觉得目前华为云还是挺稳定的。