美团嵌入式软件笔试编程题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;
}