(A卷,200分)- 机房布局（Java & JS & Python）

题目描述

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

输入描述

无

输出描述

无

用例

逻辑分析解法（最优解法）

题目解析

本题其实只要朝一个方向优先放电箱即可，但是通常我们习惯从左向右遍历，因此这里优先将电箱放在机柜的右边。

为什么要将电箱优先放在右边呢？比如下面这个例子：

I M I M

优先将机柜放在红色I位置，则最终只需要一个电箱。如果将机柜放绿色I位置，则最终需要两个电箱。

再比如下面这个例子

M I M I

由于我们是从左往右遍历，因此第一个机柜M，优先将电箱放在它的右边。

但是，如果机柜的右侧放不了电箱呢？比如

I M M I

此时，我们需要看机柜的左侧能不能放，如果能放，则放，不然对应机柜就没有配置电箱了。

如果机柜的左右两侧都放不了电箱呢？

M M I

此时应该直接返回-1。

另外，还有一个重要的点就是：

如果机柜的右侧可以放电箱，比如第 i 个位置是机柜，第 i + 1个位置是间隔，则我们可以将电箱放到第 i + 1个位置上，此时：第 i + 2 个位置是什么还需要关注吗？

比如：

M I M I

上面红色的M还需关注放不放电箱吗？答案是不需要，因为他必然有一个电箱了。

此时我们可以直接跳到i+3位置重新开始上面的判断。

Java算法源码

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    String str = sc.next();

    System.out.println(getResult(str));
  }

  public static int getResult(String str) {
    int n = str.length();

    // ans记录用了几个电箱
    int ans = 0;

    for (int i = 0; i < n; i++) {
      // 如果当前是机柜
      if (str.charAt(i) == 'M') {
        // 则优先将电箱放到该机柜的右边，如果机柜右边有间隔I的话
        if (i + 1 < n && str.charAt(i + 1) == 'I') {
          ans++;
          // 如果放成功了，即当前第 i 个位置是机柜，第i+1个位置是 电箱，那么第i+2个位置无论是机柜还是间隔都无所谓，下次我们直接从第i+3位置开始判断
          i += 2; // 这里 i += 2结合下轮for循环的i++，就是i += 3
        }
        // 如果当前第i位置的机柜右边无法放入电箱，则只能将电箱放到其左边第i-1位置，但是第i-1位置必须是间隔I
        else if (i - 1 >= 0 && str.charAt(i - 1) == 'I') {
          ans++;
        }
        // 如果当前机柜左右都无法放入电箱，则返回-1
        else {
          ans = -1;
          break;
        }
      }
    }

    return ans;
  }
}

JavaScript算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on("line", (line) => {
  console.log(getResult(line));
});

function getResult(str) {
  const n = str.length;

  // ans记录用了几个电箱
  let ans = 0;
  for (let i = 0; i < n; i++) {
    // 如果当前是机柜
    if (str[i] == "M") {
      // 则优先将电箱放到该机柜的右边，如果机柜右边有间隔I的话
      if (i + 1 < n && str[i + 1] == "I") {
        ans++;
        // 如果放成功了，即当前第 i 个位置是机柜，第i+1个位置是 电箱，那么第i+2个位置无论是机柜还是间隔都无所谓，下次我们直接从第i+3位置开始判断
        i += 2; // 这里 i += 2结合下轮for循环的i++，就是i += 3
      }
      // 如果当前第i位置的机柜右边无法放入电箱，则只能将电箱放到其左边第i-1位置，但是第i-1位置必须是间隔I
      else if (i - 1 >= 0 && str[i - 1] == "I") {
        ans++;
      }
      // 如果当前机柜左右都无法放入电箱，则返回-1
      else {
        ans = -1;
        break;
      }
    }
  }

  return ans;
}

Python算法源码

# 输入获取
s = input()


# 算法入口
def getResult(s):
    n = len(s)

    # ans记录用了几个电箱
    ans = 0
    i = 0
    while i < n:
        # 如果当前是机柜
        if s[i] == 'M':
            # 则优先将电箱放到该机柜的右边，如果机柜右边有间隔I的话
            if i + 1 < n and s[i + 1] == 'I':
                ans += 1
                # 如果放成功了，即当前第 i 个位置是机柜，第i+1个位置是 电箱，那么第i+2个位置无论是机柜还是间隔都无所谓，下次我们直接从第i+3位置开始判断
                i += 2  # 这里 i += 2结合后面的i +=1 ，就是i += 3
            #  如果当前第i位置的机柜右边无法放入电箱，则只能将电箱放到其左边第i-1位置，但是第i-1位置必须是间隔I
            elif i - 1 >= 0 and s[i - 1] == 'I':
                ans += 1
            # 如果当前机柜左右都无法放入电箱，则返回-1
            else:
                ans = -1
                break
        i += 1

    return ans


