美团嵌入式软件笔试编程题2

《嵌入式软件开发笔试与面试手册》：https://blog.nowcoder.net/zhuanlan/jvN8gj

《嵌入式软件笔试-2023年真题汇总》：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;
    c