字节跳动春招研发部分编程题汇总

一：万万没想到之聪明的编辑

题目描述

给定一个字符串，按照要求修改字符串，输出最后的结果1. 三个同样的字母连在一起，一定是拼写错误，去掉一个的就好啦：比如 helllo -> hello2. 两对一样的字母（AABB型）连在一起，一定是拼写错误，去掉第二对的一个字母就好啦：比如 helloo -> hello3. 上面的规则优先“从左到右”匹配，即如果是AABBCC，虽然AABB和BBCC都是错误拼写，应该优先考虑修复AABB，结果为AABCC

样例

输入例子1:2helloowooooooow输出例子1:hellowoow

思路：

遍历字符串，遇到符合修改条件的就进行修改，这里的问题在于如何动态的维护字符串，暴力解法就是删除完以后刷新一遍字符串， 着很明显是超时的，

这里用j去来存新的字符串， j为下标， 遍历原字符串， 每次遍历都把该字符存到新的字符串的最后一位， 如何判断新的字符串是否满足可以删除的条件， 如果满足， 进行删除

代码

#include <iostream>#include <cstring>using namespace std;string s;int main(){int t;cin >> t;while(t--){cin >> s;int j = 0;//记录新的字符串for(int i = 0; i < s.size(); i++){s[j++] = s[i]; // 刚开始s[0]=s[0]if(j >= 3 && s[j - 2] == s[j - 1] && s[j - 2] == s[j - 3]) // AAA的情况j--; //在下一次循环的时候会把第三个A覆盖掉if(j >= 4 && s[j - 1] == s[j - 2] && s[j - 3] == s[j - 4])// AABB的情况j--;} s.erase(s.begin()+j,s.end());cout << s << endl; }return 0;}

代码二

#include <iostream>#include <cstring>#include <vector> using namespace std;char s[1010];int main(){int n;cin >> n;while(n--){cin >> s;int len = strlen(s);for(int i = 0; i < len; i++){while(i >= 2 && s[i] == s[i - 1] && s[i] == s[i - 2]){for(int k = i - 1; k < len - 1; k++)s[k] = s[k + 1];len--;s[len] = '\0';}while(i >= 3 && s[i] == s[i - 1] && s[i - 3] == s[i - 2]){for(int k = i - 1; k < len - 1; k++)s[k] = s[k + 1];len--;s[len] = '\0';}}cout << s << endl;}return 0;}

二：万万没想到之抓捕孔连顺

题目描述

给定n个数字以及最大距离d， 从中选择3个数， 每两个数字间的大小差距不能超过给定的d求复合要求的方案数， ans对99997867取模

样例

输入例子1:4 31 2 3 4输出例子1:4例子说明1:可选方案 (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)输入例子2:5 191 10 20 30 50输出例子2:1例子说明2:可选方案 (1, 10, 20)

思路：

对于已知的数字串（1， 2， 3）如果加入一个数字4，那么新加的方案数就是在前面的3个数字中选出两个数字的方案数，这时我们就只需要找到前面符合要求的数字是多少个就是了

题目中有两个隐藏条件，给定的数字是升序的并且无重复，所以这里我们只需要用到双指针的思路，遍历数组（i）， 用一个j指向前面的最小满足的数字的下标即可， 这时我们需要的满足要求的数字个数就是(i - j)。

注意由于没有给出数据范围， 我们需要动态开辟空间。

代码

#include <iostream>#include <cstring>using namespace std;const int N = 10010, mod = 99997867;typedef long long ll;ll get_sum(ll n){return (n - 1) * n / 2; //n个数中选出2个 }int main(){ll n, d, ans;cin >> n >> d;ll a[n];ans = 0;for(int i = 0, j = 0; i < n; i++){cin >> a[i];while(i >= 2 && (a[i] - a[j]) > d) j++; //找到前面满足条件的jans += get_sum(i - j); //i - j是j前面满足要求的位置的数量 ans %= mod; }cout << ans << endl;return 0;}

六：找零（贪心）

题目描述

