华为OD机试真题---机房布局

华为OD机试真题中的“机房布局”题目是一道关于字符串处理和逻辑判断的问题。以下是对该题目的详细解析：

一、题目描述

机房布局问题描述如下：

小明正在规划一个大型数据中心机房，为了使得机柜上的机器都能正常满负荷工作，需要确保在每个机柜边上至少要有一个电箱。为了简化题目，假设这个机房是一整排，M表示机柜，I表示间隔，要求返回整排机柜至少需要多少个电箱。如果无解则返回-1。

二、输入描述

一个字符串cabinets，其中M表示机柜，I表示间隔。字符串长度满足1 ≤ strlen(cabinets) ≤ 10000。
例如：cabinets = "MIIM"
其中M表示机柜，I表示间隔

三、输出描述

返回整排机柜至少需要多少个电箱。

2

表示至少需要2个电箱

补充说明：
1<= strlen(cabinets) <= 10000
其中 cabinets[i] = ‘M’ 或者 ‘I’

四、示例

示例1

输入：

MIIM

输出：

2

说明：

示例2

输入：

MIM

输出：

1

示例3

输入：

M

输出：

-1

示例4

输入：

MMM

输出：

-1

示例5

输入：

I

输出：

0

五、解题思路

1. 遍历字符串cabinets，检查每个字符。
2. 当遇到字符’M’时，判断其前面或后面是否有字符’I’。
   • 如果’M’后面有’I’，则组成一个有效的电箱，并跳过该’I’字符。
   • 如果’M’后面没有’I’，但前面有’I’，也可以组成一个有效的电箱。
   • 如果’M’前面和后面都没有’I’，则无法组成有效的电箱，返回-1。
3. 统计并返回有效的电箱数量。

六、代码实现

public class DataCenterLayout {/*** 计算可以组成的盒子数量** @param cabinets 一个字符串，包含一系列的'I'（代表绝缘体）和'M'（代表金属片）* @return 返回可以组成的盒子数量，如果无法组成任何盒子则返回-1*/public static int calcBoxes(String cabinets) {int length = cabinets.length();int count = 0; // 盒子数量初始化为0boolean[] used = new boolean[length]; // 标记'I'是否已被使用// 遍历字符串中的每个字符for (int i = 0; i < length; i++) {char currentChar = cabinets.charAt(i);// 当前字符为'M'时，尝试寻找与其配对的'I'if (currentChar == 'M') {// 检查'M'后面是否有'I'且未被使用boolean hasNextI = (i + 1 < length) && (cabinets.charAt(i + 1) == 'I') && !used[i + 1];// 检查'M'前面是否有'I'且未被使用（注意i-1不能小于0）boolean hasPrevI = (i - 1 >= 0) && (cabinets.charAt(i - 1) == 'I') && !used[i - 1];// 如果'M'前后都没有'I'，则无法组成有效的电箱，跳过当前'M'if (!hasNextI && !hasPrevI) {continue;}// 如果'M'前面有'I'且未被使用，则组成一个盒子，并标记'I'为已使用if (hasPrevI) {count++;used[i - 1] = true; // 标记前面的'I'已被使用}// 如果'M'后面有'I'且未被使用，则组成一个盒子，并标记'I'为已使用else if (hasNextI) {count++;used[i + 1] = true; // 标记后面的'I'已被使用}}}// 如果没有配对成功任何一个盒子，返回-1return count > 0 ? count : -1;}public static void main(String[] args) {// 示例测试String cabinets1 = "MIIM";System.out.println(calcBoxes(cabinets1)); // 输出: 2String cabinets2 = "MIM";System.out.println(calcBoxes(cabinets2)); // 输出: 1String cabinets3 = "M";System.out.println(calcBoxes(cabinets3)); // 输出: -1String cabinets4 = "MMM";System.out.println(calcBoxes(cabinets4)); // 输出: -1}
}

七、示例解析

1. 示例1：

   • 输入：MIIM
   • 输出：2
   • 解析：可以组成两个有效的电箱，分别是MI和MI。

2. 示例2：

   • 输入：MIM
   • 输出：1
   • 解析：可以组成一个有效的电箱MI，剩下的一个M由于前面或后面都没有I，所以无法组成有效的电箱，但题目要求至少需要一个电箱与M匹配，因此该情况下仍然输出1（假设题目允许单个M在字符串末尾或开头时，可以认为其“隐式”地与一个不存在的I匹配，或者理解为题目保证输入至少有一个有效解。但在严格意义上，此示例更准确的解读应依赖于题目对边界情况的明确说明。然而，根据给出的答案和常见理解，这里我们按照能形成一个有效电箱的情况来处理）。

3. 示例3：

   • 输入：M
   • 输出：-1
   • 解析：只有一个M，且前面和后面都没有I，无法组成有效的电箱。

4. 示例4：

   • 输入：MMM
   • 输出：-1
   • 解析：有三个M，但都没有与之匹配的I，无法组成有效的电箱。

通过以上解析，可以清晰地理解华为OD机试真题中“机房布局”问题的解题思路和方法。