【美团笔试】2022-09-11 题解
Debug完了，第一题找到一个O(n)时间复杂度的方法，满足能被11整除的条件是奇数位之和与偶数位之和做差的绝对值能被11整除。这样的话我们可以用末尾是偶数且能被11整除来计算有多少子串，从前往后扫一遍就可以。明天写一下。
第一题：判断一个字符串中能有多少被22整除的子串。【通过率82%】
#include <iostream>
char str[100005];
int get_sub_num(int start) {
int cnt = 0;
int sum = 0;
for (int i = start; str[i]; i++) {
sum += str[i] - '0';
if (sum % 22 == 0) {
cnt++;
}
sum %= 22;
sum *= 10;
}
return cnt;
}
int main() {
scanf("%s", str);
int cnt = 0;
for (int i = 0; str[i]; i++) {
cnt += get_sub_num(i);
}
printf("%d", cnt);
return 0;
}由于第一题我们不知道测评里具体的输入和输出，没办法保证我们的答案是否是正确的，因此我写了一个对数器，correct函数穷举了字符串的所有子串，对每个子串进行了判断。新的方法将写在my_function中。
#include <iostream>
#include <ctime>
#include <cmath>
const int STRING_LENGTH = 100005;
void generate(char* str, int length) {
srand(time(NULL));
char num = rand() % 9 + 1 + '0';
str[0] = num;
for (int i = 1; i < length; i++) {
str[i] = rand() % 10 + '0';
}
str[length] = 0;
}
int get_sub_num(char* str, int start) {
int cnt = 0;
int sum = 0;
for (int i = start; str[i]; i++) {
sum += str[i] - '0';
if (sum % 22 == 0) {
cnt++;
}
sum %= 22;
sum *= 10;
}
return cnt;
}
int correct(char* str) {
int cnt = 0;
for (int i = 0; str[i]; i++) {
cnt += get_sub_num(str, i);
}
return cnt;
}
int my_function(char* str) {
int result =
// input your code here.
return 2;
}
int main() {
char* str = (char*)malloc(sizeof(char) * STRING_LENGTH);
generate(str, 100);
printf("%s\n", str);
int right = correct(str);
int left = my_function(str);
printf("left:%d right:%d\n", left, right);
if (right == left) {
printf("correct\n");
}
else {
printf("failed\n");
}
return 0;
}第二题：判断地铁中每一站有多少与其直接相连。【通过率100%】
#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;
int near[100005];
int index[100005];
int main() {
unordered_map<string, int> mp;
int n = 0;
int m = 0;
int q = 0;
scanf("%d%d%d", &n, &m, &q);
for (int i = 0; i <= n; i++) {
index[i] = i;
}
for (int i = 0; i < m; i++) {
int u = 0;
int v = 0;
scanf("%d%d", &u, &v);
if (u > v) {
swap(u, v);
}
string s = to_string(u) + ',' + to_string(v);
if (mp[s] == 1) {
continue;
}
mp[s] = 1;
near[u]++;
near[v]++;
}
for (int i = 0; i < q; i++) {
int x = 0;
int y = 0;
scanf("%d%d", &x, &y);
swap(index[x], index[y]);
}
for (int i = 1; i <= n; i++) {
printf("%d ", near[index[i]]);
}
return 0;
}第三题：计算愉悦值。【通过率100%】
#include <iostream>
#include <cstring>
using namespace std;
int musicIndex[100005];
int main() {
int n = 0;
int K = 0;
scanf("%d%d", &n, &K);
for (int i = 0; i < 100005; i++) {
musicIndex[i] = 1;
}
int result = 0;
for (int i = 0; i < n; i++) {
int a, b, c, d;
scanf("%d%d%d%d", &a, &b, &c, &d);
if (musicIndex[c] == d) {
result += a;
musicIndex[c]++;
continue;
}
result += max(a - b, -K);
}
printf("%d", result);
return 0;
}第四题：字符串的第k小周期。【通过率100%】
#include <iostream>
#include <cstring>
using namespace std;
char str[100005];
bool isCycle[100005];
int require(int u, int v){
memset(isCycle, 0, sizeof(isCycle));
for(int i = 1; i <= u; i++){
if(isCycle[i]){
continue;
}
bool flag = true;
for(int j = 0; j < u - i; j++){
if(str[j] != str[j + i]){
flag = false;
break;
}
}
if(!flag){
continue;
}
for(int j = 1; j * i <= u; j++){
isCycle[j * i] = true;
}
}
int cnt = 0;
int result = -1;
for(int i = 1; i <= u; i++){
if(!isCycle[i]){
continue;
}
cnt++;
if(cnt == v){
result = i;
break;
}
}
return result;
}
int main(){
scanf("%s", str);
int n = 0;
scanf("%d", &n);
int u = 0;
int v = 0;
while(n--){
scanf("%d%d", &u, &v);
printf("%d\n", require(u, v));
}
return 0;
}第五题：给一串数字，分割为k段后分别进行排序，可得到一升序有序序列，问k最大为多少
感觉单调栈可以做。
投递美团等公司10个岗位 >