代码是我现在写的，无法提交验证，欢迎大家指正！
第一题给出二叉树前序和中序求有几个叶子节点，跟重建二叉树差不多，但不需要重建。
#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) 回帖