字节9.12笔试

总体来说前面两题满分，后面两个题过了部分，

# 第一题

这个就是原题，华为之前的环形打车问题也是这个

253. 会议室 II

1. 这个题把它想成公交车上最多的乘客数量问题，公交车上乘客上上下下，某时刻车上有多人？最多人是多少？

2. 记录上车+1，下车减1，按时间轴排序

3. 其实也就模拟的公交车上下车

4. 答案就是公交车乘客最大值

5. 案例中有大数，需要long long

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char *argv[]) {
	int cases;
	cin >> cases;
	while (cases-- > 0) {
		int n;
		cin >> n;
		vector<vector<long long>> nums(n, vector<long long>(2, 0));
		int x, y;
		for (int i = 0; i < n; ++i) {
			cin >> x >> y;
			nums[i][0] = x;
			nums[i][1] = x+y;
		}

		vector<pair<long long, int>> res;
		for (int i = 0; i < n; ++i) {
			res.push_back({nums[i][0], 1});					/**<上车 */
			res.push_back({nums[i][1], -1});				/**<下车 */
		}
		sort(res.begin(), res.end());						/**<按照时间点排序 */

		int ans = 0;
		int output = 0;
		for (const auto& e : res) {
			ans += e.second;
			output = max(output, ans);						/**<公交车上最多的乘客 */
		}
		cout << output << '\n';
	}

	return 0;
}


#if 0
1
2
1 2
2 3
output
2

#endif

# 第二题

1. 先建立一棵二叉树createTree

105. 从前序与中序遍历序列构造二叉树

2. 由于每个结点都是唯一的，因此可以记住maxValue

3. 通过辅助函数helper来判断结构是否对称--先序遍历，原题链接

101. 对称二叉树

4. 遍历过程中取到对称位置的结点

5. 获取先序遍历的结果，为真则输出对称位置，否则输出原始节点

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int val) : val(val), left(nullptr), right(nullptr) {}
};

/** \brief      createTree  先序、中序建树
 *  \author     wzk
 *  \copyright  GNU Public License
 *  \version    1.0 
 *  \date       2020-9-12
 * 
 *  \param[in] pre 		输入pre数组
 *  \param[in] preStart 输入pre左闭
 *  \param[in] preEnd  	输入pre右闭
 *  \param[in] in  		输入in数组
 *  \param[in] inStart  输入in左闭
 *  \param[in] inEnd   	输入in右闭
 *  \param[in] memo    	输入中序遍历的hash表
 *  \return             返回二叉树
 */
TreeNode *createTree(vector<int>& pre, int preStart, int preEnd, vector<int>& in, int inStart, int inEnd, unordered_map<int,int>& memo) {
	if (preStart>preEnd || inStart>inEnd)
		return nullptr;
	
	TreeNode *root = new TreeNode(pre[preStart]);
	int pos = memo[pre[preStart]];															/**<根结点在中序遍历数组的位置 */
	int numsLeft = pos - inStart;															/**<左子树元素个数 */
	root->left = createTree(pre, preStart+1, preStart+numsLeft, in, inStart, pos-1, memo);
	root->right = createTree(pre, preStart + numsLeft + 1, preEnd, in, pos + 1, inEnd, memo);
	return root;
}

int maxValue = 0;														/**<最大节点值 */
int point = 0;															/**<对称节点值 */
bool helper(TreeNode *root1, TreeNode *root2) {
	if (!root1 && !root2)
		return true;
	if (!root1 || !root2)
		return false;

	/**<取对称结点 */
	if (root1->val == maxValue) {
		point = root2->val;
	} else if (root2->val == maxValue) {
		point = root1->val;
	}

	return helper(root1->left, root2->right) && helper(root1->right, root2->left);
}


// 内存释放，考试的时候不用考虑，先做对
void freeTree(TreeNode* root) {
    if(root == nullptr)
        return;
    freeTree(root->left);
    freeTree(root->right);
    delete root;
}

int main(int argc, char *argv[]) {
	int n;
	cin >> n;
	vector<int> pre(n, 0);
	for (int i = 0; i < n; i++) {
		cin >> pre[i];
		maxValue = max(maxValue, pre[i]);				/**<求解最大值，因为没有相同的值 */
	}
	vector<int> in(n, 0);
	for (int i = 0; i < n; i++) {
		cin >> in[i];
	}

	unordered_map<int, int> memo;
	for (int i = 0; i < n; i++) {
		memo[in[i]] = i;
	}

	TreeNode *root = createTree(pre, 0, n-1, in, 0, n-1, memo);
	bool output = helper(root->left, root->right);
	if (output)														/**<在对称的前提下，输出对称点 */
		cout << point << '\n';
	else
		cout << maxValue << '\n';

	freeTree(root);
	return 0;
}


#if 0
3
1 3 4
3 1 4
output: 3

5
1 3 5 7 4
5 3 1 4 7
output: 7

#endif

# 第三题

是个大数问题，希望通过的大佬补充

# 第四题

我的没全过，希望通过的大佬补充

#字节笔试##字节跳动##笔经#