头像

带翅膀的猫

时光荏苒,我们一直都在

《LeetCode刷题(Easy Rank):849. Maximize Distance to Closest Person》

 1月前  •   LeetCode  •     •   11  •   0

Question:

In a row of seats1 represents a person sitting in that seat, and 0 represents that the seat is empty. There is at least one empty seat, and at least one person sitting.

Alex wants to sit in the seat such that the distance between him and the closest person to him is maximized. Return that maximum distance to closest person.

Example 1:

示例Input: [1,0,0,0,1,0,1]
Output: 2
Explanation: 
If Alex sits in the second open seat (seats[2]), then the closest person has distance 2.
If Alex sits in any other open seat, the closest person has distance 1.
Thus, the maximum distance to the closest person is 2.

Example 2:

示例示例Input: [1,0,0,0]
Output: 3
Explanation: 
If Alex sits in the last seat, the closest person is 3 seats away.
This is the maximum distance possible, so the answer is 3.

Note:

  1. 1 <= seats.length <= 20000
  2. seats contains only 0s or 1s, at least one 0, and at least one 1.

Solution:

Alex 的座位与其他人座位有三种形式:①、在两个人之间,这也是最多的情况,这种情况最理想的结果就是在中间;②、最右边位置没人,其他人在Alex 左侧;③、最左边位置没人,其他人在Alex 右侧。我将每个有人的位置记录下,逐一判断这三种情况下的最远距离。

Pythonclass Solution:
    def maxDistToClosest(self, seats):
        """
        :type seats: List[int]
        :rtype: int
        """
        maximum=1
        pos = []
        for i in range(len(seats)):
            if seats[i]:pos.append(i)#记录每个有人的座位的索引
        for i in range(len(pos)-1):
            maximum = max((pos[i]+pos[i+1])//2-pos[i],maximum)#在两个人之间,最理想的结果就是在位置中间,故//2
        if seats[len(seats)-1]==0:#最右边位置没人
            maximum = max(len(seats)-1-pos[-1],maximum)
        if seats[0]==0:#最左边位置没人
            maximum = max(pos[0]-0,maximum)
        return maximum

相同原理,十分nice的代码:

JAVApublic int maxDistToClosest(int[] seats) {
	int i, j, res = 0, n = seats.length;
	for (i = j = 0; j < n; ++j)
		if (seats[j] == 1) {
			if (i == 0) res = Math.max(res, j - i);
			else res = Math.max(res, (j - i + 1) / 2);
			i = j + 1;
		}
	res = Math.max(res, n - i);
	return res;
}

 

上一篇:
下一篇:

 评论


 已有0条评论

    还没有任何评论,你来说两句吧!