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

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

《软件开发笔试汇总》：https://blog.nowcoder.net/zhuanlan/0oDWVm

点赞&&评论mark超10，附上答案

小美的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 的子矩形，只有一个是合法的。

小美的回文子串

小美有一个长为 n的字符串s，她希望删除尽可能少的字符，使得字符串不含长度为偶数的回文子串。

她想知道她最少要删除几个字符，请你帮帮她吧。

输入描述

输入包含两行。

第一行一个正整数n(1<=n<=10^5)，表示字符串s 的长度。

第二行一个长为n字符串s。

输出描述

输出包含一行一个整数，表示最少删除数量。

补充说明

子串：一个字符串从头或尾删除若干个（也可以不删）得到的结果字符串。回文：一个字符串正着读和倒着读一样，则该字符串回文。

示例 1

输入

5

aaabc

输出

2

示例 2

输入

1

e

输出

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]

小美的字符串切割

小美定义一个字符串的权值为：字符串长度乘以字符的种类数。例如，"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"