美团嵌入式软件实习笔试编程题
《嵌入式软件开发笔试与面试手册》:https://blog.nowcoder.net/zhuanlan/jvN8gj
《软件开发笔试汇总》:https://blog.nowcoder.net/zhuanlan/0oDWVm
1.小美点外卖
小美是美团外卖的忠实用户,她经常去美团外卖 app 上面点外卖,因为会员红包的性价比太高啦!
现在小美点了若干道菜,她希望你计算一个订单的总价。你能帮帮她吗?
输入描述
第一行输入一个正整数n,代表菜品总数。
第二行输入n个正整数ai,代表每道菜的价格。
第三行输入两个正整数x和y,x代表满减的价格,y代表红包的价格。
1<=n<=10^5
1<=x,y,ai<=10^9
保证所有的和大于,保证会用到满减
输出描述
一个正整数,代表小美最终应付的钱数。
示例 1
输入
4
10 20 10 20
25 10
输出
25
说明
四个菜一共 60 元,满减减掉了 25 元,再用一个 10 元的红包,因此需要付 25 元。
#include <iostream> using namespace std; int main() { int num; long long sum = 0; cin >> num; for (int i = 0; i < num; i++) { long long temp; cin >> temp; sum += temp; } long long l1, l2; cin >> l1 >> l2; sum = sum - l1 - l2; cout << sum << endl; return 0; }
2.小美的合法单词
小美定义以下三种单词是合法的:
- 所有字母都是小写。例如:good
- 所有字母都是大写。例如:APP
- 第一个字母大写,后面所有字母都是小写。例如:Alice
现在小美拿到了一个单词,她每次操作可以修改任意一个字符的大小写。小美想知道最少操作几次可以使得单词变成合法的?
输入描述
一个仅由大写字母和小写字母组成的字符串,长度不超过10^5。
输出描述
一个整数,代表操作的最小次数。
示例 1
输入
AbC
输出
1
说明
变成 ABC 或者 Abc 均可。只需要一次操作。
#include <iostream> #include <string> #include <algorithm> using namespace std; int main() { string s; getline(cin, s); int small = 0, big = 0; int res = s.length(); for (size_t i = 0; i < s.length(); ++i) { if(s[i] >= 'a' && s[i] <= 'z') small++; else if(s[i] >= 'A' && s[i] <= 'Z') big++; } int temp = s.length(); if(s[0] >= 'A' && s[0] <= 'Z') temp = s.length() - 1 - small; res = min({small, big, temp}); // 使用min函数计算三个数中的最小值 cout << res << endl; return 0; }
3、翻倍元素
小美拿到了一个数组,她每次操作会将除了第x个元素的其余元素翻倍,一共操作了q次。请你帮小美计算操作结束后所有元素之和。
由于答案过大,请对10^9+7取模。
输入描述
第一行输入两个正整数n,q,代表数组的大小和操作次数。 第二行输入n个正整数ai,代表数组的元素。 第三行输入一个正整数q,代表操作的次数。 接下来的q行,每行输入一个正整数xi,代表第i次操作未被翻倍的元素。 1<=n,q<=10^5 1<=xi<=n 1<=ai<=10^9
输出描述
一个整数,代表操作结束后所有元素之和模10^9+7的值。
示例
输入
4 2 1 2 3 4 1 2
输出
34
说明
第一次操作后,数组变成[1,4,6,8] 第二次操作后,数组变成[2,4,12,16] 所有元素之和为 34。
#include <iostream> #include <vector> using namespace std; const int MOD = 1000000007; // 快速幂算法 long long fast_power(long long base, long long exp, long long mod) { long long result = 1; while (exp > 0) { if (exp % 2 == 1) { result = (result * base) % mod; } base = (base * base) % mod; exp /= 2; } return result; } // 主函数,解决问题 long long solve(int n, int q, vector<int>& a, vector<int>& operations) { // 初始化跳过计数数组 vector<int> skip_count(n, 0); // 计算每个元素被跳过的次数 for (int x : operations) { skip_count[x - 1]++; } // 计算最终的和 long long final_sum = 0; for (int i = 0; i < n; i++) { // 计算元素ai的最终乘数 long long element_power = fast_power(2, q - skip_count[i], MOD); //计算2的幂,就是翻倍的次数 long long final_value = (static_cast<long long>(a[i]) * element_power) % MOD; // 累加到最终和 final_sum = (final_sum + final_value) % MOD; } return final_sum; } int main() { int n, q; cin >> n >> q; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } vector<int> operations(q); for (int i = 0; i < q; i++) { cin >> operations[i]; } cout << solve(n, q, a, operations) << endl; return 0; }
4.小美的众数
小美拿到了一个数组。她希望你求出所有区间众数之和。你能帮帮她吗?
定义区间的众数为出现次数最多的那个数。如果有多个数出现次数最多,那么众数是其中最小的那个数。
输入描述
第一行输入一个正整数n,代表数组的大小。
第二行输入n个正整ai,代表数组的元素。
1<=n<=200000
1<=ai<=2
输出描述
一个正整数,代表所有区间的众数之和。
示例 1
输入
3
2 1 2
输出
9
说明
[2],[2,1,2],[2]的众数是 2。[2,1],[1],[1,2]的众数是 1。因此答案是 9。
#include <iostream> #include <vector> using namespace std; int main() { int n; cin >> n; vector<int> arr(n); for (int i = 0; i < n; i++) { cin >> arr[i]; } const int MOD = 1000000007; long long result = 0; // 用于存储1和2的数量 vector<long long> count_1(n + 1, 0), count_2(n + 1, 0); // 初始化前缀和数组 for (int i = 0; i < n; i++) { count_1[i + 1] = count_1[i] + (arr[i] == 1); count_2[i + 1] = count_2[i] + (arr[i] == 2); } // 遍历所有可能的子区间 for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { int c1 = count_1[j + 1] - count_1[i]; // 从i到j的1的数量 int c2 = count_2[j + 1] - count_2[i]; // 从i到j的2的数量 if (c1 > c2) { result += 1; } else if (c1 < c2) { result += 2; } else { // c1 == c2 result += min(arr[i], arr[j]); } result %= MOD; } } cout << result << endl; return 0; }#软件开发2024笔面经#
本专栏主要发布2024年嵌入式软件开发相关岗位笔试真题(嵌入式软件开发、通用软件开发、C/C++软件开发、算法工程师、测试开发等)主要是算法编程题,其中一些岗位笔试含有对应的选择题、填空题、简单题。