美团嵌入式软件笔试编程题2
《嵌入式软件开发笔试与面试手册》:https://blog.nowcoder.net/zhuanlan/jvN8gj
《软件开发笔试汇总》:https://blog.nowcoder.net/zhuanlan/0oDWVm
小美的01矩阵
小美拿到了一个n行m列的矩阵,她想知道该矩阵有多少个 2*2 的子矩形满足 1 和 0 的数量相等?
输入描述
第一行输入两个正整数n,m用空格隔开。
接下来的n行,每行输入一个长度为m的 01 串,用来表示矩阵。
2<=n,m<=100
输出描述
一个整数,代表 1 和 0 的数量相等的 2*2 的子矩形数量。
示例 1
输入
2 3
110
010
输出
1
说明
两个 2*2 的子矩形,只有一个是合法的。
#include <iostream> #include <vector> using namespace std; int main() { int n, m; cin >> n >> m; vector<vector<int> >matrix(n, vector<int>(m)); for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { char c; cin >> c; matrix[i][j] = c - '0'; } } int ans = 0; for(int i = 0; i < n-1; i++) { for(int j = 0; j < m-1; j++) { if(matrix[i][j] + matrix[i][j+1] + matrix[i+1][j] + matrix[i+1][j+1] == 2) { ans += 1; } } } cout << ans << endl; return 0; }
小美的回文子串
小美有一个长为 n的字符串s,她希望删除尽可能少的字符,使得字符串不含长度为偶数的回文子串。
她想知道她最少要删除几个字符,请你帮帮她吧。
输入描述
输入包含两行。
第一行一个正整数n(1<=n<=10^5),表示字符串s 的长度。
第二行一个长为n字符串s。
输出描述
输出包含一行一个整数,表示最少删除数量。
补充说明
子串:一个字符串从头或尾删除若干个(也可以不删)得到的结果字符串。回文:一个字符串正着读和倒着读一样,则该字符串回文。
示例 1
输入
5
aaabc
输出
2
示例 2
输入
1
e
输出
0
#include <iostream> #include <string> using namespace std; int main() { int n; cin >> n; // 读取字符串的长度(虽然在这个代码中未直接使用) string str; cin >> str; // 读取字符串 int ans = 0; // 遍历字符串,计算连续相同字符的数量 for (int i = 1; i < n; ++i) { // 从索引1开始,方便比较前一个字符 if (str[i] == str[i-1]) { // 如果当前字符与前一个字符相同 ans += 1; // 累加连续相同字符的数量 } } cout << ans << endl; // 输出结果 return 0; }
小美的元素交换
小美拿到了一个排列,其中初始所有元素都是红色,但有一些元素被染成了白色。
小美每次操作可以选择交换任意两个红色元素的位置。她希望操作尽可能少的次数使得数组变成非降序,你能帮帮她吗?
排列是指:一个长度为n的数组,其中 1 到n每个元素恰好出现了一次。
输入描述
第一行输入一个正整数n,代表数组的长度。
第二行输入n个正整数ai,代表数组的元素。
第三行输入一个长度为n的字符串,代表数组元素的染色情况。第i个字符为'R'代表第i个元素被染成红色,为'W'代表初始的白色。
1<=n<=10^5
1<=ai<=n
输出描述
如果无法完成排序,请输出 -1。否则输出一个整数,代表操作的最小次数。
示例 1
输入
4
1 3 2 4
WRRW
输出
1
说明
第一次操作,交换 2 和 3,数组变成[1,2,3,4]
#include <iostream> #include <vector> #include <unordered_map> #include <limits> using namespace std; int main() { int n; cin >> n; vector<int> nums(n); for (int i = 0; i < n; i++) { cin >> nums[i]; } vector<char> colors(n); for (int i = 0; i < n; i++) { cin >> colors[i]; } unordered_map<int, int> dic; for (int i = 0; i < n; i++) { dic[nums[i]] = i; } int ans = 0; const int inf = numeric_limits<int>::max(); for (int i = 0; i < n; i++) { if (nums[i] == i + 1) continue; if (colors[i] == colors[dic[i + 1]] && colors[i] == 'R') { ans += 1; int targetIndex = dic[i + 1]; swap(nums[i], nums[targetIndex]); dic[nums[i]] = i; dic[nums[targetIndex]] = targetIndex; } else { ans = inf; break; } } if (ans == inf) { cout << -1 << endl; } else { cout << ans << endl; } return 0; }
小美的字符串切割
小美定义一个字符串的权值为:字符串长度乘以字符的种类数。例如,"arcaea"的权值为 6*4=24
现在小美拿到了一个字符串,她希望你将该字符串切割成若干个连续子串,使得每个子串的权值不小于k。请你求出最终最多可以切割出的子串数量。
请注意,由于字符串过长,给出的字符串将是以连续段长度形式给出,例如:aabbaaa 将描述为 a(2)b(2)a(3),aaaaaaaaaaaab 将描述为 a(12)b(1)。
输入描述
第一行输入一个两个正整数 n,k,代表原字符串长度和每个子串至少应取的权值。
第二行一个仅包含小写字母、数字和括号的字符串。长度不超过 10^6。
保证所有括号内的数字之和恰好等于n。给定的每个字母后面必然包含一个括号加数字。
1<=k,n<=10^18
输出描述
如果整个字符串的权值小于k,请直接输出 -1。
否则输出一个正整数,代表可以切割的最多子串数量。
示例 1
输入
7 6
a(2)b(2)a(3)
输出
2
说明
该字符串表示为"aabbaaa",切割成"aab"和"baaa"即可。
示例 2
输入
1000000000 5
x(1000000000)
输出
200000000
说明
该字符串表示为"xxx……x",共有10^9个 x,可以切割成 200000000 个"xxxxx"
#include<bits/stdc++.h> using namespace std; #define ll long long const int maxn=2e6+10; ll n,k; char a[maxn],s[maxn]; ll num[maxn]; ll cnt[30]; int len,i,j; int main(){ scanf("%lld %lld",&n,&k); scanf("%s",a+1); len = strlen(a+1); // 将字符串转换成字母和数字的形式,s存字母,num存该字母出现次数 for(i=1,j=1;i<=len;){ if(a[i]>='a'&&a[i]<='z'){ s[j]=a[i]; i+=2; if(i<=len){ ll tmp=0; while(a[i]!=')'){ tmp=tmp*10+(a[i]-'0'); i++; } i++; num[j]=tmp; j++; }else{ break; } } } ll diff=0,tmp=0,ans=0; for(i=1;i<j;){ // 如果该字母没出现过 if(cnt[s[i]-'a']==0){ diff++; cnt[s[i]-'a']++; } // 如果符合条件了 if((tmp+num[i])*diff>=k){ // 计算符合条件需要的最少数量 ll sub = max(k/diff-tmp,1ll); while((tmp+sub)*diff<k){// 循环次数很少,不会超时 sub++; } num[i]-=sub; if(num[i]==0){// 如果最少数量也用光了当前字母,那么移动到下一个字母 i++; } // 否则,当前字母还有剩余,i不变,继续下一次统计 memset(cnt,0,sizeof cnt); diff=0; tmp=0; ans++; } else{ tmp+=num[i]; i++; } } if(ans==0){ printf("-1"); }else{ printf("%lld",ans); } return 0; }#美团##嵌入式##软件##笔试#
本专栏主要发布2024年嵌入式软件开发相关岗位笔试真题(嵌入式软件开发、通用软件开发、C/C++软件开发、算法工程师、测试开发等)主要是算法编程题,其中一些岗位笔试含有对应的选择题、填空题、简单题。