难度: Easy
Submission
运行时间: 143 ms
内存: 16.6 MB
# 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 i in range(k): street.openDoor() street.moveLeft() n=0 while street.isDoorOpen(): n+=1 street.closeDoor() street.moveLeft() return n
Explain
This solution uses a two-pass method on a circular street abstraction. Initially, the solution assumes an arbitrary starting point on the street and opens 'k' consecutive doors to the left (creating a unique pattern or a marker). Then, it iterates through the street starting from the first open door encountered, counting each house as it proceeds. It moves left and closes each door as it goes, until it encounters a closed door, indicating it has returned to the start point and therefore has counted all houses.
时间复杂度: O(n)
空间复杂度: O(1)
# 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: # Open k doors to the left to mark the start for i in range(k): street.openDoor() street.moveLeft() # Initialize house count n=0 # Loop until an unopened door is found while street.isDoorOpen(): n+=1 # Increment house count street.closeDoor() # Close the door behind street.moveLeft() # Move to the next house return n
Explore
选择使用 `k` 个连续的门作为标记点是为了创建一个独特的模式或标记,以便于识别起点。这种方法可以有效地以一个明确的标记区分开始和结束的位置,尤其是在环形街道的情况下。使用连续的门作为标记可以简化算法的逻辑,因为这样做可以确保在遍历街道时,一旦回到起点,立即可以通过检测到关闭的门识别出。如果使用数量少于 `k` 的门或其他不连续的标记方式,可能会增加在环形结构中识别起点和终点的复杂度,有可能导致错误的计数。
在初始状态下所有门都是关闭的情况下,算法首先会打开 `k` 个门作为标记。这样,当开始遍历街道时,算法会从这些已经打开的门开始,确认每一步都在正确的路径上。因此,即便是所有门最初都是关闭的,打开 `k` 门这一步骤保证了算法可以从一个明确的点开始计数,并且在环形街道上正确地回到起点。这避免了从一个未标记的状态开始可能导致的混淆和错误计数。
这种解决方案在街道非常长的情况下仍然有效,因为它系统地遍历每个门一次,并在确认全部门后结束计数。然而,确实存在性能问题的可能,特别是在街道极长时。每次操作(包括开门、关门和移动)都需消耗时间,如果街道长度非常大,这些操作的总时间可能会变得相当可观。在实际应用中,如果街道长度达到数千或更多,建议采用更高效的数据结构或优化算法来减少操作次数和提高性能。