因为字节跳动的笔试不能本地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) 回帖