Z国的货币系统包含面值1元、4元、16元、64元共计4种硬币，以及面值1024元的纸币。现在小Y使用1024元的纸币购买了一件价值为n的商品，请问最少他会收到多少硬币？

样例

输入例子1:200输出例子1:17例子说明1:花200，需要找零824块，找12个64元硬币，3个16元硬币，2个4元硬币即可。

思路

每次优先找大的面额的硬币

代码

#include <iostream>#include <cstring>using namespace std;int get_ans(int num){int ans = 0;int money = 64;for(int i = 0; i < 4; i++){ans += num / money;num %= money;money >>= 2;}return ans;} int main(){int n;cin >> n;cout << get_ans(1024 - n) <<endl;return 0;}

七：机器人跳跃问题

题目描述

机器人正在玩一个古老的基于DOS的游戏。游戏中有N+1座建筑——从0到N编号，从左到右排列。编号为0的建筑高度为0个单位，编号为i的建筑的高度为H(i)个单位。 起初， 机器人在编号为0的建筑处。每一步，它跳到下一个（右边）建筑。假设机器人在第k个建筑，且它现在的能量值是E, 下一步它将跳到第个k+1建筑。它将会得到或者失去正比于与H(k+1)与E之差的能量。如果 H(k+1) > E 那么机器人就失去 H(k+1) - E 的能量值，否则它将得到 E - H(k+1) 的能量值。游戏目标是到达第个N建筑，在这个过程中，能量值不能为负数个单位。现在的问题是机器人以多少能量值开始游戏，才可以保证成功完成游戏？

样例

输入例子1:53 4 3 2 4输出例子1:4输入例子2:34 4 4输出例子2:4

思路

根据题目条件我们可以得到这样一个式子，E(k) +(E(k) - H(k + 1)) = E(k + 1), 变形可以得到E(k) = (E(k + 1) + H(k + 1)) / 2, 由于要求我们得到最小的开始能量， 就是最后结束时能量为0， 我们逆推回去就可以得到开始的能量，注意逆推过程中能量要向上取整。

代码

#include <iostream>#include <cstring>#include <vector>#include <cmath>using namespace std;int n;vector<int> a;int main(){cin >> n;for(int i = 0; i < n; i++){int t;cin >> t;a.push_back(t);}int ans = 0;for(int i = a.size() - 1; i >= 0; i--){ans = ceil((double)(ans + a[i]) / 2);}cout << ans << endl;return 0;}

五：毕业旅行问题

题目描述

小明目前在做一份毕业旅行的规划。打算从北京出发，分别去若干个城市，然后再回到北京，每个城市之间均乘坐高铁，且每个城市只去一次。由于经费有限，希望能够通过合理的路线安排尽可能的省一些路上的花销。给定一组城市和每对城市之间的火车票的价钱，找到每个城市只访问一次并返回起点的最小车费花销。

样例

输入例子1:40 2 6 52 0 4 46 4 0 25 4 2 0输出例子1:13

代码

#include <iostream>#include <cstring>#include <vector> using namespace std;int n;int e[25][25];int main(){while(cin >> n){memset(e, 0, sizeof e);int x;for(int i = 0; i < n; i++){for(int j = 0; j < n; j++)cin >> e[i][j];}int f[1 << n][n];memset(f, 0x3f, sizeof f);int inf = f[0][0];//i是一个二进制形式的数，表示经过城市的集合，如0111表示经过了城市0,1,2//j是以j结尾 f[1][0] = 0;//在0这个城市原地 花费是0for(int i = 1; i < 1 << n; i++){for(int j = 0; j < n; j++){if(f[i][j] != inf) //已经访问过了 因为下面是用f[i][j]去更新f[i+(1<<k)][k]的 {for(int k = 0; k < n; k++){if(((i >> k) & 1) == 0 ) // 等于0 说明没有访问过k {f[i | (1 << k)][k] = min(f[i | (1 << k)][k], f[i][j] + e[j][k]); }}}}}int ans = inf;for(int i = 1; i < n; i++){ans = min(ans, f[(1 << n) - 1][i] + e[i][0]); } cout << ans <<endl;}return 0;}