# 算法调用
print(getResult(s))

栈+区间问题解法

题目解析

本题，“无解”的情况应该是指：M的左右两边都是M，或者边界，比如：

• MMIIM：标红M的左边是边界，所以无法放电箱，右边是M，所以也无法放电箱
• IMMMI：标红M的左右两边都是M，因此无法放电箱

因此，遇到上面情况，我们应该返回-1。

接下来就是最少电箱的分配策略了，本题要求每台机柜的两边，至少有一边上配有电箱，那么最少电箱分配，肯定是尽可能地让两个机柜共享一个电箱。

我这里利用了区间交集的思想：

即，如果机柜处于 i 位置，则该机柜的区间为 [i-1, i+1]，需要注意的是i-1和i+1不能超过边界，如果超过边界，则取边界值。

如果后面一个机柜的区间和前面一个机柜有交集，则代表两个机柜可以共享一个电箱。

这里，我使用栈结构来实现电箱数的统计，即将机柜区间尝试压入栈中，如果要要入的机柜区间range和栈顶区间top有交集，则弹出栈顶区间top，并压入range。这样最终栈中区间数，就是电箱数了。

但是上面逻辑存在一个漏洞：那就是MIMIM这种情况，这这情况栈中只会剩下最后一个M的区间，但是实际上需要的电箱数是2。

这是因为，第2个M和第1个M存在交集后，我们就将第1个M弹出了，因此第2个M不仅代表了自身需要的电箱数，还代表了被弹出的第1个M的电箱数，因此即使第3个M和第2个M有交集，我们也不能将第2个M弹出，因为弹出的话，就会丢失第1个M需要的电箱数。

因此，我额外定义了一个stick标识，初始stick = false，表示栈顶区间未形成共享电箱

• 如果压入区间A和栈顶区间B存在交集，则将栈顶区间B弹出，并将stick=true，表示A区间已形成共享电箱

如果栈顶区间已形成共享电箱，即stick=true，则此时，我们可以直接压入新区间，并将stick重置为false。

2023.04.12 优化思路：

上面为了避免遗漏统计共享电箱，因此设计了一个stick变量，来记录栈顶区间是否挂载了共享电箱，如果挂载了，则栈顶区间不可弹出。

上面逻辑其实可以优化，其实优化思路很简单，就是：共享电箱挂载到哪个区间上的问题

我们假设栈顶区间为top，而要加入区间为new，现在top和new有交集，即可以共享电箱。

前面逻辑：是将共享电箱挂载到了new区间上，而栈中的区间数量又表示为所需电箱数，因此，上面逻辑做了两个动作：

• top区间弹出
• new区间压栈后，设置为不可弹出（即设置stick标志为true）

但是，我们完全可以转变思路，即一开始，就将共享电箱挂载到top区间上，而new区间不入栈。

此时，top区间肯定不会和后续区间产生交集，因此相当于天生有stick=true的标志。而new区间不入栈，也不会对所需电箱数产生影响。

JavaScript算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on("line", (line) => {
  console.log(getResult(line));
});

function getResult(str) {
  const n = str.length;
  const stack = [];
  let stick = false;

  for (let i = 0; i < str.length; i++) {
    if (str[i] == "M") {
      // 如果机柜A两边都是机柜，或者没有间隔，则无法给机柜A放电箱，返回-1
      let left = i - 1 < 0 || str[i - 1] == "M";
      let right = i + 1 >= n || str[i + 1] == "M";
      if (left && right) return -1;

      // 将求解最少电箱问题，转化为区间交集问题
      const range = [Math.max(0, i - 1), Math.min(n - 1, i + 1)];

      if (stack.length && !stick) {
        const e1 = stack.at(-1)[1];
        const s2 = range[0];

        if (e1 === s2) {
          stack.pop();
          stick = true;
        }
      } else {
        stick = false;
      }
      stack.push(range);
    }
  }

  return stack.length;
}

2023.04.12优化后解法

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on("line", (line) => {
  console.log(getResult(line));
});

