华为OD机试真题-机房布局/栈解法【2023.Q1】
小明正在规划一个大型数据中心机房，需要满足的条件是：确保在每个机柜边上至少要有一个电箱。 已知：机房排成1排，我们用M表示机柜，I表示间隔。 请你返回这整排机房，至少需要多少个电箱。如果无解请返回-1。 输入描述 第一行输入一个字符串，由 M 和 I 组成，表示机房的组成样式 输出描述 输出一个整数，表示整排机房至少需要多少个电箱。 如果无解请返回-1。 示例1： 输入： MIIM 输出： 2
解题思路
除了模拟之外，这道题还可以用栈求解。 遍历输入的字符串，如果遇到字符 ‘M’，表示遇到一个机柜，首先判断该机柜是否满足前后都有机柜的情况，如果是，则直接输出 -1 并结束程序。 1.如果遇到机柜（‘M’），我们需要确保至少在其左侧或右侧放置一个电箱。我们计算左侧和右侧的位置（pos_left 和 pos_right）。 2.检查栈顶元素是否等于 pos_left。如果等于 pos_left，说明上一个机柜已经放置了电箱，可以在当前机柜的左侧重复使用这个电箱。 3.如果栈顶元素不等于 pos_left 或者栈为空，说明需要在当前机柜的右侧放置一个新的电箱。这种情况下，我们将 pos_right 压入栈，表示新放置的电箱位置。 如果遇到间隔（‘I’），直接跳过。 遍历结束后，栈中的元素个数就是所需的电箱数量。<
下一篇：
自定义用户-若依框架