Skip to content

Latest commit

 

History

History
226 lines (184 loc) · 5.89 KB

README.md

File metadata and controls

226 lines (184 loc) · 5.89 KB
comments difficulty edit_url
true
困难

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)$。

相似题目：

Python3

# 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

Java

/**
 * 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;
    }
}

C++

/**
 * 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;
    }
};

Go

/**
 * 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
}

TypeScript

/**
 * 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;
}