首页 > 8.16字节笔试整理
头像
林不厌
编辑于 2020-08-16 14:09
+ 关注

8.16字节笔试整理

代码是我现在写的,无法提交验证,欢迎大家指正!
第一题给出二叉树前序和中序求有几个叶子节点,跟重建二叉树差不多,但不需要重建。
#include <iostream>
#include <unordered_map>
using namespace std;

int N, leaf, index;
int pre[30010];
int mid[30010];
unordered_map<int, int> mp;
void build_tree(int L, int R){
	if (L >= R) return;
	if (L == R-1){
		++leaf;
		return;
	}
	int val = pre[index];
	++index;
	build_tree(L, mp[val]);
	build_tree(mp[val]+1, R);
}
int main()
{
	cin >> N;
	for (int i = 0; i < N; ++i) cin >> pre[i];
	for (int i = 0; i < N; ++i){
		cin >> mid[i];
		mp[mid[i]] = i;
	}
	leaf = 0;
	index = 0;
	build_tree(0, N);
	cout << leaf << endl;
	return 0;
}
第二题问一个字符串里至少要删去几个字符可以使该字符串不包含“0010”。
没做出来。。。后来讨论区里说只要找有几个“0010”即可,仔细想想确实是,比如00100010至少删去两个字符,0010010至少删去两个字符,001010至少删去一个字符。
#include <iostream>
#include <string>
using namespace std;

string ss;
string now = "0010";
int main()
{
	int T;
	cin >> T;
	while (T--)
	{
		cin >> ss;
		string::size_type pos = 0;
		int ans = 0;
		while ((pos = ss.find(now, pos)) != string::npos){
			++pos;
			++ans;
		}
		cout << ans << endl;
	}
	return 0;
}
第三题给出n段视频,每段视频的时长是L[i],要在视频里插入广告,如果广告间隔时间是x,则第i段视频可以插入L[i]/x+1个广告,现在一共要插入m个广告,求广告间隔时间的最大值。
二分这个间隔时间,左边界是0,表示不能放视频,只能一直放广告,右边界是max{L[i]},因为如果m = n + 1,广告间隔最长就是max{L[i]},其余m > n的情况间隔肯定小于等于max{L[i]}
这题的代码可以确定能过,笔试也是提交的这个。
#include <iostream>
using namespace std;

int n;
long long m;
long long L[100010];
int main()
{
	cin >> n >> m;
	long long right = 0;
	for (int i = 0; i < n; ++i){
		cin >> L[i];
		right = max(L[i], right);
	}
	long long left = 0;
	++right;
	while (left < right){
		long long mid = 1 + left + (right - left) / 2;
		long long sum = 0;
		for (int i = 0; i < n; ++i)
			sum += L[i] / mid + 1;
		if (sum >= m) left = mid;
		else right = mid - 1;
	}
	cout << left << endl;
	return 0;
}
第四题给出n和m,n个数字a[i],每个数字只能用一次,问能凑出的最大的sum%m,sum是数字取和,其中n最大为35,m最大1e9+7。
因为m太大了,如果用dp[i]表示i能不能凑出来,那要开1e9的数组,所以我一开始就放弃了dp的思路。
n很小,所以暴力dfs,每个数字就只有选/不选,复杂度O(2^n),然后过了0.6。
结束以后跟朋友讨论了一下,想到把n个数字分成两组进行暴力dfs,得到的结果分别存在两个set里,set有排序和去重功能。
然后双指针,第一个指针指向set1的头,第二个指针指向set2的尾,把指向的这两个数加起来,更新ans,如果和等于m-1直接结束,如果大于m-1,第二个指针前移,如果小于,第一个指针后移。
dfs复杂度2 * 2^(n/2),双指针复杂度2 * 2^(n/2),最终O(2^(n/2+2))。
#include <iostream>
#include <set>
using namespace std;

int n;
long long m, ans;
long long a[40];
set<long long> s1, s2;

void dfs1(int index, long long sum)
{
	if (index == n/2){
		s1.insert(sum);
		return;
	}
	dfs1(index+1, (sum+a[index])%m);
	dfs1(index+1, sum);
}

void dfs2(int index, long long sum)
{
	if (index == n){
		s2.insert(sum);
		return;
	}
	dfs2(index+1, (sum+a[index])%m);
	dfs2(index+1, sum);
}

int main()
{
	ans = -1;
	cin >> n >> m;
	for (int i = 0; i < n; ++i) cin >> a[i];
	dfs1(0, 0);
	dfs2(n/2, 0);
	auto p = s1.begin();
	auto q = s2.rbegin();
	while (p!=s1.end() && q!=s2.rend()){
		ans = max(ans, (*p+*q)%m);
		if (*p + *q > m-1) 
			++q;
		else if (*p + *q == m-1){
			ans = m-1;
			break;
		}
		else ++p;
	}
	cout << ans << endl;
	return 0;
}




全部评论

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

相关热帖

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

近期精华帖

热门推荐