Question

2753. 计算一个环形街道上的房屋数量 II

English Version

题目描述

给定一个代表 环形 街道的类 Street 和一个正整数 k，表示街道上房屋的最大数量（也就是说房屋数量不超过 k）。每个房屋的门初始时可以是开着的也可以是关着的（至少有一个房屋的门是开着的）。

刚开始，你站在一座房子的门前。你的任务是计算街道上的房屋数量。

Street 类包含以下函数：

• void closeDoor()：关闭当前房屋的门。
• boolean isDoorOpen()：如果当前房屋的门是开着的返回 true，否则返回 false。
• void moveRight()：向右移动到下一座房屋。

注意：在 环形 街道内，如果将房屋从 1 到 n 编号，则当 i < n 时 housei 右边的房子是 housei+1，housen 右边的房子是 house1。

返回 ans，它表示街道上的房屋数量。

 

示例 1：

输入：street = [1,1,1,1], k = 10
输出：4
解释：街道上有 4 座房屋，它们的门都是开着的。
房屋数量小于 k，即 10。

示例 2：

输入：street = [1,0,1,1,0], k = 5
输出：5
解释：街道上有 5 座房屋，向右移动时第 1、3 和 4 座房屋的门是开着的，其余的门都是关着的。
房屋数量等于 k，即 5。

 

提示：

• n 是房屋数量
• 1 <= n <= k <= 105
• street 是环形的
• 输入数据中至少有一扇门是开着的

解法

方法一：脑筋急转弯

我们注意到，题目中至少有一扇门是开着的，我们可以先找到其中一扇开着的门。

然后，我们跳过这扇开着的门，往右移动，每次移动时，计数器加一，如果遇到开着的门，就把门关上。那么答案就是最后一次遇到的开着的门时的计数器的值。

时间复杂度 $O(k)$，空间复杂度 $O(1)$。

相似题目：

• 2728. 计算一个环形街道上的房屋数量

# Definition for a street.
# class Street:
#   def closeDoor(self):
#     pass
#   def isDoorOpen(self):
#     pass
#   def moveRight(self):
#     pass
class Solution:
  def houseCount(self, street: Optional["Street"], k: int) -> int:
    while not street.isDoorOpen():
      street.moveRight()
    for i in range(1, k + 1):
      street.moveRight()
      if street.isDoorOpen():
        ans = i
        street.closeDoor()
    return ans

/**
 * Definition for a street.
 * class Street {
 *   public Street(int[] doors);
 *   public void closeDoor();
 *   public boolean isDoorOpen();
 *   public void moveRight();
 * }
 */
class Solution {
  public int houseCount(Street street, int k) {
    while (!street.isDoorOpen()) {
      street.moveRight();
    }
    int ans = 0;
    for (int i = 1; i <= k; ++i) {
      street.moveRight();
      if (street.isDoorOpen()) {
        ans = i;
        street.closeDoor();
      }
    }
    return ans;
  }
}

/**
 * Definition for a street.
 * class Street {
 * public:
 *   Street(vector<int> doors);
 *   void closeDoor();
 *   bool isDoorOpen();
 *   void moveRight();
 * };
 */
class Solution {
public:
  int houseCount(Street* street, int k) {
    while (!street->isDoorOpen()) {
      street->moveRight();
    }
    int ans = 0;
    for (int i = 1; i <= k; ++i) {
      street->moveRight();
      if (street->isDoorOpen()) {
        ans = i;
        street->closeDoor();
      }
    }
    return ans;
  }
};

/**
 * Definition for a street.
 * type Street interface {
 *   CloseDoor()
 *   IsDoorOpen() bool
 *   MoveRight()
 * }
 */
func houseCount(street Street, k int) (ans int) {
  for !street.IsDoorOpen() {
    street.MoveRight()
  }
  for i := 1; i <= k; i++ {
    street.MoveRight()
    if street.IsDoorOpen() {
      ans = i
      street.CloseDoor()
    }
  }
  return
}

/**
 * Definition for a street.
 * class Street {
 *   constructor(doors: number[]);
 *   public closeDoor(): void;
 *   public isDoorOpen(): boolean;
 *   public moveRight(): void;
 * }
 */
function houseCount(street: Street | null, k: number): number {
  while (!street.isDoorOpen()) {
    street.moveRight();
  }
  let ans = 0;
  for (let i = 1; i <= k; ++i) {
    street.moveRight();
    if (street.isDoorOpen()) {
      ans = i;
      street.closeDoor();
    }
  }
  return ans;
}