记录一次华为od题

一、箱子之形摆放

题目描述：

要求将一批箱子按从上到下以‘之’字形的顺序摆放在宽度为n的空地上，输出箱子的摆放位置，例如：箱子ABCDEFG，空地宽为3，摆放效果如下图：

则输出结果为：

AFG

BE

CD

输入：
一行字符串，通过空格分割两部分，前面str部分表示箱子的字符串由数字或字母组成，后面部分是表示宽度的数字n，如下：
ABCDEFG 3

输出：
AFG
BE
CD

注：最后一行不得输出额外的空行

str只包含数字和数字，1<=len(str)<=1000，1<=n<=1000。

#include <iostream>
#include <string>
#include <vector>
using namespace std;

void solution(string s, int width) {
	if (width < 2)
		cout << s;
	int index=0;
	bool flag = true;
	vector<string> st(3, "");
	for (auto ch : s) {
		if (index == -1) {
			index = 0;
			flag = true;
		}
		if (index == width) {
			index--;
			flag = false;
		}
		st[index]+=ch;
		if (flag)
			index++;
		else
			index--;
	}
	for (auto str : st)
		cout << str << endl;
}

int main() {

	int width;
	string in;
	cin >> in >> width;
	solution(in, width);
	return 0;
}

上面是构建了一个存三个字符串的数组，然后有index作为控制，迭代处理字符串s，当index递增到宽度上限，就反过来递减，当index递减到宽度下限，就再反过来递增。类似的题目是z字形字符串：

[leetcode地址](https://leetcode.cn/problems/zigzag-conversion/)

牛客上的是：NC344 Z字形输出字符串

二、微服务的集成测试

描述：有n个容器服务，容器的启动可能有依赖性，也可能没有，另外，服务的启动需要一定的时间加载，给一个nxn的二维矩阵useTime，useTime的值具有特定意义，useTime[i][i]表示服务i+1的启动需要的时间，useTime[i][j]=1表示服务i+1的启动需要依赖服务j+1，useTime[i][j]=0表示服务i+1的启动不依赖于服务j+1，需要得出服务k的最短启动时间。

三、快递业务站

描述：

有n个快递点，快递点A、B可中装快递，就可以认为A-B可达，如果A-B可达且B-C可达，则A-C可达。针对n个快递站进行编号：0、1、2.。。。。。。n-1，s[i][j]来表示i-j是否可达，值为1表示可达，值为0则是不可达，所以输入是一个二维矩阵，需要计算出至少选择从几个主站点出发，才能达到所有站点。

注：s[i][j]==s[j][i]，第一行输入是快递点数量也是二维矩阵的维数。

输入：
4
1 1 1 1
1 1 1 0
1 1 1 0
1 0 0 1
输出：
1

说明：选择0站点为主站点可到达所有站点。

输入：
4
1 1 0 0
1 1 0 0
0 0 1 0
0 0 0 1
输出：
3

说明：

选择0站点为主站点可以覆盖0、1站点，

选择2站点为主站点可以覆盖2站点，

选择3站点为主站点可以覆盖3站点，

所以需要至少三个站点为主站点可以覆盖所有站点。

解：

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

int solution(vector<vector<int>> vec, int n) {
	if (n < 2)
		return 1;
	int cnt = 0, i, j;
	unordered_set<int> st;
	for (i = 0; i < n; i++) {
		if (st.find(i) != st.end()) {
			cnt++;
		}
		vector<int> tmp = vec[i];
		for (j = 0; j < tmp.size(); j++) {
			if (tmp[j] == 1)
				st.insert(j);
		}
	}
	return cnt;
}

int main() {

	int n, tmp, i, j;
	cin >> n;
	vector<vector<int>> st;
	for (i = 0; i < n; i++) {
		vector<int> t;
		for (j = 0;j<n;j++) {
			cin >> tmp;
			t.push_back(tmp);
		}
		st.push_back(t);
	}
	cout << solution(st, n) << endl;
	return 0;
}

----------------------------------------------------------

得到网友资助，更新一下第二题，原定描述不变，添加一下输入和输出描述：

输入：
第一行是代表二维矩阵维数的数字n，后面是对应二维矩阵，最后一行数字，代表服务k

3
5 0 0
1 5 0
0 1 5
3

输出：
15

根据java解法思路稍微改动，解答如下：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

void solution(vector<vector<int>> vec, int n, int index) {
	vector<vector<int>> upstream(n);
	int i, j, res=vec[index][index];
	//初始化前置任务
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
			if (i != j && vec[i][j] == 1)
				upstream[i].push_back(j);

	//保存服务列表
	queue<vector<int>> sq;
	sq.push(upstream[index]);
	
	while (sq.size() > 0) {
		vector<int> upstream_tasks = sq.front();
		sq.pop();
		vector<int> services;
		int size = upstream_tasks.size(), res_tmp=0;
		for (i = 0; i < size; i++) {
			res_tmp = max(res_tmp, vec[i][i]);
			for (j = 0; j < upstream[upstream_tasks[i]].size(); j++)
				services.push_back(upstream[upstream_tasks[i]][j]);
		}
		res += res_tmp;
		if (services.size() > 0)
			sq.push(services);
	}
	cout << res << endl;
}

int main() {

	int n, tmp, i, j, k;
	cin >> n;
	vector<vector<int>> st;
	for (i = 0; i < n; i++) {
		vector<int> t;
		for (j = 0;j<n;j++) {
			cin >> tmp;
			t.push_back(tmp);
		}
		st.push_back(t);
	}
    cin >> k; k--;
	solution(st, n, k);
	return 0;
}

稍微魔改后的解法，只过了上面的范例，因为也没有其他范例可以尝试了，没有考虑高效与否并且建立在给入n、二维矩阵和k合规的情况，放到实际肯定要考虑invalid。最后，感谢网友的分享，万分感谢。