Skip to content

Latest commit

 

History

History
234 lines (193 loc) · 5.63 KB

File metadata and controls

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

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