function getResult(str) {
  const n = str.length;
  const stack = [];

  for (let i = 0; i < str.length; i++) {
    if (str[i] == "M") {
      // 如果机柜A两边都是机柜，或者没有间隔，则无法给机柜A放电箱，返回-1
      let left = i - 1 < 0 || str[i - 1] == "M";
      let right = i + 1 >= n || str[i + 1] == "M";
      if (left && right) return -1;

      // 将求解最少电箱问题，转化为区间交集问题
      const range = [Math.max(0, i - 1), Math.min(n - 1, i + 1)];

      if (stack.length) {
        const e1 = stack.at(-1)[1];
        const s2 = range[0];
        
        // 如果新区间和栈顶区间有交集，则可共用电箱，此时新区间不需要入栈，即这两个区间所需的电箱挂载在了此时的栈顶区间上
        if (e1 == s2) continue;
      }
      stack.push(range);
    }
  }

  return stack.length;
}

Java算法源码

import java.util.LinkedList;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    String str = sc.next();

    System.out.println(getResult(str));
  }

  public static int getResult(String str) {
    int n = str.length();
    LinkedList<Integer[]> stack = new LinkedList<>();
    boolean stick = false;

    for (int i = 0; i < n; i++) {
      if (str.charAt(i) == 'M') {
        // // 如果机柜A两边都是机柜，或者没有间隔，则无法给机柜A放电箱，返回-1
        boolean left = i - 1 < 0 || str.charAt(i - 1) == 'M';
        boolean right = i + 1 >= n || str.charAt(i + 1) == 'M';
        if (left && right) return -1;

        // 将求解最少电箱问题，转化为区间交集问题
        Integer[] range = {Math.max(0, i - 1), Math.min(n - 1, i + 1)};

        if (stack.size() > 0 && !stick) {
          int e1 = stack.getLast()[1];
          int s2 = range[0];

          if (e1 == s2) {
            stack.removeLast();
            stick = true;
          }
        } else {
          stick = false;
        }
        stack.addLast(range);
      }
    }

    return stack.size();
  }
}

2023.04.12优化后解法

import java.util.LinkedList;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    String str = sc.next();

    System.out.println(getResult(str));
  }

  public static int getResult(String str) {
    int n = str.length();
    LinkedList<Integer[]> stack = new LinkedList<>();

    for (int i = 0; i < n; i++) {
      if (str.charAt(i) == 'M') {
        // // 如果机柜A两边都是机柜，或者没有间隔，则无法给机柜A放电箱，返回-1
        boolean left = i - 1 < 0 || str.charAt(i - 1) == 'M';
        boolean right = i + 1 >= n || str.charAt(i + 1) == 'M';
        if (left && right) return -1;

        // 将求解最少电箱问题，转化为区间交集问题
        Integer[] range = {Math.max(0, i - 1), Math.min(n - 1, i + 1)};

        if (stack.size() > 0) {
          int e1 = stack.getLast()[1];
          int s2 = range[0];

          // 如果新区间和栈顶区间有交集，则可共用电箱，此时新区间不需要入栈，即这两个区间所需的电箱挂载在了此时的栈顶区间上
          if (e1 == s2) continue;
        }
        stack.addLast(range);
      }
    }

    return stack.size();
  }
}

Python算法源码

# 输入获取
s = input()


# 算法入口
def getResult(s):
    n = len(s)
    stack = []
    stick = False

    for i in range(n):
        if s[i] == 'M':
            # 如果机柜A两边都是机柜，或者没有间隔，则无法给机柜A放电箱，返回-1
            left = i - 1 < 0 or s[i - 1] == 'M'
            right = i + 1 >= n or s[i + 1] == 'M'

            if left and right:
                return -1

            # 将求解最少电箱问题，转化为区间交集问题
            ran = [max(0, i - 1), min(n - 1, i + 1)]

            if len(stack) > 0 and not stick:
                e1 = stack[-1][1]
                s2 = ran[0]

                if e1 == s2:
                    stack.pop()
                    stick = True
            else:
                stick = False

            stack.append(ran)

    return len(stack)


print(getResult(s))

2023.04.12优化后解法

# 输入获取
s = input()


# 算法入口
def getResult(s):
    n = len(s)
    stack = []

    for i in range(n):
        if s[i] == 'M':
            # 如果机柜A两边都是机柜，或者没有间隔，则无法给机柜A放电箱，返回-1
            left = i - 1 < 0 or s[i - 1] == 'M'
            right = i + 1 >= n or s[i + 1] == 'M'

            if left and right:
                return -1

            # 将求解最少电箱问题，转化为区间交集问题
            ran = [max(0, i - 1), min(n - 1, i + 1)]

            if len(stack) > 0:
                e1 = stack[-1][1]
                s2 = ran[0]

                if e1 == s2:
                    continue

            stack.append(ran)

    return len(stack)


print(getResult(s))