字节跳动-多媒体嵌入式笔试
1、将若干数组合并，降序排列。
输入描述：第一行输入正整数n，表示数组个数。
后续n行，每行代表一个数组。
数组长度和<=10e6。数组元素值<=10e9。
示例
输入：
2
[1,4,6]
[2,3,5]
输出：
[6,5,4,3,2,1]
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <sstream>
using namespace std;
int main() {
int n;
cin >> n;
cin.ignore(); // 忽略到行末，准备读取数组
vector<long long> all_elements; // 使用long long以支持大整数
string line;
while (n-- > 0) {
getline(cin, line); // 读取整行输入
istringstream iss(line);
char bracket, comma;
long long num;
iss >> bracket; // 读取 '['
while (iss >> num) { // 读取每个数字
all_elements.push_back(num);
iss >> comma; // 读取 ',' 或 ']'
}
}
// 对所有元素进行降序排序
sort(all_elements.begin(), all_elements.end(), greater<long long>());
// 输出排序后的数组
cout << '[';
if (!all_elements.empty()) {
cout << all_elements[0];
for (size_t i = 1; i < all_elements.size(); ++i) {
cout << ',' << all_elements[i];
}
}
cout << ']' << endl;
return 0;
}
2、将数组某个区间的元素各自进行翻转，希望最终所有的元素和尽可能大。
翻转就是将1234变为4321。
输入：第一行输入元素个数n，第二行输入n个正整数。
示例：
输入：
4
126 30 48 42
输出：
750（翻转 126 30 48）
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int reverseNumber(int num) {
int rev = 0;
while (num > 0) {
rev = rev * 10 + num % 10;
num /= 10;
}
return rev;
}
int maxSumAfterReverse(const vector<int>& nums) {
int n = nums.size();
vector<int> gain(n); // 存储每个元素翻转可能带来的增益
int totalSum = 0;
// 计算每个元素的原始和和翻转增益
for (int i = 0; i < n; ++i) {
int reversed = reverseNumber(nums[i]);
gain[i] = reversed - nums[i];
totalSum += nums[i];
}
// 找到最大的增益子数组
int maxGain = 0;
int currentMax = 0;
for (int i = 0; i < n; ++i) {//这里其实就转换成了计算最大连续子数组的和
currentMax = std::max(gain[i], currentMax + gain[i]);
maxGain = std::max(maxGain, currentMax);
}
// 计算可能的最大总和
return totalSum + maxGain;
}
int main() {
int n;
cin >> n;
vector<int> nums(n);
for (int i = 0; i < n; ++i) {
cin >> nums[i];
}
cout << maxSumAfterReverse(nums) << endl;
return 0;
}
3、给定一个仅包含“YCH”字符的字符串，每次给定一个区间，输出重排给定区间子串可以得到 多少种不同的回文串。
输入：第一行输入正整数n，q，代表字符串的长度和给定的区间个数。
第二行输入长度为n的字符串。后续q行输入两个整数表示区间l，r。
示例：
4 3
YYCC
1 2
1 4
2 3
输出：
1
2
0
#include <iostream>
#include <vector>
#include <string>
using namespace std;
const int MOD = 1000000007;//这个是题意说的不会超过这个值
// 计算阶乘和阶乘的逆元
vector<long long> fact, ifact;
long long power(long long x, int y, int p) {
long long res = 1;
x = x % p;
while (y > 0) {
if (y & 1)
res = (res * x) % p;
y = y >> 1;
x = (x * x) % p;
}
return res;
}
void computeFactorials(int max_n) {
fact.resize(max_n + 1, 1);
ifact.resize(max_n + 1, 1);
for (int i = 2; i <= max_n; i++)
fact[i] = fact[i - 1] * i % MOD;
ifact[max_n] = power(fact[max_n], MOD - 2, MOD); // Fermat's little theorem
for (int i = max_n - 1; i >= 1; i--)
ifact[i] = (ifact[i + 1] * (i + 1)) % MOD;
}
// 计算排列数 P(n, k) = n! / (n-k)!
long long permutation(int n, int k) {
if (k > n) return 0;
return fact[n] * ifact[n - k] % MOD;
}
int countPalindromes(const vector<int>& count) {
int odd = 0, length = 0;
for (int c : count) {
if (c % 2 == 1) odd++;
length += c;
}
if (odd > 1) return 0; // 无法形成回文
if (odd == 0 && length % 2 == 1) return 0; // 奇数长度但没有奇数次字符
int half_length = length / 2;
//这里有一个bug，题中说不同的回文串，所有要统计每个字符的重复个数，然后再将下式结果除以这些相同字符的组合数
return permutation(half_length, half_length); // 计算 P(half_length, half_length) 即 half_length!
}
int main() {
int n, q;
cin >> n >> q;
string s;
cin >> s;
// 前缀和数组
vector<int> count_y(n + 1, 0), count_ce(n + 1, 0), count_h(n + 1, 0);
for (int i = 0; i < n; i++) {
count_y[i + 1] = count_r[i] + (s[i] == 'Y');
count_c[i + 1] = count_e[i] + (s[i] == 'C');
count_h[i + 1] = count_d[i] + (s[i] == 'H');
}
computeFactorials(n / 2 + 1);
while (q--) {
int l, r;
cin >> l >> r;
vector<int> counts(3);
counts[0] = count_r[r] - count_r[l - 1]; // 'Y'
counts[1] = count_e[r] - count_e[l - 1]; // 'C'
counts[2] = count_d[r] - count_d[l - 1]; // 'H'
cout << countPalindromes(counts) << endl;
}
return 0;
}
4、给定一个由字符组成的二维矩阵，定义一个移动方式：如果当前坐标为(x0,y0),那么下一个点的坐标(x,y)需要满足|x-x0|+|y-y0|=3,且x!=x0,y!=y0.
输入：第一行输入两个正整数n,m表示矩阵的行和列。接下来n行每行输入m个字符。
输出：得到”step“的移动方案数。
示例：
输入：
3 4
m s p l
o k j t
i e r y
输出：1
参考代码：
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>
using namespace std;
// 用哈希表存储可以通过跳马步到达的点
typedef unordered_set<int> PointsSet;
typedef unordered_map<int, PointsSet> PointsMap;
// 为方便处理，将二维坐标转换为一维索引
inline int index(int x, int y, int m) {
return x * m + y;
}
// 计算跳马步可能的八个方向，并存储可到达的位置
void addJumpSteps(int x, int y, int n, int m, PointsMap& reachable, char target, const vector<string>& matrix) {
vector<pair<int, int>> directions = {
{2, 1}, {2, -1}, {-2, 1}, {-2, -1},
{1, 2}, {1, -2}, {-1, 2}, {-1, -2}
};
int idx = index(x, y, m);
for (auto& dir : directions) {
int nx = x + dir.first;
int ny = y + dir.second;
if (nx >= 0 && nx < n && ny >= 0 && ny < m && matrix[nx][ny] == target) {
reachable[idx].insert(index(nx, ny, m));
}
}
}
int findByte(int n, int m, const vector<string>& matrix) {
PointsMap s_to_t, t_to_e, e_to_p;
// 预处理所有可能的跳跃步
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (matrix[i][j] == 's') addJumpSteps(i, j, n, m, s_to_t, 't', matrix);
if (matrix[i][j] == 't') addJumpSteps(i, j, n, m, t_to_e, 'e', matrix);
if (matrix[i][j] == 'e') addJumpSteps(i, j, n, m, e_to_p, 'p', matrix);
}
}
// 计算可能的"step"组合
int count = 0;
for (auto& s : s_to_t) {
for (auto& t_idx : s.second) {
if (t_to_e.find(t_idx) != t_to_e.end()) {
for (auto& e_idx : t_to_e[t_idx]) {
if (e_to_p.find(e_idx) != e_to_p.end()) {
count += e_to_p[e_idx].size();
}
}
}
}
}
return count;
}
int main() {
int n, m;
cin >> n >> m;
vector<string> matrix(n);
for (int i = 0; i < n; i++) {
cin >> matrix[i];
}
cout << findByte(n, m, matrix) << endl;
return 0;
}
#嵌入式##我的实习求职记录##通信硬件人笔面经互助##字节#嵌入式学习免费专栏 文章被收录于专栏
分享嵌入式软件开发相关资料，专栏永久免费，嵌入式学习技术交流
投递虹软科技等公司8个岗位 >