当前位置：首页 > article >正文

【华为OD-E卷 - 机房布局 100分（python、java、c++、js、c）】

article 2025/1/4 6:03:32

【华为OD-E卷 - 机房布局 100分（python、java、c++、js、c）】

题目

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

输入描述

cabinets = “MIIM”

其中 M 表示机柜，I 表示间隔

输出描述

表示至少需要2个电箱

备注

1 ≤ strlen(cabinets) ≤ 10000 其中 cabinets[i] = ‘M’ 或者 ‘I’

用例

用例一：

输入：

MIIM

输出：

用例二：

输入：

MIM

输出：

用例三：

输入：

输出：

-1

用例四：

输入：

MMM

输出：

-1

python解法

解题思路：
输入的字符串 s 代表一个排列，其中字符 ‘M’ 和 ‘I’ 代表物品和箱子。
目标是通过判断字符 ‘M’ 和 ‘I’ 的相对位置来计算可以形成多少对 “箱子”。
每对 “箱子” 由一个 ‘M’ 和一个 ‘I’ 组成，可以是 ‘M’ 在前，‘I’ 在后；也可以是 ‘I’ 在前，‘M’ 在后。
遍历字符串，如果当前字符是 ‘M’，则检查其左右相邻的字符是否是 ‘I’，并确保不会重复计算。
如果找不到匹配的 ‘I’ 或者有不符合条件的字符排列，则返回 -1。

s = input()

def calc_boxes(s):
    l = len(s)  # 获取字符串长度
    count = 0  # 初始化箱子计数
    i = 0  # 初始化遍历索引
    while i < l:  # 使用while循环遍历字符串
        if s[i] == 'M':  # 如果当前字符是'M'
            if i + 1 < l and s[i + 1] == 'I':  # 如果'M'后面是'I'
                count += 1  # 找到一对箱子，计数加1
                i += 2  # 跳过这对'M'和'I'，继续检查下一个字符
            elif i - 1 >= 0 and s[i - 1] == 'I':  # 如果'M'前面是'I'
                count += 1  # 找到一对箱子，计数加1
                i += 1  # 跳过当前的'M'，继续检查下一个字符
            else:
                return -1  # 如果'M'没有配对的'I'，返回-1
        else:
            i += 1  # 如果当前字符不是'M'，继续向后遍历
    return count  # 返回找到的箱子对数

print(calc_boxes(s))  # 输出结果

java解法

解题思路
给定一个字符串，其中字符 ‘M’ 表示机器，字符 ‘I’ 表示电箱。目标是计算出能够组成多少个机器与电箱的配对，且每个配对必须由一个 ‘M’ 和一个 ‘I’ 组成。
配对时，优先选择将 ‘M’ 与其右侧的 ‘I’ 配对，如果右侧没有 ‘I’，则尝试与左侧的 ‘I’ 配对。
如果无法找到任何有效的配对，则返回 -1。
遍历字符串时，如果 ‘M’ 已经与电箱配对成功，则跳过这部分字符，继续检查下一个可能的配对

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String input = sc.next();  // 输入字符串
        System.out.println(getMinBoxes(input));  // 输出最小电箱数
    }

    // 主函数用于返回最小电箱数
    public static int getMinBoxes(String str) {
        return countValidBoxes(str);  // 调用辅助方法进行电箱数计算
    }

    // 计算有效的电箱对数
    private static int countValidBoxes(String str) {
        int length = str.length();  // 获取字符串长度
        int totalBoxes = 0;  // 初始化电箱计数器

        // 遍历字符串，根据规则判断电箱放置
        for (int i = 0; i < length; i++) {
            if (isMachine(str, i)) {  // 判断当前字符是否是机器 'M'
                // 尝试优先放置右边的电箱
                if (canPlaceRight(str, i)) {
                    totalBoxes++;  // 成功放置电箱，更新电箱计数
                    i += 2;  // 跳过已处理的部分，移动索引
                }
                // 若不能放置右边，尝试放置左边
                else if (canPlaceLeft(str, i)) {
                    totalBoxes++;  // 成功放置电箱，更新电箱计数
                }
                // 两边都无法放置电箱，则返回 -1
                else {
                    return -1;
                }
            }
        }
        return totalBoxes;  // 返回总的电箱数量
    }

    // 判断当前位置字符是否是机器 'M'
    private static boolean isMachine(String str, int index) {
        return str.charAt(index) == 'M';  // 如果字符为 'M' 返回 true
    }

    // 判断能否在右边放置电箱
    private static boolean canPlaceRight(String str, int index) {
        return index + 1 < str.length() && str.charAt(index + 1) == 'I';  // 判断右边是否是 'I'
    }

    // 判断能否在左边放置电箱
    private static boolean canPlaceLeft(String str, int index) {
        return index - 1 >= 0 && str.charAt(index - 1) == 'I';  // 判断左边是否是 'I'
    }
}