Skip to content

Latest commit

 

History

History
234 lines (193 loc) · 5.63 KB

README.md

File metadata and controls

234 lines (193 loc) · 5.63 KB
Raw
comments difficulty edit_url tags
true
简单
数组
交互

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

English Version

题目描述

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

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

Street 类包含以下函数：

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

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

 

示例 1：

输入：street = [0,0,0,0], 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 <= 103

解法

方法一：遍历

我们先循环 $k$ 次，每次打开当前房子的门，然后向左移动一格，循环结束后，所有房子的门都是打开的。

然后，我们再循环左移，如果当前房子的门是打开的，就关闭它，房子数加一，继续左移，直到当前房子的门是关闭的，循环结束，返回房子数。

时间复杂度 $O(k)$，其中 $k$ 为题目给定的整数。空间复杂度 $O(1)$。

相似题目：

Python3

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

Java

/**
 * Definition for a street.
 * class Street {
 *     public Street(int[] doors);
 *     public void openDoor();
 *     public void closeDoor();
 *     public boolean isDoorOpen();
 *     public void moveRight();
 *     public void moveLeft();
 * }
 */
class Solution {
    public int houseCount(Street street, int k) {
        while (k-- > 0) {
            street.openDoor();
            street.moveLeft();
        }
        int ans = 0;
        while (street.isDoorOpen()) {
            ++ans;
            street.closeDoor();
            street.moveLeft();
        }
        return ans;
    }
}

C++

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

Go

/**
 * Definition for a street.
 * type Street interface {
 *     OpenDoor()
 *     CloseDoor()
 *     IsDoorOpen() bool
 *     MoveRight()
 *     MoveLeft()
 * }
 */
func houseCount(street Street, k int) (ans int) {
	for ; k > 0; k-- {
		street.OpenDoor()
		street.MoveLeft()
	}
	for ; street.IsDoorOpen(); street.MoveLeft() {
		ans++
		street.CloseDoor()
	}
	return
}

TypeScript

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