因为字节跳动的笔试不能本地IDE编辑，所以考完试后，凭着记忆再写一下代码，如有笔误，希望大佬们可以指正！谢谢！
【第一题】一棵二叉树，每个节点都有唯一的正整数值代表节点，在遍历时，我们使用节点的整数值作为标记，求二叉树叶子节点个数。
输入：第一行为二叉树节点个数。第二行和第三行分别为前序和中序遍历结果
输出：二叉树叶子节点个数
思路：直接按照建树的方式（不用建树），搜索到只有一个节点的时候累加叶子节点数量
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn = 30005;
int pre[maxn];
int mid[maxn];
void dfs(int prel, int prer, int midl, int midr, int& ans) {
if(prel > prer) return;
if(prel == prer) {++ans; return;}
int root = pre[prel];
int index = midl - 1;
for(int i = midl; i <= midr; ++i) {
if(mid[i] == root) {index = i; break;}
}
int lnum = index - midl;
int rnum = midr - index;
dfs(prel + 1, prel + lnum, midl, index - 1, ans);
dfs(prel + lnum + 1, prer, index + 1, midr, ans);
}
int main(void)
{
#ifndef ONLINE_JUDGE
freopen("a.txt", "r", stdin);
#endif
//faster_cin_cout;
int n;
while(cin >> n) {
for(int i = 1; i <= n; ++i) cin >> pre[i];
for(int i = 1; i <= n; ++i) cin >> mid[i];
int ans = 0;
dfs(1, n, 1, n, ans);
cout << ans << endl;
}
return 0;
}
【第二题】编码协议：给出一个十六进制数组成的字符串，问最少去掉几个字符，使得剩下的字符串不存在‘0010’
输入：t(样例数）
接下来依次出入t个字符串s
输出：每个字符串对应的最少去掉字符数
思路：查找下有几个“0010”就是答案了，细节：下一次查找的时候，需要从1的下一个0开始查找
代码：
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
#ifndef ONLINE_JUDGE
freopen("b.txt", "r", stdin);
#endif
//faster_cin_cout;
int n;
string s;
string p = "0010";
while(cin >> s) {
int cnt = 0;
size_t found = s.find(p, 0);
while(found != string::npos) {
++cnt;
found += 3;
if(found >= s.size()) break;
found = s.find(p, found);
}
cout << cnt << endl;
}
return 0;
}
【第三题】N个视频，每个视频时长为L_i秒，在其中插M个广告。一个视频里两个广告必须间隔一段时间（间隔时间可以为0），间隔时长为整数。
帮忙计算间隔时间最大可设置多少秒，如不能插入M条广告，输出0。
ps:考试过程中补充 ： 可无限插入广告
输入 ：N，M
第二行输入N个整数L_i
输出：最大间隔
暂时没有好的思路，希望路过的大佬们都可以留下你们的解法！
【第四题】寻觅：在n个正整数中，任意挑选k个（不可重复挑选，0 <= k <= n）,数字和记为sum。另有一个正整数m，请问sum % m最大是多少？
输入：n,m
第二行输入n个正整数
输出：sum % m的最大值
思路：考虑到n = 35，而且m很大，所以简单的01背包肯定不能直接用，因为背包容量太大了。可以分成两半进行搜索，然后找<m的最大值即可；
代码：
#include<bits/stdc++.h>
using namespace std;
int a[40];
void dfs(int left, int right, int sum, set<int>& s) {
if(left > right) return;
s.insert(sum);
dfs(left + 1, right, sum + a[left], s);
dfs(left + 1, right, sum, s);
}
int main(void)
{
#ifndef ONLINE_JUDGE
freopen("d.txt", "r", stdin);
#endif
//faster_cin_cout;
int n, m;
while(cin >> n >> m) {
for(int i = 1; i <= n; ++i) cin >> a[i];
set<int> left;
set<int> right;
dfs(1, n/2, 0, left);
dfs(n/2+1, n, 0, right);
vector<int> rights(right.begin(), right.end());
int ans = 0;
for(int l : left) {
auto r = lower_bound(rights.begin(), rights.end(), m - l);
if(r == rights.end()) {
ans = max(ans, rights.back() + l);
} else if(r != rights.begin()) {
r--;
ans = max(ans, *r + l);
}
}
cout << ans << endl;
}
return 0;
}
全部评论
(4) 回帖